五.算法設計題

1.     void CreatGraph (AdjList g)

//建立有n個頂點和m 條邊的無向圖的鄰接表存儲結構

{int n,m;

   scanf("%d%d",&n,&m);

for (i =1,i<=n;i++)//輸入頂點信息,建立頂點向量

{scanf(&g[i].vertex);  g[i].firstarc=null;}

for (k=1;k<=m;k++)//輸入邊信息

{scanf(&v1,&v2);//輸入兩個頂點

i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2); //頂點定位

p=(ArcNode *)malloc(sizeof(ArcNode));//申請邊結點

p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;//將邊結點鏈入

  p=(ArcNode *)malloc(sizeof(ArcNode));

p->adjvex=i; p->next=g[j].firstarc;  g[j].frstarc=p;

}

}//算法CreatGraph結束

2.     void CreatAdjList(AdjList g)

//建立有向圖的鄰接表存儲結構

{int n;

scanf("%d",&n);

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

{scanf(&g[i].vertex); g[i].firstarc=null;}//輸入頂點信息

scanf(&v1,.&v2);

    while(v1 && v2)//題目要求兩頂點之一為0表示結束

     {i=GraphLocateVertex(g2,v1);

      p=(ArcNode*)malloc(sizeof(ArcNode));

      p->adjvex=j;  p->next=g[i].firstarc;  g[i].firstarc=p;

scanf(&v1,&v2);

} }

3.     void CreatMGraph(AdjMulist g)

//建立有n個頂點e條邊的無向圖的鄰接多重表的存儲結構

{int n,e;

scanf("%d%d",&n,&e);

     for(i=1,i<=n;i++)    //建立頂點向量

      { scanf(&g[i].vertex);  g[i].firstedge=null;}

     for(k=1;k<=e;k++)    //建立邊結點

      {scanf(&v1,&v2);

       i=GraphLocateVertex(g,v1); j=GraphLocateVertex(g,v2);

p=(ENode *)malloc(sizeof(ENode));

p->ivex=i; p->jvex=j; p->ilink=g[i].firstedge; p->jlink=g[j].firstedge;

g[i].firstedge=p; g[j].firstedge=p;

}

}//算法結束

4.     void CreatOrthList(OrthList g)

//建立有向圖的十字鏈表存儲結構

{int i,j,v; //假定權值為整型

scanf("%d",&n);

  for(i=1,i<=n;i++)    //建立頂點向量

    { scanf(&g[i].vertex);    g[i].firstin=null; g[i].firstout=null;}

      scanf("%d%d%d",&i,&j,&v);

      while (i && j && v)       //當輸入i,j,v之一為0時,結束算法運行

      {p=(OrArcNode *)malloc(sizeof(OrArcNode)); //申請結點

       p->headvex=j;    p->tailvex=i;   p->weight=v;  //弧結點中權值域

       p->headlink=g[j].firstin; g[j].firstin=p;

       p->tailink=g[i].firstout; g[i].firstout=p;

scanf("%d%d%d",&i,&j,&v);

      } }算法結束

[算法討論]  本題已假定輸入的i和j是頂點號,否則,頂點的信息要輸入,且用頂點定位函數求出頂點在頂點向量中的下標。圖建立時，若已知邊數（如上面1和2題），可以用for循環；若不知邊數，可用while循環（如本題），規定輸入特殊數（如本題的零值）時結束運行。本題中數值設為整型，否則應以和數值類型相容的方式輸入。

