本文是[数据结构基础系列(7)：图]中第4课时[图的邻接矩阵存储结构及算法]的例程。
（程序中graph.h是图存储结构的“算法库”中的头文件，详情请单击链接…）
1、是否有简单路径? 问题：假设图G采用邻接表存储，设计一个算法，判断顶点u到v是否有简单路径。
visited[MAXV];//定义存放节点的访问标志的全局数组void ExistPath(ALGraph *G,int u,int v, bool &has){int w;ArcNode *p;visited[u]=1;if(u==v){has=true;return;}p=G->adjlist[u].firstarc;while (p!=NULL){w=p->adjvex;if (visited[w]==0)ExistPath(G,w,v,has);p=p->nextarc;}}void HasPath(ALGraph *G,int u,int v){int i;bool flag = false;for (i=0; i<G->n; i++)visited[i]=0; //访问标志数组初始化ExistPath(G,u,v,flag);printf(” 从 %d 到 %d “, u, v);if(flag)printf(“有简单路径\n”);elseprintf(“无简单路径\n”);}int main(){ALGraph *G;int A[5][5]={{0,0,0,0,0},{0,0,1,0,0},{0,0,0,1,1},{0,0,0,0,0},{1,0,0,1,0},}; //请画出对应的有向图ArrayToList(A[0], 5, G);HasPath(G, 1, 0);HasPath(G, 4, 1);return 0;}
附：测试图结构及存储
2、输出简单路径 问题：假设图G采用邻接表存储，设计一个算法输出图G中从顶点u到v的一条简单路径（假设图G中从顶点u到v至少有一条简单路径）。
visited[MAXV];//定义存放节点的访问标志的全局数组void FindAPath(ALGraph *G,int u,int v,int path[],int d){//d表示path中的路径长度，初始为-1int w,i;ArcNode *p;visited[u]=1;d++;path[d]=u; //路径长度d增1，顶点u加入到路径中if (u==v) //找到一条路径后输出并返回{printf(“一条简单路径为:”);for (i=0; i<=d; i++)printf(“%d “,path[i]);printf(“\n”);return;//找到一条路径后返回}p=G->adjlist[u].firstarc; //p指向顶点u的第一个相邻点while (p!=NULL){w=p->adjvex; //相邻点的编号为wif (visited[w]==0)FindAPath(G,w,v,path,d);p=p->nextarc; //p指向顶点u的下一个相邻点}}void APath(ALGraph *G,int u,int v){int i;int path[MAXV];for (i=0; i<G->n; i++)visited[i]=0; //访问标志数组初始化FindAPath(G,u,v,path,-1); //d初值为-1，调用时d++，即变成了0}int main(){ALGraph *G;int A[5][5]={{0,0,0,0,0},{0,0,1,0,0},{0,0,0,1,1},{0,0,0,0,0},{1,0,0,1,0},}; //请画出对应的有向图ArrayToList(A[0], 5, G);APath(G, 1, 0);APath(G, 4, 1);return 0;}
3、输出所有路径 问题：输出从顶点u到v的所有简单路径。
visited[MAXV];//定义存放节点的访问标志的全局数组void FindPaths(ALGraph *G,int u,int v,int path[],int d)//d是到当前为止已走过的路径长度，调用时初值为-1{int w,i;ArcNode *p;visited[u]=1;d++;//路径长度增1path[d]=u;//将当前顶点添加到路径中if (u==v && d>1)//输出一条路径{printf(” “);for (i=0; i<=d; i++)printf(“%d “,path[i]);printf(“\n”);}p=G->adjlist[u].firstarc; //p指向u的第一条边while(p!=NULL){w=p->adjvex;//w为u的邻接顶点if (visited[w]==0)//若顶点未标记访问，则递归访问之FindPaths(G,w,v,path,d);p=p->nextarc; //找u的下一个邻接顶点}visited[u]=0; //恢复环境}void DispPaths(ALGraph *G,int u,int v){int i;int path[MAXV];for (i=0; i<G->n; i++)visited[i]=0; //访问标志数组初始化printf(“从%d到%d的所有路径:\n”,u,v);FindPaths(G,u,v,path,-1);printf(“\n”);}int main(){ALGraph *G;int A[5][5]={{0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0}}; //请画出对应的有向图ArrayToList(A[0], 5, G);DispPaths(G, 1, 4);return 0;}
附：测试用的图结构、存储结构、运行结果
人生，一场人喧鼓响的戏，我只是一个平凡的过客，
