第十二周项目4-利用遍历思想求解图问题（6-7）

/*   Copyright (c)2016,烟台大学计算机与控制工程学院   All rights reserved.   文件名称：第十二周项目4 - 利用遍历思想求解图问题.cpp   作    者：陈晓琳   完成日期：2016年11月18日   版 本 号：v1.0      问题描述: 假设图G采用邻接表存储，分别设计实现以下要求的算法，要求用区别于示例中的图进行多次测试，通过观察输出值，掌握相关问题的处理方法。        　　 （6）求不带权连通图G中从顶点u到顶点v的一条最短路径。    　　   （7）求不带权连通图G中，距离顶点v最远的顶点k    输入描述：若干测试数据。   程序输出：相应的数据输出。    */     （1）最短路径

源代码：

[cpp]  view plain  copy typedef struct     {         int data;                   //顶点编号         int parent;                 //前一个顶点的位置     } QUERE;                        //非环形队列类型          void ShortPath(ALGraph *G,int u,int v)     {         //输出从顶点u到顶点v的最短逆路径         ArcNode *p;         int w,i;         QUERE qu[MAXV];             //非环形队列         int front=-1,rear=-1;       //队列的头、尾指针         int visited[MAXV];         for (i=0; i<G->n; i++)      //访问标记置初值0             visited[i]=0;         rear++;                     //顶点u进队         qu[rear].data=u;         qu[rear].parent=-1;         visited[u]=1;         while (front!=rear)         //队不空循环         {             front++;                //出队顶点w             w=qu[front].data;             if (w==v)               //找到v时输出路径之逆并退出             {                 i=front;            //通过队列输出逆路径                 while (qu[i].parent!=-1)                 {                     printf("- ",qu[i].data);                     i=qu[i].parent;                 }                 printf("-\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的下一个邻接点             }         }     }     主函数：

[cpp]  view plain  copy 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）最远顶点

源代码：

[cpp]  view plain  copy int Maxdist(ALGraph *G,int v)     {         ArcNode *p;         int i,j,k;         int Qu[MAXV];               //环形队列         int visited[MAXV];              //访问标记数组         int 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;            //邻接点为顶点j                 if (visited[j]==0)          //若j未访问过                 {                     visited[j]=1;                     rear=(rear+1)%MAXV;                     Qu[rear]=j; //进队                 }                 p=p->nextarc;           //找下一个邻接点             }         }         return k;     }     主函数：

[cpp]  view plain  copy 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;     }     运行结果：

知识点总结：

图的遍历。