5．void InvertAdjList(AdjList gin,gout）

//將有向圖的出度鄰接表改為按入度建立的逆鄰接表

    {for (i=1;i<=n;i++)//設有向圖有n個頂點，建逆鄰接表的頂點向量。

      {gin[i].vertex=gout[i].vertex; gin.firstarc=null; }

     for (i=1;i<=n;i++)   //鄰接表轉為逆鄰接表。

      {p=gout[i].firstarc;//取指向鄰接表的指針。

       while (p!=null)

            { j=p->adjvex;

              s=(ArcNode *)malloc(sizeof(ArcNode));//申請結點空間。

              s->adjvex=i; s->next=gin[j].firstarc; gin[j].firstarc=s;

              p=p->next;//下一個鄰接點。

            }//while

     }//for   }

6. void  AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)

//將圖的鄰接表表示轉換為鄰接矩陣表示。

{for (i=1;i<=n;i++)  //設圖有n個頂點，鄰接矩陣初始化。

       for (j=1;j<=n;j++) gm[i][j]=0;

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

      {p=gl[i].firstarc;  //取第一個鄰接點。

       while (p!=null) {gm[i][p->adjvex]=1;p=p->next; }//下一個鄰接點

       }//for  }//算法結束

7. void  AdjMatrixToAdjList( AdjMatrix gm, AdjList gl )

//將圖的鄰接矩陣表示法轉換為鄰接表表示法。

{for (i=1;i<=n;i++)   //鄰接表表頭向量初始化。

      {scanf(&gl[i].vertex); gl[i].firstarc=null;}

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

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

          if (gm[i][j]==1)

             {p=(ArcNode *)malloc(sizeof(ArcNode)) ;//申請結點空間。

p->adjvex=j;//頂點I的鄰接點是j

p->next=gl[i].firstarc; gl[i].firstarc=p; //鏈入頂點i的鄰接點鏈表中

}

 }//end

[算法討論] 算法中鄰接表中頂點在向量表中的下標與其在鄰接矩陣中的行號相同。

8.[題目分析] 在有向圖中，判斷頂點Vi和頂點Vj間是否有路徑，可采用遍歷的方法，從頂點Vi出發，不論是深度優先遍歷（dfs）還是寬度優先遍歷（bfs），在未退出dfs或bfs前,若訪問到Vj，則說明有通路，否則無通路。設一全程變量flag。初始化為0，若有通路，則flag=1。

算法1：int visited[]=0;  //全局變量，訪問數組初始化

int  dfs(AdjList g , vi)

    //以鄰接表為存儲結構的有向圖g，判斷頂點Vi到Vj是否有通路,返回1或0表示有或無

 { visited[vi]=1;   //visited是訪問數組，設頂點的信息就是頂點編號。

    p=g[vi].firstarc;  //第一個鄰接點。

    while ( p!=null)

       { j=p->adjvex;

        if (vj==j) { flag=1; return（1）;} //vi 和 vj 有通路。

        if (visited[j]==0) dfs(g,j);

        p=p->next； }//while 

     if (!flag) return(0);

  }//結束

[算法討論] 若頂點vi和vj 不是編號，必須先用頂點定位函數,查出其在鄰接表頂點向量中的下標i和j。下面算法2輸出vi 到 vj的路徑，其思想是用一個棧存放遍歷的頂點，遇到頂點vj時輸出路徑。

算法2：void dfs(AdjList g , int i)

  //有向圖g的頂點vi（編號i）和頂點vj（編號j）間是否有路徑，如有，則輸出。

   {int top=0,stack[]; //stack是存放頂點編號的棧

    visited[i]=1;      //visited 數組在進入dfs前已初始化。

    stack[++top]=i;

    p=g[i].firstarc; /求第一個鄰接點.

    while (p)

      {if (p->adjvex==j)

              {stack[++top]=j; printf( "頂點 vi 和 vj 的路徑為：\n");

               for (i=1; i<=top; i++)  printf( "%4d",stack[i]); exit(0);

 }//if

            else if (visited[p->adjvex]==0) {dfs(g,g->adjvex); top--; p=p->next;}//else if

           }//while

    }//結束算法2

算法3：本題用非遞歸算法求解。

  int  Connectij (AdjList g , vertype vi , vj )

 //判斷n個頂點以鄰接表表示的有向圖g中，頂點 Vi 各Vj 是否有路徑，有則返回1，否則返回0。

{ for (i=1;i<=n;i++)  visited[i]=0; //訪問標記數組初始化。

  i=GraphLocateVertex(g,vi); //頂點定位，不考慮 vi或 vj不在圖中的情況。

  j=GraphLocateVertex(g,vj);

  int stack[],top=0;stack[++top]=i;

  while(top>0)

{k=stack[top--]; p=g[k].firstarc;

while(p!=null && visited[p->adjvex]==1) p=p->next; //查第k個鏈表中第一個未訪問的弧結點。

 if(p==null) top--;

 else {i=p->adjvex;

if(i==j) return(1); //頂點vi和vj 間有路徑。

else {visited[i]=1; stack[++top]=i;}//else

}//else

    }while

return(0); } //頂點vi和vj 間無通路。

9. void DeletEdge(AdjList g,int i,j)

     //在用鄰接表方式存儲的無向圖g中，刪除邊(i,j)

{p=g[i].firstarc;  pre=null; //刪頂點i 的邊結點(i,j),pre是前驅指針

while (p)

     if (p->adjvex==j)

       {if(pre==null)g[i].firstarc=p->next;else pre->next=p->next;free(p);}//釋放結點空間。

     else {pre=p; p=p->next;}   //沿鏈表繼續查找

p=g[j].firstarc;  pre=null; //刪頂點j 的邊結點(j,i)

while (p)

     if (p->adjvex==i)

       {if(pre==null)g[j].firstarc=p->next;else pre->next=p->next;free(p);}//釋放結點空間。

     else {pre=p; p=p->next;}   //沿鏈表繼續查找

   }// DeletEdge

[算法討論] 算法中假定給的i，j 均存在，否則應檢查其合法性。若未給頂點編號，而給出頂點信息，則先用頂點定位函數求出其在鄰接表頂點向量中的下標i和j。

10. void  DeleteArc（AdjList g,vertype vi,vj）

   //刪除以鄰接表存儲的有向圖g的一條弧<vi,vj>，假定頂點vi和vj存在

{i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); //頂點定位

   p=g[i].firstarc;  pre=null;

while (p)

    if (p->adjvex==j)

      {if(pre==null) g[i].firstarc=p->next;else pre->next=p->next;free(p);}//釋放結點空間。

    else  { pre=p; p=p->next;}

}//結束

11. void InsertArc ( OrthList g ,vertype vi,vj)

//在以十字鏈表示的有向圖g中插入弧<vi,vj>

{ i=GraphLocateVertex(g,vi); //頂點定位.

  j=GraphLocateVertex(g,vj);

p=(OrArcNode *)malloc(sizeof(OrArcNode));

p=headvex=j; p=tailvex=i;  //填寫弧結點信息并插入十字鏈表。

p->headlink=g[j].firstin; g[j].firstin=p;

p->taillink=g[i].firstout; g[i].firstout=p;

}//算法結束

12. [題目分析]在有向圖的鄰接表中，求頂點的出度容易，只要簡單在該頂點的鄰接點鏈表中查結點個數即可。而求頂點的入度，則要遍歷整個鄰接表。

 int count (AdjList g , int k )

//在n個頂點以鄰接表表示的有向圖g中，求指定頂點k(1<=k<=n)的入度。

{ int count =0;

 for (i=1;i<=n;i++)   //求頂點k的入度要遍歷整個鄰接表。

 if(i!=k)           //頂點k的鄰接鏈表不必計算

{p=g[i].firstarc;//取頂點 i 的鄰接表。

 while (p)

    {if (p->adjvex==k) count++;

     p=p->next;

}//while

}//if

  return(count); //頂點k的入度.

}

13. [題目分析]有向圖判斷回路要比無向圖復雜。利用深度優先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未訪問完;已訪問且其鄰接點已訪問完。下面用0，1，2表示這三種狀態。前面已提到，若dfs（v）結束前出現頂點u到v的回邊，則圖中必有包含頂點v和u的回路。對應程序中v的狀態為1，而u是正訪問的頂點，若我們找出u的下一鄰接點的狀態為1，就可以輸出回路了。

void  Print(int v,int start )  //輸出從頂點start開始的回路。

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

    if(g[v][i]!=0 && visited[i]==1 )  //若存在邊（v,i），且頂點i的狀態為1。

      {printf(“%d”,v); if(i==start) printf(“\n”); else Print(i,start);break;}//if

    }//Print

void dfs(int v)

   {visited[v]=1;

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