图的操作.txt

关于图的一些基本操作

         p=p->next; //下一个邻接点。

        }//while

       visited[v0]=0; num--; //取消访问标记，使该顶点可重新使用。

      }//SPathdfs

26.　与上题类似，这里给出非递归算法，顶点信息仍是编号。

  　void AllSPdfs(AdjList g,vertype u,vertype v)

      //求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v)

      { int top=0,s[];

        s[++top]=u; visited[u]=1;

        while (top>0 || p)

             {p=g[s[top]].firstarc;  //第一个邻接点。

              while (p!=null && visited[p->adjvex]==1) p=p->next; //下一个访问邻接点表。

               if (p==null) top--; //退栈。

               else { i=p->adjvex; //取邻接点（编号）。

                      if (i==v) //找到从u到v的一条简单路径，输出。

                        {for (k=1;k<=top;k++) printf( "%3d",s[k]); printf( "%3d\n",v);}//if

                      else { visited[i]=1; s[++top]=i; } //else深度优先遍历。

                    }//else  }//while

          }// AllSPdfs

类似本题的另外叙述的第（2）题 ：u到v有三条简单路径：uabfv，ucdv，ucdefv。

27. （1）[题目分析]D_搜索类似BFS，只是用栈代替队列，入出队列改为入出栈。查某顶点的邻接点时，若其邻接点尚未遍历，则遍历之，并将其压入栈中。当一个顶点的所有邻接点被搜索后，栈顶顶点是下一个搜索出发点。

  void D_BFS(AdjList g ,vertype v0) 

      // 从v0顶点开始，对以邻接表为存储结构的图g进行D_搜索。

      { int s[], top=0;     //栈，栈中元素为顶点，仍假定顶点用编号表示。

        for (i=1,i<=n;i++) visited[i]=0;  //图有n个顶点，visited数组为全局变量。

        for (i=1,i<=n;i++)  //对n个顶点的图g进行D_搜索。

          if (visited[i]==0)

            {s[++top]=i; visited[i]=1; printf( "%3d",i);

             while (top>0)

                {i=s[top--]; //退栈

                 p=g[i].firstarc; //取第一个邻接点

                 while (p!=null)  //处理顶点的所有邻接点

                   {j=p->adjvex; 

if (visited[j]==0) //未访问的邻接点访问并入栈。

{visited[j]=1; printf( "%3d",i);s[++top]=j;} 

5
 
1
 
3
 
2
 
4
 
 
7
 
p=p->next; 

} //下一个邻接点

}//while(top>0)

               } //if

         }//D_BFS

（2）D_搜索序列：1234675，生成树如图：

 

28，[题目分析] 本题的含义是对有向无环图(DAG)的顶点，以整数适当编号后，可使其邻接矩阵中对角线以下元素全部为零。根据这一要求，可以按各顶点出度大小排序，使出度最大的顶点编号为1，出度次大者编号为2，出度为零的顶点编号为n。这样编号后，可能出现顶点编号i<j，但却有一条从顶点到j到i的弧。这时应进行调整，即检查每一条弧，若有<i,j>，且i>j，则使顶点j的编号在顶点i的编号之前。

    void Adjust(AdjMatrix g1 ,AdjMatrix g2)

      //对以邻接矩阵存储的DAG图g1重新编号，使若有<i,j>，则编号i<j，重新编号后的图以邻接矩阵g2存储。

    {typedef struct { int vertex ,out ,count }node ; //结点结构：顶点，出度，计数。

     node v[];   //顶点元素数组。

     int c[];    //中间变量

     for (i=1;i<=n;i++)    //顶点信息数组初始化，设图有n个顶点。

        {v[i].vertex=i; v[i].out=0; v[i].count=1; c[i]=1;}   //count=1为最小

     for (i=1;i<=n;i++)    //计算每个顶点的出度。

        for (j=1;j<=n;j++) v[i].out+=g1[i][j]; 

     for (i=n;i>=2;i--)    //对v的出度域进行计数排序，出度大者，count域中值小。

        for (j=i-1;j>=1;j--)   

           if (v[i].count<=v[j].count) v[i].count++; else v[j].count++;

     for (i=1;i<=n;i++) //第二次调整编号。若<i,j>且i>j，则顶点j的编号在顶点i的编号之前

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

           if(g1[i][j]==1 && v[i].count>v[j].count) {v[i].count=v[j].count;v[j].count++;}

     for (i=n;i>=2;i--)) //对v的计数域v[i].count排序，按count域从小到大顺序存到数组c中。

        for (j=i-1;j>=1;j--)   

           if (v[i].count<v[j].count) c[j]++; else c[i]++;

     for (i=1;i<=n;i++)  v[i].count=c[i]; //将最终编号存入count 域中。

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

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

           g2[v[i].count][v[j].count]=g1[v[i].vertex][v[j].vertex];

   }//算法结束

29. 

 

非二部图
 
二部图
 

[题目分析] 将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。

    int BPGraph (AdjMatrix g)

         //判断以邻接矩阵表示的图g是否是二部图。

       {int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合）

        int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。

        int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组

        for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合

        Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1

while(f<r)

 {v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号

  if (!visited[v])

   {visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中

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

    if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;}  //邻接点入队列

                   else if (s[j]==s[v]) return(0);} //非二部图

 }//if (!visited[v])

}//while 

return(1); }//是二部图

