原帖及讨论：http://bbs.bccn.net/thread-130955-1-1.html #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;
}
// 文件格式参见"无向图"说明:
//http://bbs.bc-cn.net/dispbbs.asp?boardID=179&ID=129767 Status CreateDMGraph(DMGraph *DMG) //创建图的邻接矩阵;
{
char ReadFileName[MaxStr];
unsigned int w;
FILE *fp;
int i,j;
do{
printf("/n 输入文本文件名：");
gets(ReadFileName);
}while(ReadFileName[0] == '/0' || !(fp = fopen(ReadFileName,"r"))); fscanf(fp,"%d",&DMG->VexNums); //得到顶点总数;
if(!(DMG->Vex = (ElemType *)malloc((DMG->VexNums+1)*sizeof(ElemType))))
{printf("/n内存溢出。");return 1;}
if(!(DMG->Arc = (unsigned int **)malloc((DMG->VexNums+1)*sizeof(unsigned int*))))
{printf("/n内存溢出。");return 1;}
for(i = 1;i <= DMG->VexNums;i++) //邻接矩阵初始化;
{
DMG->Vex[i] = i; //
if(!(DMG->Arc[i]=(unsigned int *)malloc((DMG->VexNums+1)*sizeof(unsigned int))))
{printf("/n内存溢出。");return 1;}
for(j = 1;j <= DMG->VexNums;j++)
{
DMG->Arc[i][j] = INT_MAX;
}
}
while(fscanf(fp,"%d%d%u",&i,&j,&w) == 3) DMG->Arc[i][j] = w;//
fclose(fp);
return 0;
}
//========================================================================================
Status DMG2DLG(DMGraph DMG,DLGraph *DLG) //图的邻接矩阵转换为邻接表;
{
int i,j;
ArcType *p = NULL;
DLG->VexNums = DMG.VexNums;
if(!(DLG->Vex = (VexType *)malloc((DLG->VexNums+1)*sizeof(VexType))))
{printf("/n内存溢出。");return 1;}
if(!(DLG->FirstArc = (ArcType **)malloc((DLG->VexNums+1)*sizeof(ArcType*))))
{printf("/n内存溢出。");return 1;}
for(i = 1;i <= DLG->VexNums;i++)
{
DLG->Vex[i].VNode = DMG.Vex[i]; //
DLG->FirstArc[i] = NULL;
DLG->Vex[i].indgree = 0;
for(j = 1;j <= DMG.VexNums;j++)
{
if(DMG.Arc[i][j] < INT_MAX)
{
if(!(p = (ArcType *)malloc(sizeof(ArcType))))
{printf("/n内存溢出。");return 1;}
p->Adj.VNode = DMG.Vex[j];
p->Weight = DMG.Arc[i][j];
p->NextArc = DLG->FirstArc[i];
DLG->FirstArc[i] = p;
}
}
for(j = 1;j <= DMG.VexNums;j++)
{
if(DMG.Arc[j][i] < INT_MAX) ++DLG->Vex[i].indgree;
}
}
return 0;
}
//========================================================================================
Status DMG_Traver(DMGraph DMG) //邻接矩阵的遍历;
{
int i,*Visited;
if(!(Visited = (int *)malloc((DMG.VexNums+1)*sizeof(int))))
{printf("/n内存溢出。");return 1;}
printf("/n 1. 图的深度遍历：/n递 归：");
for(i = 1;i <= DMG.VexNums;i++) Visited[i] = 0;
for(i = 1;i <= DMG.VexNums;i++)
if(Visited[i] == 0) DMG_DFS(DMG,i,Visited);
printf("/n非递归：");
for(i = 1;i <= DMG.VexNums;i++) Visited[i] = 0;
for(i = 1;i <= DMG.VexNums;i++)
if(Visited[i] == 0) DMG_DFS_Uni(DMG,i,Visited);
printf("/n/n 2. 图的广度遍历：/n/t");
for(i = 1;i <= DMG.VexNums;i++) Visited[i] = 0;
for(i = 1;i <= DMG.VexNums;i++)
if(Visited[i] == 0) DMG_BFS(DMG,i,Visited);
return 0;
}
//========================================================================================
Status DLG_Traver(DLGraph DLG) //邻 接 表的遍历;
{
int i,*Visited;
if(!(Visited = (int *)malloc((DLG.VexNums+1)*sizeof(int))))
{printf("/n内存溢出。");return 1;}
printf("/n 1. 图的深度遍历：/n递 归：");
for(i = 1;i <= DLG.VexNums;i++) Visited[i] = 0;
for(i = 1;i <= DLG.VexNums;i++)
if(Visited[i] == 0) DLG_DFS(DLG,i,Visited);
printf("/n非递归：");
for(i = 1;i <= DLG.VexNums;i++) Visited[i] = 0;
for(i = 1;i <= DLG.VexNums;i++)
if(Visited[i] == 0) DLG_DFS_Uni(DLG,i,Visited);
printf("/n/n 2. 图的广度遍历：/n/t");
for(i = 1;i <= DLG.VexNums;i++) Visited[i] = 0;
for(i = 1;i <= DLG.VexNums;i++)
if(Visited[i] == 0) DLG_BFS(DLG,i,Visited);
printf("/n");
return 0;
}
//========================================================================================
Status DMG_DFS(DMGraph DMG,int v,int *Visited) //邻接矩阵深度遍历(递 归);
{
int i;
Visited[v] = 1;
printf("%2d ->",v);
for(i = 1;i <= DMG.VexNums;i++)
if(Visited[i] == 0 && DMG.Arc[v][i] < INT_MAX)
DMG_DFS(DMG,i,Visited);
return 0;
}
//========================================================================================
Status DLG_DFS(DLGraph DLG,int v,int *Visited) //邻 接 表深度遍历(递 归);
{
ArcType *p = NULL;
Visited[v] = 1;
printf("%2d ->",v);
p = DLG.FirstArc[v];
while(p != NULL)
{
if(Visited[p->Adj.VNode] == 0) DLG_DFS(DLG,p->Adj.VNode,Visited);
p = p->NextArc;
}
return 0;
}
//========================================================================================
Status DMG_DFS_Uni(DMGraph DMG,int v,int *Visited) //邻接矩阵深度遍历(非递归);
{
int i,*Stack,top = -1;
if(!(Stack = (int *)malloc((DMG.VexNums+1)*sizeof(int))))
{printf("/n内存溢出。");return 1;}
Visited[v] = 1;
printf("%2d ->",v);
Stack[++top] = v;
while(top != -1)
{
for(i = 1;i <= DMG.VexNums;i++)
if(Visited[i] == 0 && DMG.Arc[Stack[top]][i] < INT_MAX)
{
Visited[i] = 1;
printf("%2d ->",i);
Stack[++top] = i;
break;
}
if(i == DMG.VexNums+1) --top;
}
return 0;
}
//========================================================================================
Status DLG_DFS_Uni(DLGraph DLG,int v,int *Visited) //邻 接 表深度遍历(非递归);
{
int *Stack,top = -1;
ArcType *p = NULL;
if(!(Stack = (int *)malloc((DLG.VexNums+1)*sizeof(int))))
{printf("/n内存溢出。");return 1;}
Visited[v] = 1;
printf("%2d ->",v);
Stack[++top] = v;
while(top != -1)
{
p = DLG.FirstArc[Stack[top]];
while(p != NULL)
{
if(Visited[p->Adj.VNode] == 0)
{
Visited[p->Adj.VNode] = 1;
printf("%2d ->",p->Adj.VNode);
Stack[++top] = p->Adj.VNode;
break;
}
p = p->NextArc;
}
if(p == NULL) --top;
}
return 0;
}
//========================================================================================
Status DMG_BFS(DMGraph DMG,int v,int *Visited) //邻接矩阵广度遍历;
{
int i,*Queue,rear,front;
if(!(Queue = (int *)malloc((DMG.VexNums+1)*sizeof(int))))
{printf("/n内存溢出。");return 1;}
Visited[v] = 1;
printf("%2d ->",v);
rear = front = 0;
rear = (rear+1)%DMG.VexNums;
Queue[rear] = v;
while(rear != front)
{
front = (front+1)%DMG.VexNums;
for(i = 1;i <= DMG.VexNums;i++)
if(Visited[i] == 0 && DMG.Arc[Queue[front]][i] < INT_MAX)
{
Visited[i] = 1;
printf("%2d ->",i);
rear = (rear+1)%DMG.VexNums;
Queue[rear] = i;
}
}
return 0;
}
//========================================================================================
Status DLG_BFS(DLGraph DLG,int v,int *Visited) //邻 接 表广度遍历;
{
ArcType *p = NULL;
int *Queue,rear,front;
if(!(Queue = (int *)malloc((DLG.VexNums+1)*sizeof(int))))
{printf("/n内存溢出。");return 1;}
rear = front = 0;
Visited[v] = 1;
printf("%2d ->",v);
rear = (rear+1)%DLG.VexNums;
Queue[rear] = v;
while(rear != front)
{
front = (front+1)%DLG.VexNums;
p = DLG.FirstArc[Queue[front]];
while(p != NULL)
{
if(Visited[p->Adj.VNode] == 0)
{
Visited[p->Adj.VNode] = 1;
printf("%2d ->",p->Adj);
rear = (rear+1)%DLG.VexNums;
Queue[rear] = p->Adj.VNode;
}
p = p->NextArc;
}
}
return 0;
}
//========================================================================================
Status Topsort(DLGraph DLG,ElemType **ts) //邻接表有向图的Topsort拓扑排序;
{
int i,j,k,m = 0,top = -1;
ArcType *tp,*p;
if(!(*ts = (ElemType *)malloc((DLG.VexNums+1)*sizeof(ElemType))))
{printf("/n内存溢出。");return 1;}
if(!(tp = (ArcType *)malloc((DLG.VexNums+1)*sizeof(ArcType))))
{printf("/n内存溢出。");return 1;}
printf(" Topsort：/n/n ");
for(i = 1;i <= DLG.VexNums;i++) //初始化tp;
{
tp[i].Adj.VNode = DLG.Vex[i].VNode;
tp[i].NextArc = DLG.FirstArc[i];
tp[i].Adj.indgree = DLG.Vex[i].indgree;
if(DLG.Vex[i].indgree == 0)
{
tp[i].Adj.indgree = top;
top = i;
}
}
while(top != -1)
{
j = top;
top = tp[top].Adj.indgree;
printf(" %2d ,",tp[j].Adj.VNode);
++m;
p = tp[j].NextArc;
while(p != NULL)
{
k = p->Adj.VNode;
--tp[k].Adj.indgree;
if(tp[k].Adj.indgree == 0)
{
tp[k].Adj.indgree = top;
top = k;
}
p = p->NextArc;
}
}
if(m < DLG.VexNums) printf("/n不能拓扑!/n");
return 0;
}
//========================================================================================
Status PRN_DK(DMGraph DMG,unsigned int ***dis) //输出Dijkstra最短路径;
{
int i,j,flag;
unsigned int **dist;
if(!(dist = (unsigned int **)malloc((DMG.VexNums+1)*sizeof(unsigned int*))))
{printf("/n内存溢出。");return 1;}
*dis = dist;
for(i = 1;i <= DMG.VexNums;i++)
{
if(!(dist[i] = (unsigned int *)malloc((DMG.VexNums+1)*sizeof(unsigned int))))
{printf("/n内存溢出。");return 1;}
Dijkstra(DMG,i,dist[i]); //Dijkstra最短路径;
}
for(i = 1;i <= DMG.VexNums;i++)
{
flag = 0;
printf("/n从%3d出发的最短路径：",i);
for(j = 1;j <= DMG.VexNums;j++)
{
if(j != i && dist[i][j] < INT_MAX)
{
printf("/n/t自%3d ==>%3d点：%4d",i,j,dist[i][j]);
flag = 1;
//if(j != i && dist[i][j] == INT_MAX) printf("/n/t自%3d ==>%3d点： ∞",i,j);
//else if(j == i);printf("/n/t自%3d ==>%3d点：%4d",i,j,dist[i][j]);
}
}
if(flag == 0) printf("/n/t没有任何路径...555555");
}
return 0;
}
//========================================================================================
Status Dijkstra(DMGraph DMG,ElemType v,unsigned int *dist)//最短路径Dijkstra(迪杰斯特拉);
{
int i,j,t;
ElemType *flag;
unsigned int min;
if(!(flag = (ElemType *)malloc((DMG.VexNums+1)*sizeof(ElemType))))
{printf("/n内存溢出。");return 1;}
for(i = 1;i <= DMG.VexNums;i++) //初始化,置U={v}到V-U到各点最短路径;
{
flag[i] = 0;
dist[i] = DMG.Arc[v][i];
}
flag[v] = 1; //v并入U;
for(i = 1;i <= DMG.VexNums;i++)
{
min = INT_MAX;
t = i;
for(j = 1;j <= DMG.VexNums;j++) //找到U到V-U最小权值(最短路径);
{
if(flag[j] == 0 && min > dist[j])
{
min = dist[j];
t = j;
}
}
flag[t] = 1; //t并入U;
for(j = 1;j <= DMG.VexNums;j++) //重置U到V-U各点最短路径;
{
if(flag[j] == 0 && dist[t] + DMG.Arc[t][j] < dist[j])
{
dist[j] = dist[t] + DMG.Arc[t][j];
}
}
}
return 0;
}
//========================================================================================
Status Floyd(DMGraph DMG,unsigned int ***flyd) //Floyd(弗洛伊德)最短路径;
{ int i,j,k,**Path = NULL;
unsigned int **Weight = NULL;
if(!(Path = (int **)malloc((DMG.VexNums+1)*sizeof(int*))))
{printf("/n内存溢出。");return 1;}
if(!(Weight = (unsigned int **)malloc((DMG.VexNums+1)*sizeof(unsigned int*))))
{printf("/n内存溢出。");return 1;}
*flyd = Weight;
for(i = 1;i <= DMG.VexNums;i++) //初始化;
{
if(!(Path[i] = (int *)malloc((DMG.VexNums+1)*sizeof(int))))
{printf("/n内存溢出。");return 1;}
if(!(Weight[i] = (unsigned int *)malloc((DMG.VexNums+1)*sizeof(unsigned int))))
{printf("/n内存溢出。");return 1;}
for(j = 1;j <= DMG.VexNums;j++)
{
Weight[i][j] = DMG.Arc[i][j];
Path[i][j] = 0;
}
}
for(k = 1;k <= DMG.VexNums;k++) //Floyd迭代算法;
for(i = 1;i <= DMG.VexNums;i++)
for(j = 1;j <= DMG.VexNums;j++)
if(Weight[i][j] > (Weight[i][k] + Weight[k][j]))
{
Weight[i][j] = Weight[i][k] + Weight[k][j];
Path[i][j] = k;
}
for(i = 1;i <= DMG.VexNums;i++) //输出;
{
printf("/n从%3d出发的最短路径：",i);
for(j = 1;j <= DMG.VexNums;j++)
{
if(j != i && Weight[i][j] < INT_MAX)
printf("/n/t自%3d ==>%3d点：%4d",i,j,Weight[i][j]);
}
}
return 0;
}
//========================================================================================
Status PRN_DMGraph(DMGraph DMG) //输出邻接矩阵;
{
int i,j;
for(i = 1;i <= DMG.VexNums;i++)
{
printf("/n/t");
for(j = 1;j <= DMG.VexNums;j++)
{
if(DMG.Arc[i][j] < INT_MAX) printf(" %3d ",DMG.Arc[i][j]);
else printf(" ∞ ");
}
printf("/n");
}
return 0;
}
//========================================================================================
Status PRN_DLGraph(DLGraph DLG) //输出邻接表;
{
int i;
ArcType *p = NULL;
for(i = 1;i <= DLG.VexNums;i++)
{
printf("/n %2d(入度%2d) ==> ",i,DLG.Vex[i].indgree);
p = DLG.FirstArc[i];
while(p != NULL)
{
if(p->NextArc) printf("%2d(%3d) ->",p->Adj.VNode,p->Weight);
else printf("%2d(%3d) 。",p->Adj.VNode,p->Weight);
p = p->NextArc;
}
}
return 0;
} |