本文共 2025 字，大约阅读时间需要 6 分钟。

例: 求出距离顶点v0的最短路径长度为最长的一个顶点，并要求尽可能节省时间

分析：

int  maxdist (Graph G, int v0) {
         int w;  Queue  Q;                    // 定义算法中用到的局部变量和队列      for (i=1; i<=n; i++)     visited[i]=FALSE;//初始化标志位            visited[v0]=TRUE;           //访问顶点v0，其中仅需设置访问标志      Q.Append(v0);                        // 被访问顶点入队      while (!Empty(Q)){
                v=Q.Serve();                    // 从队列Q中取顶点，以检测和访问其邻接顶点             w=firstadj(G,v);              // 求顶点v的第一个邻接点             while (w!=0) {
                     // 依次访问v的未被访问过的邻接点                    if (!visited[w])                               {
    visited[w]=TRUE; Q.Append(w); }        // 访问邻接点w                    w=nextadj(G,v,w);              }             }       return  v;                              //将最后一个出队列的v作为结果返回}

图结构的bfs生成树及其双亲表示形式

简便起见，选择双亲表示法，即对每个顶点，仅给出其父结点信息。

void bfsSpanTree (Graph G, int v0){
           int w;  queue  Q;            for (i=1; i<=n; i++)   visited[i]=FALSE;         visited[v0]=TRUE; Q.Append(v0); //访问顶点v0，其中仅设置访问标志         parentof[v0]=0;                        //记录顶点v0的双亲结点为0        while (!Empty(Q)){
                  v=Q.Serve();        // 从队列Q中取出顶点到v, 以访问其邻接顶点               w=firstadj(G,v);   //  求顶点v的第一个邻接点               while (w!=0){
         //依次访问v的未被访问过的邻接点                      if (!visited[w]) {
                                   visited[w]=TRUE;  Q.append(w); // 访问邻接点w                           parentof[w]= v;                              // 记录顶点w的双亲结点为v                       }                     w=nextadj(G,v,w);                }          }          for (i=1; i<=n; i++)                 printpath(parentof, i);               // 输出v0到顶点i的最短路径   }

其中printpath算法描述如下:

void  printpath(int parentof[], int i){
         // 输出v0到顶点i的最短路径          if  (i!=0){
                 if (i== v0)  cout<< v0;              else {
    printpath(parentof, parentof[i]);                        cout<<””<

转载地址：http://vtten.baihongyu.com/