[算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。

30. [题目分析] 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。

  void  SpnTree (AdjList g) 

     //用“破圈法”求解带权连通无向图的一棵最小代价生成树。

{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数

 node edge[];

      scanf( "%d%d",&e,&n) ; //输入边数和顶点数。

      for (i=1;i<=e;i++)     //输入e条边：顶点，权值。

         scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);

       for (i=2;i<=e;i++)    //按边上的权值大小，对边进行逆序排序。

       {edge[0]=edge[i]; j=i-1;

while (edge[j].w<edge[0].w)  edge[j+1]=edge[j--];

edge[j+1]=edge[0]; }//for

       k=1;  eg=e;

       while (eg>=n)       //破圈，直到边数e=n-1.

         {if (connect(k))  //删除第k条边若仍连通。

            {edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除

k++;  //下条边

         }//while 

}//算法结束。

　    connect()是测试图是否连通的函数，可用图的遍历实现，若是连通图，一次进入dfs或bfs就可遍历完全部结点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。前面第17,18题就是测连通分量个数的算法，请参考。“破圈”结束后，可输出edge中w不为０的n-1条边。限于篇幅，这些算法不再写出。

31. [题目分析]求单源点最短路径问题，存储结构用邻接表表示，这里先给出所用的邻接表中的边结点的定义： struct node {int adjvex,weight; struct node *next;}p;

void  Shortest_Dijkstra(AdjList cost ,vertype v0)

     //在带权邻接表cost中，用Dijkstra方法求从顶点v0到其它顶点的最短路径。

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

       for (i=1;i<=n;i++) {dist[i]=INFINITY; s[i]=0; } //初始化，INFINITY是机器中最大的数

       s[v0]=1;

       p=g[v0].firstarc;

       while(p)  //顶点的最短路径赋初值 

          {dist[p->adjvex]=p->weight; p=p->next;}

       for (i=1;i<n;i++) //在尚未确定最短路径的顶点集中选有最短路径的顶点u。

         {mindis=INFINITY; //INFINITY是机器中最大的数，代表无穷大

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

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

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

          p=g[u].firstarc;

          while(p)  //修改从v0到其它顶点的最短路径

          {j=p->adjvex;

           if (s[j]==0 && dist[j]>dist[u]+p->weight) dist[j]=dist[u]+p->weight;

           p=p->next;

          }

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

      }//Shortest_Dijkstra

32.   本题用FLOYD算法直接求解如下：

     void ShortPath_FLOYD(AdjMatrix g)

        //求具有n个顶点的有向图每对顶点间的最短路径

     {AdjMatrix length; //length[i][j]存放顶点vi到vj的最短路径长度。

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

         for (j=1;j<=n;j++) length[i][j]=g[i][j]; //初始化。

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

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

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

               if (length[i][k]+length[k][j]<length[i][j])

                   length[i][j]=length[i][k]+length[k][j];

        }//算法结束

33. [题目分析] 该题可用求每对顶点间最短路径的FLOYD算法求解。求出每一顶点（村庄）到其它顶点（村庄）的最短路径。在每个顶点到其它顶点的最短路径中，选出最长的一条。因为有n个顶点，所以有n条, 在这n条最长路径中找出最短一条，它的出发点（村庄）就是医院应建立的村庄。

   void  Hospital(AdjMatrix w,int n)

    //在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。

    {for (k=1;k<=n;k++)   //求任意两顶点间的最短路径

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

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

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

     m=MAXINT;             //设定m为机器内最大整数。

     for (i=1;i<=n;i++)    //求最长路径中最短的一条。

       {s=0;

        for (j=1;j<=n;j++) //求从某村庄i（1<=i<=n）到其它村庄的最长路径。

          if (w[i][j]>s) s=w[i][j];

        if (s<=m) {m=s; k=i;}//在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。

        Printf(“医院应建在%d村庄，到医院距离为%d\n”,i,m);

        }//for

}//算法结束

对以上实例模拟的过程略。在A(6)矩阵中（见下图），各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。

34. （１）该有向图的强连通分量有两个：一个是顶点a,另一个由b,c,e,d四个顶点组成。

（２）因篇幅有限从略，请参见本章四？

（３）用FLOYD算法求每对顶点间最短距离，其５阶方阵的初态和终态如下：

A(0)= A(5)= 第33题结果矩阵A(6)= 
    由于要求各村离医院较近（不是上题中“离医院最远的村庄到医院的路径最短”），因此算法中求出矩阵终态后，将各列值相加，取最小的一个，该列所在村庄即为所求（本题答案是医院建在b村，各村到医院距离和是11），下面是求出各顶点间最短的路径后，求医院所在位置的语句段：

  min=MAXINT ; //设定机器最大数作村庄间距离之和的初值。

  k=1; //k设医院位置。

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

    {m=0 ;

     for (i=1;i<=n;i++) m=m+w[i][j];

     if (min>m) { min=m ;k=j;}     //取顶点间的距离之和的最小值。

    }//for

35. [题目分析] 本题应用宽度优先遍历求解。若以v0作生成树的根为第１层，则距顶点v0最短路径长度为K的顶点均在第K+1层。可用队列存放顶点，将遍历访问顶点的操作改为入队操作。队列中设头尾指针f和r，用level表示层数。

    void bfs_K ( graph g ,int v0 ,K)

      //输出无向连通图g（未指定存储结构）中距顶点v0最短路径长度为K的顶点。

     {int Q[]; //Q为顶点队列，容量足够大。

      int f=0,r=0,t=0; //f和r分别为队头和队尾指针，t指向当前层最后顶点。

      int level=0,flag=0;  //层数和访问成功标记。

      visited[v0]=1; //设v0为根。

      Q[++r]=v0; t=r; level=1; //v0入队。

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

        {v=Q[++f];

         w=GraphFirstAdj(g,v);

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

           {if (visited[w]==0)

             {Q[++r]=w; visited[w]=1;//邻接点入队列。