本文是[数据结构基础系列(7)：图]中第9课时[BFS的应用]的例程。
（程序中graph.h是图存储结构的“算法库”中的头文件，详情请单击链接…）
1、最短最路径 问题：求不带权连通图G中从顶点u到顶点v的一条最短路径。
{int data;//顶点编号int parent;//前一个顶点的位置} QUERE;//非环形队列类型void ShortPath(ALGraph *G,int u,int v){//输出从顶点u到顶点v的最短逆路径ArcNode *p;int w,i;QUERE qu[MAXV];visited[MAXV];for (i=0; i<G->n; i++)//访问标记置初值0visited[i]=0;rear++;//顶点u进队qu[rear].data=u;qu[rear].parent=-1;visited[u]=1;while (front!=rear)//队不空循环{front++;//出队顶点ww=qu[front].data;if (w==v)//找到v时输出路径之逆并退出{i=front;//通过队列输出逆路径while (qu[i].parent!=-1){printf(“%2d “,qu[i].data);i=qu[i].parent;}printf(“%2d\n”,qu[i].data);break;}p=G->adjlist[w].firstarc; //找w的第一个邻接点while (p!=NULL){if (visited[p->adjvex]==0){visited[p->adjvex]=1;rear++;//将w的未访问过的邻接点进队qu[rear].data=p->adjvex;qu[rear].parent=front;}p=p->nextarc;//找w的下一个邻接点}}}int main(){ALGraph *G;int A[9][9]={{0,1,1,0,0,0,0,0,0},{0,0,0,1,1,0,0,0,0},{0,0,0,0,1,1,0,0,0},{0,0,0,0,0,0,1,0,0},{0,0,0,0,0,1,1,0,0},{0,0,0,0,0,0,0,1,0},{0,0,0,0,0,0,0,1,1},{0,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0}}; //请画出对应的有向图ArrayToList(A[0], 9, G);ShortPath(G,0,7);return 0;}
附：测试用图结构
2、最远顶点 问题：求不带权连通图G中，，距离顶点v最远的顶点k
Maxdist(ALGraph *G,int v){ArcNode *p;int i,j,k;front=0,rear=0;//队列的头、尾指针for (i=0; i<G->n; i++)//初始化访问标志数组visited[i]=0;rear++;Qu[rear]=v;//顶点v进队visited[v]=1;//标记v已访问while (rear!=front){front=(front+1)%MAXV;k=Qu[front];//顶点k出队p=G->adjlist[k].firstarc;//找第一个邻接点while (p!=NULL)//所有未访问过的相邻点进队{j=p->adjvex;//邻接点为顶点jif (visited[j]==0)//若j未访问过{visited[j]=1;rear=(rear+1)%MAXV;Qu[rear]=j; //进队}p=p->nextarc;//找下一个邻接点}}return k;}int main(){ALGraph *G;int A[9][9]={{0,1,1,0,0,0,0,0,0},{0,0,0,1,1,0,0,0,0},{0,0,0,0,1,1,0,0,0},{0,0,0,0,0,0,1,0,0},{0,0,0,0,0,1,1,0,0},{0,0,0,0,0,0,0,1,0},{0,0,0,0,0,0,0,1,1},{0,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0}}; //请画出对应的有向图ArrayToList(A[0], 9, G);printf(“离顶点0最远的顶点:%d”,Maxdist(G,0));return 0;}
附：测试用图结构
每个人在他的人生发轫之初，总有一段时光，
