图的操作.txt

关于图的一些基本操作

              if (level==K+1){ printf("距顶点v0最短路径为k的顶点%d ",w); flag=1;}//if

              }//if

            w=GraphNextAdj(g ,v ,w);

           }//while(w!=0)

         if (f==t) {level++；t=r; }//当前层处理完，修改层数，t指向下一层最后一个顶点

        }//while(f<r && level<=K+1)

       if (flag==0) printf( "图中无距v0顶点最短路径为%d的顶点。\n",K);

}//算法结束。              

[设法讨论]本题亦可采取另一个算法。由于在生成树中结点的层数等于其双亲层次数加1，故可设顶点和层次数２个队列，其入队和出队操作同步，其核心语句段如下：

　　QueueInit(Q1) ; QueueInit(Q2); //Q1和Q2是顶点和顶点所在层次数的队列。

    visited[v0]=1;  //访问数组初始化，置v0被访问标记。

    level=1; flag=0; //是否有层次为K的顶点的标志

    QueueIn(Q1,v0); QueueIn(Q2,level); //顶点和层数入队列。

    while (!empty(Q1) && level<=K+1)

      {v=QueueOut(Q1); level=QueueOut(Q2);//顶点和层数出队。

       w=GraphFirstAdj(g,v0);

       while (w!=0)  //邻接点存在。

         {if (visited[w]==0)

            if (level==K+1)

              {printf("距离顶点v0最短路径长度为K的顶点是%d\n",w);

               visited[w]=1; flag=1; QueueIn(Q1 ,w); QueueIn(Q2,level+1); }//if

          w=GraphNextAdj(g ,v ,w);

         }//while(w!=0)  

 }//while(!empty(Q1) && level<K+1)

     if (flag==0) printf( "图中无距v0顶点最短路径为%d的顶点。\n",K);

36. 对于无环连通图，顶点间均有路径，树的直径是生成树上距根结点最远的两个叶子间的距离，利用深度优先遍历可求出图的直径。

    int dfs(Graph g ,vertype parent ,vertype child ,int len)

       //深度优先遍历，返回从根到结点child所在的子树的叶结点的最大距离。

     {current_len=len; maxlen=len;

      v=GraphFirstAdj(g ,child);

      while (v!=0) //邻接点存在。

        if (v!=parent)

          {len=len+length(g ,child ,c); dfs(g ,child ,v ,len);

           if (len>maxlen) maxlen=len;

           v=GraphNextAdj(g ,child ,v); len=current_len; } //if

       len=maxlen;

       return(len);

}//结束dfs。

  int  Find_Diamenter (Graph g)

        //求无向连通图的直径，图的顶点信息为图的编号。

      {maxlen1=0; maxlen2=0; //存放目前找到的根到叶结点路径的最大值和次大值。

       len=0;  ///深度优先生成树根到某叶结点间的距离

 w=GraphFirstAdj(g,1);   //顶点１为生成树的根。

        while (w!=0)  //邻接点存在。

          {len=length(g ,1 ,w);

           if (len>maxlen1) {maxlen2=maxlen1; maxlen1=len;}

           else if (len>maxlen2) maxlen2=len;

           w=GraphNextAdj(g ,1 ,w);//找顶点1的下一邻接点。

          }//while

        printf( "无向连通图g的最大直径是%d\n" ,maxlen1+maxlen2);

        return(maxlen1+maxlen2);

}//结束find_diamenter

    算法主要过程是对图进行深度优先遍历。若以邻接表为存储结构，则时间复杂度为O(n+e)。

37. [题目分析] 利用FLOYD算法求出每对顶点间的最短路径矩阵w，然后对矩阵w，求出每列j的最大值，得到顶点j的偏心度。然后在所有偏心度中，取最小偏心度的顶点v就是有向图的中心点。

  void  FLOYD_PXD(AdjMatrix g)

      //对以带权邻接矩阵表示的有向图g，求其中心点。

      {AdjMatrix w=g ;      //将带权邻接矩阵复制到w。

       for (k=1;k<=n;k++)    //求每对顶点间的最短路径。

         for (i=1;i<=n;i++)

           for (j=1;j<=n;j++)

             if ( w[i][j]>w[i][k]+w[k][j]) w[i][j]=w[i][k]+w[k][j];

        v=1;   dist=MAXINT;   //中心点初值顶点v为１，偏心度初值为机器最大数。

        for (j=1;j<=n;j++)

          {s=0;

           for (i=1;i<=n;i++) if (w[i][j]>s) s=w[i][j]; //求每列中的最大值为该顶点的偏心度。

           if (s<dist) {dist=s; v=j;}//各偏心度中最小值为中心点。

           }//for

        printf( "有向图g的中心点是顶点%d,偏心度%d\n",v,dist);

       }//算法结束

  38. 上面第35题是求无向连通图中距顶点v0的最短路径长度为k的所有结点，本题是求有向无环图中距每个顶点最长路径的长度，由于每条弧的长度是1，也需用宽度优先遍历实现，当队列为空前，最后一个结点的层次（减1）可作为从某顶点开始宽度优先遍历的最长路径长度。

  PROC  bfs_Longest ( g: Hnodes)

    //求以邻接表表示的有向无环图g的各个顶点的最长路径长度。有关变量已在高层定义。

    visited: ARRAY[1..n] OF integer; //访问数组。

