原帖及讨论：http://bbs.bc-cn.net/dispbbs.asp?boardid=179&id=130955

#include <stdio.h>
#include <stdlib.h>
逆风编程精品
#include <limits.h>
#define MaxStr 20
typedef int Status;
typedef int ElemType;
typedef struct{
ElemType VNode;
int indgree;
}VexType;
typedef struct Arc{
VexType Adj;
unsigned int Weight;
struct Arc *NextArc;
}ArcType;
typedef struct{
VexType *Vex;
ArcType **FirstArc;//邻接表;
//ArcType **InvertArc; //逆邻接表;
int VexNums; //顶点总数;
}DLGraph;//图的邻接表结构定义;
typedef struct{
ElemType *Vex;
unsigned int **Arc;
int VexNums;
}DMGraph;//图的邻接矩阵结构定义;
//========================================================================================
Status CreateDMGraph(DMGraph *DMG);//创建图的邻接矩阵;
Status DMG_Traver(DMGraph DMG);//邻接矩阵的遍历;
Status DMG_DFS(DMGraph DMG,int v,int *Visited);//邻接矩阵深度遍历(递归);
Status DMG_DFS_Uni(DMGraph DMG,int v,int *Visited);//邻接矩阵深度遍历(非递归);
Status DMG_BFS(DMGraph DMG,int v,int *Visited);//邻接矩阵广度遍历;
Status DMG2DLG(DMGraph DMG,DLGraph *DLG);//邻接矩阵转换为邻接表;
Status DLG_Traver(DLGraph DLG);//邻 接 表的遍历;
Status DLG_DFS(DLGraph DLG,int v,int *Visited);//邻 接 表深度遍历(递归);
Status DLG_DFS_Uni(DLGraph DLG,int v,int *Visited);//邻 接 表深度遍历(非递归);
Status DLG_BFS(DLGraph DLG,int v,int *Visited);//邻 接 表广度遍历;
//---------------------------------------------------------
Status Topsort(DLGraph DLG,ElemType **ts);//邻接表有向图的Topsort;
Status Dijkstra(DMGraph DMG,ElemType v,unsigned int *dist);//Dijkstra;
Status PRN_DK(DMGraph DMG,unsigned int ***dis);//输出Dijkstra算法;
Status Floyd(DMGraph DMG,unsigned int ***flyd);//Floyd;
Status PRN_DMGraph(DMGraph DMG);//输出邻接矩阵;
Status PRN_DLGraph(DLGraph DLG);//输出邻接表;
//========================================================================================
int main(void)
{
int i,j;
DMGraph DMG;
DLGraph DLG;
ElemType *ts;
unsigned int **dist,**flyd;
printf(" 一、创立有向图的邻接矩阵：\n");
CreateDMGraph(&DMG);
PRN_DMGraph(DMG);
printf("\n\n 二、有向图-邻接矩阵的遍历：\n");
DMG_Traver(DMG);
printf("\n\n 三、邻接矩阵转换为邻接表：\n");
DMG2DLG(DMG,&DLG);
PRN_DLGraph(DLG);
printf("\n\n 四、有向图-邻接表的遍历：\n");
DLG_Traver(DLG);
printf("\n\n 五、邻接表有向图的拓扑排序：\n");
Topsort(DLG,&ts);
printf("\n\n\n");system("pause");
printf("\n\n 六、邻接矩阵有向图的各点最短路径：\n\n1. Dijkstra(迪杰斯特拉算法):");
PRN_DK(DMG,&dist);
printf("\n\n\n2. Floyd(弗洛伊德算法):");
Floyd(DMG,&flyd);

printf("\n");system("pause");
printf("\n\n\nDijkstra最短路径测试输出：\n 某两点 ： 最短路径");
for(i = 1;i <= DMG.VexNums;i )
for(j = 1;j <= DMG.VexNums;j )
if(dist[i][j] < INT_MAX) printf("\n[-,-] : ] ",i,j,dist[i][j]);
printf("\n\nFloyd最短路径测试输出：\n 某两点 ： 最短路径");
for(i = 1;i <= DMG.VexNums;i )
for(j = 1;j <= DMG.VexNums;j )
if(flyd[i][j] < INT_MAX) printf("\n[-,-] : ] ",i,j,flyd[i][j]);
printf("\n");system("pause");
return 0;
}

//文件格式参见"无向图"说明:
//http://bbs.bc-cn.net/dispbbs.asp?boardID=179&ID=129767

[1][2]下一页