第7章圖答案(編輯修改稿)

　

【文章內容簡介】 adjvex=i。 snext=gin[j].firstarc。 gin[j].firstarc=s。 p=pnext。//下一個鄰接點。 }//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][padjvex]=1。p=pnext。 }//下一個鄰接點 }//for }//算法結束 7. void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl ) //將圖的鄰接矩陣表示法轉換為鄰接表表示法。 {for (i=1。i=n。i++) //鄰接表表頭向量初始化。 {scanf(amp。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)) 。//申請結點空間。 padjvex=j。//頂點 I的鄰接點是 j pnext=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=padjvex。 if (vj==j) { flag=1。 return（ 1） 。} //vi 和 vj 有通路。 if (visited[j]==0) dfs(g,j)。 p=pnext； }//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 (padjvex==j) {stack[++top]=j。 printf( 頂點 vi 和 vj 的路徑為： \n)。 for (i=1。 i=top。 i++) printf( %4d,stack[i])。 exit(0)。 }//if else if (visited[padjvex]==0) {dfs(g,gadjvex)。 top。 p=pnext。}//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(top0) {k=stack[top]。 p=g[k].firstarc。 while(p!=null amp。amp。 visited[padjvex]==1) p=pnext。 //查第 k個鏈表中第一個未訪問的弧結點。 if(p==null) top。 else {i=padjvex。 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 (padjvex==j) {if(pre==null)g[i].firstarc=pnext。else prenext=pnext。free(p)。}//釋放結點空間。 else {pre=p。 p=pnext。} //沿鏈表繼續查找 p=g[j].firstarc。 pre=null。 //刪頂點 j 的邊結點 (j,i) while (p) if (padjvex==i) {if(pre==null)g[j].firstarc=pnext。else prenext=pnext。free(p)。}//釋放結點空間。 else {pre=p。 p=pnext。} //沿鏈表繼續查找 }// 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 (padjvex==j) {if(pre==null) g[i].firstarc=pnext。else prenext=pnext。free(p)。}//釋放結 點空間。 else { pre=p。 p=pnext。} }//結束 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。 //填寫弧 結點信息并插入十字鏈表。 pheadlink=g[j].firstin。 g[j].firstin=p。 ptaillink=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 (padjvex==k) count++。 p=pnext。 }//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 amp。amp。 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++ ) if (g[v][j]!=0) //存在邊 (v,j) if (visited[j]!=1) {if (!visited[j]) dfs(j)。 }//if else {cycle=1。 Print(j,j)。} visited[v]=2。 }//dfs void find_cycle() //判斷是否有回路，有則輸出鄰接矩陣。 visited數組為全局變量。 {for (i=1。i=n。i++) visited[i]=0。 for (i=1。i=n。i++ ) if (!visited[i]) dfs(i)。 }//find_cycle 14． [題目分析 ]有幾種方法判斷有向圖是否存在環路，這里使用拓撲排序法。對 有向圖的頂點進行拓撲排序，若拓撲排序成功，則無環路；否則，存在環路。題目已假定有向圖用十字鏈表存儲，為方便運算，在頂點結點中，再增加一個入度域 indegree，存放頂點的入度。入度為零的頂點先輸出。為節省空間，入度域還起棧的作用。值得注意的是，在鄰接表中，頂點的鄰接點非常清楚，頂點的單鏈表中的鄰接點域都是頂點的鄰接點。由于十字鏈表邊（弧）結點個數與邊（弧）個數相同（不象無向圖邊結點個數是邊的二倍），因此，對某頂點 v, 要判斷其鄰接點是 headvex還是 tailvex。 int Topsor(OrthList g) //判斷以十字鏈表為存儲結構的有向圖 g是否存在環路，如是，返回 1，否則，返回0。 {int top=0。 //用作棧頂指針 for (i=1。i=n。i++) //求各頂點的入度。設有向圖 g有 n個頂點，初始時入度域均為 0 {p=g[i].firstin。 //設頂點信息就是頂點編號，否則，要進行頂點定位 while(p) {g[i].indegree++。 //入度域增 1 if (p