有向图转换&遍历&拓扑&最短路径

#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\n 1. Dijkstra(迪杰斯特拉算法):");
PRN_DK(DMG,&dist);
printf("\n\n\n 2. 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[%2d,%2d] : %5d ",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[%2d,%2d] : %5d ",i,j,flyd[i][j]);
printf("\n"); system("pause");
return 0;
}