#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; //頂點總數(shù);
}DLGraph; //圖的鄰接表結(jié)構(gòu)定義;
typedef struct{
ElemType *Vex;
unsigned int **Arc;
int VexNums;
}DMGraph; //圖的鄰接矩陣結(jié)構(gòu)定義;
//========================================================================================
Status CreateDMGraph(DMGraph *DMG); //創(chuàng)建圖的鄰接矩陣;
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); //鄰接矩陣轉(zhuǎn)換為鄰接表;
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( " 一、創(chuàng)立有向圖的鄰接矩陣：\n");
CreateDMGraph(&DMG);
PRN_DMGraph(DMG);
printf("\n\n 二、有向圖-鄰接矩陣的遍歷：\n");
DMG_Traver(DMG);
printf("\n\n 三、鄰接矩陣轉(zhuǎ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;
}