Q: ARRAY[1..n] OF integer; //顶点队列。

    f,r,t,level：integer；     //f,r是队头队尾指针，t记为当前队尾，level层数。

    FOR i:=1 TO n DO           //循环，求从每个顶点出发的最长路径的长度

     [visited[1..n]:=0;  f:=0;  level:=0; //初始化。

visited[i]:=1; r:=r+1; Q[r]:=i; t:=r; level:=1; //从顶点i开始宽度优先遍历.

WHILE (f<r) DO

       [f:=f+1; v:=Q[f];   //队头元素出队。 

        p:=g[v].firstarc;

        WHILE (p<>NIL) DO

         [j:=p^adjvex; //邻接点。

          IF visited[j]=0 THEN [visited[j]:=1; r:=r+1; Q[r]:=j;]

          p=p^nextarc;

         ]//WHILE(p<>NIL)

        IF f=t THEN [level:=level+1; t:=r; ]//t指向下层最后一个顶点。

]//WHILE (f<r)

      g[i].mpl:=level-1; //将顶点i的最长路径长度存入mpl域

     ]//FOR

   EDNP;

39. [题目分析] 按Dijkstra路径增序求出源点和各顶点间的最短路径，上面31题已有解答。本题是求出最小生成树，即以源点为根，其路径权值之和最小的生成树。在确定顶点的最短路径时，总是知道其（弧出自的）前驱（双亲）顶点，我们可用向量p[1..n]记录各顶点的双亲信息，源点为根，无双亲，向量中元素值用-1表示。

    void Shortest_PTree ( AdjMatrix G, vertype v0)

       //利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G的最小生成树

      {int d[] ,s[] ; //d数组存放各顶点最短路径，s数组存放顶点是否找到最短路径。

       int p[] ;      //p数组存放顶点在生成树中双亲结点的信息。

       for (i=1;i<=n;i++)

         {d[i]=G[v0][i]; s[i]=0;

          if (d[i]<MAXINT) p[i]=v0;  //MAXINT是机器最大数，v0是i的前驱（双亲）。

          else p[i]=-1; }//for       //i目前无前驱，p数组各量初始化为-1。

       s[v0]=1; d[v0]=0; p[v0]=-1;    //从v0开始，求其最小生成树。

       for (i=1;i<n;i++)

         {mindis=MAXINT;

          for (j=1;j<=n;j++)

            if (s[j]==0 && d[j]<mindis) { u=j; mindis=d[j];}

          s[u]=1;   //顶点u已找到最短路径。

          for (j=1;j<=n;j++)   //修改j的最短路径及双亲。

            if (s[j]==0 && d[j]>d[u]+G[u][j]) {d[j]=d[u]+G[u][j]; p[j]=u;} 

         }//for (i=1;i<=n;i++)

         for (i=1;i<=n;i++) //输出最短路径及其长度，路径是逆序输出。

           if (i!=v0)

             {pre=p[i]; printf( "\n最短路径长度＝%d，路径是：%d，",d[i],i);

              while (pre!=-1) { printf( ",%d",pre); pre=p[pre];} //一直回溯到根结点。

             }//if

        }//算法结束

40. [题目分析] 由关节点定义及特性可知，若生成树的根有多于或等于两棵子树，则根结点是关节点；若生成树某非叶子顶点v，其子树中的结点没有指向v的祖先的回边，则v是关节点。因此，对图G＝(v,{Edge})，将访问函数visited[v]定义为深度优先遍历连通图时访问顶点v的次序号，并定义一个low( )函数：

low(v)＝Min(visited[v],low[w],visited[k])

其中(v,w)∈Edge，(v,k)∈Edge，w是v在深度优先生成树上的孩子结点，k是v在深度优先生成树上的祖先结点。在如上定义下，若low[w]>=visited[v]，则v是根结点，因w及其子孙无指向v的祖先的回边。由此，一次深度优先遍历连通图，就可求得所有关节点。

  int  visited[] ,low[]; //访问函数visited和low函数为全局变量。

  int  count;            //记访问顶点个数。

  AdjList g;            //图g以邻接表方式存储

  void dfs_articul(vertype v0)

      //深度优先遍历求关节点。

   {count++; visited[v0]=count; //访问顶点顺序号放入visited

    min=visited[v0];  //初始化访问初值。

    p=g[v0].firstarc; //求顶点v的邻接点。

    while (p!=null)

      {w=p->adjvex; //顶点v的邻接点。

       if (visited[w]==0) //w未曾访问，w是v0的孩子。

         {dfs_articul(g ,w);

          if (low[w]<min) min =low[w];

          if (low[w]>=visited[v0]) printf(g[v0].vertex); //v0是关节点。

          }//if

       else //w已被访问，是v的祖先。

         if (visited[w]<min) min=visited[w];

       p=p->next;

      }//while

     low[v0]=min;

}//结束dfs_articul

  void  get_articul( )

      //求以邻接表为存储结构的无向连通图g的关节点。

    {for (vi=1;vi<=n;vi++) visited[vi]=0; //图有n个顶点，访问数组初始化。

     count=1; visited[1]=1;               //设邻接表上第一个顶点是生成树的根。

     p=g[1].firstarc;  v=p->adjvex; 

     dfs_articul(v);

     if (count<n) //生成树的根有两棵以上子树。

       {printf(g[1].vertex);//根是关节点

        while(p->next!=null)

          {p=p->next; v=p->adjvex; if(visited[v]==0) dfs-articul(v);

          }//while

}//if  }//结束get-articul

41. [题目分析] 对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历，在dfs(v)结束之前，出现从顶点u到顶点v的回边，图中必存在环。这里设定visited访问数组和finished数组为全局变量，若finished[i]=1,表示顶点i的邻接点已搜索完毕。由于dfs产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变量final，在dfs函数退出时，把顶点v插入到final所指的链表中，链表中的结点就是一个正常的拓扑序列。邻接表的定义与本书相同，这里只写出拓扑排序算法。

    int visited[]=0; finished[]=0; flag=1;   //flag测试拓扑排序是否成功

    ArcNode  *final=null;    //final是指向顶点链表的指针，初始化为0

    void  dfs(AdjList g,vertype v)

       //以顶点v开始深度优先遍历有向图g，顶点信息就是顶点编号.

      {ArcNode *t;  //指向边结点的临时变量

       printf("%d",v); visited[v]=1; p=g[v].firstarc;

       while(p!=null)

         {j=p->adjvex;

          if (visited[j]==1 && finished[j]==0) flag=0 //dfs结束前出现回边

            else if(visited[j]==0) {dfs(g,j); finished[j]=1;} //if

          p=p->next;

         }//while

t=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点

       t->adjvex=v; t->next=final; final=t;    //将该顶点插入链表

      } //dfs结束

    int dfs-Topsort(Adjlist g)

      //对以邻接表为存储结构的有向图进行拓扑排序，拓扑排序成功返回1，否则返回0

      {i=1;

       while (flag && i <=n)

         if (visited[i]==0) {dfs(g,i);  finished[i]=1; }//if

       return(flag);  

}// dfs-Topsort

42. [题目分析] 地图涂色问题可以用“四染色“定理。将地图上的国家编号（1到n），从编号1开始逐一涂色，对每个区域用1色，2色，3色，4色（下称“色数”）依次试探，若当前所取颜色与周围已涂色区域不重色，则将该区域颜色进栈；否则，用下一颜色。若1至4色均与相邻某区域重色，则需退栈回溯,修改栈顶区域的颜色。用邻接矩阵数据结构C[n][n]描叙地图上国家间的关系。n个国家用n阶方阵表示，若第i个国家与第j个国家相邻，则Cij=1，否则Cij=0。用栈s记录染色结果，栈的下标值为区域号，元素值是色数。

void  MapColor(AdjMatrix  C)

        //以邻接矩阵C表示的n个国家的地区涂色

      {int s[];   //栈的下标是国家编号，内容是色数

       s[1]=1；   //编号01的国家涂1色

       i=2;j=1;   //i为国家号，j为涂色号

       while (i<=n)

         {while (j<=4 && i<=n)

            {k=1;  //k指已涂色区域号

             while (k<i && s[k]*C[i][k]!=j) k++;  //判相邻区是否已涂色

             if (k<i) j=j+1;      //用j+1色继续试探

             else {s[i]=j;i++;j=1;}//与相邻区不重色，涂色结果进栈，继续对下一区涂色进行试探

            }

          }//while (j<=4 && i<=n)

       if (j>4) {i--; j=s[i]+1;}  //变更栈顶区域的颜色。

      }//while   }//结束MapColor