【導(dǎo)讀】部分答案解釋如下。48．按著定義，AOE網(wǎng)中關(guān)鍵路徑是從“源點(diǎn)”到“匯點(diǎn)”路徑長(zhǎng)度最長(zhǎng)的路徑。鍵路徑上活動(dòng)的時(shí)間延長(zhǎng)多少，整個(gè)工程的時(shí)間也就隨之延長(zhǎng)多少。本題按鄰接表存儲(chǔ)結(jié)構(gòu)，鄰接點(diǎn)按字典序排列。結(jié)果是不唯一的。本答案是按鄰接點(diǎn)升序排列給出的。結(jié)點(diǎn)多了一條通路，即形成回路。從某頂點(diǎn)發(fā)出并回到自身頂點(diǎn)的弧，所以鄰接矩陣主對(duì)角元素均為0。先證明該命題的充分。由于弧尾頂點(diǎn)的編號(hào)均大于弧頭頂點(diǎn)的編號(hào)，在鄰接矩陣中，非零元素。使用深度優(yōu)先遍歷，按退出dfs過(guò)程的先后順序記錄下的頂點(diǎn)是逆向拓?fù)溆行蛐蛄?。若在?zhí)行dfs未退出前，出現(xiàn)頂點(diǎn)u到v的回邊，則說(shuō)明存在包含頂點(diǎn)v和頂點(diǎn)u的環(huán)。度為0）K6，K7。規(guī)則：開(kāi)始結(jié)點(diǎn)為K1或K2，之后，若遇多個(gè)入度為0的頂點(diǎn)，按頂點(diǎn)編號(hào)順序選擇。

　　

【正文】 [v0]=1。 //設(shè)頂點(diǎn)信息就是編號(hào)， visited是全局變量。 initqueue(Q)。 enqueue(Q,v0)。 //v0入隊(duì)列。 while (!empty(Q)) {v=delqueue(Q)。 //隊(duì)頭元素出隊(duì)列。 w=firstadj(g ,v)。 //求頂點(diǎn) v的第一鄰接點(diǎn) while (w!=0) //w!=0表示 w存在。 {if (visited[w]==0) //若鄰接點(diǎn)未訪問(wèn)。 {visit(w)。 visited[w]=1。 enqueue(Q,w)。}//if w=nextadj(g,v,w)。 //求下一個(gè)鄰接點(diǎn)。 }//while }//while }//bfs void Traver() //對(duì)圖 g進(jìn)行寬度優(yōu)先遍歷，圖 g是全局變量。 {for (i=1。i=n。i++) visited[i]=0。 for (i=1。i=n。i++) if (visited[i]==0) bfs(i)。 } //Traver 25.[題目分析 ] 本題應(yīng)使用深度優(yōu)先遍歷。設(shè)圖的頂點(diǎn)信息就是頂點(diǎn)編號(hào)，用 num記錄訪問(wèn)頂點(diǎn)個(gè)數(shù)，當(dāng) num等于圖的頂點(diǎn)個(gè)數(shù)（題中的 NODES(G)），輸出所訪 問(wèn)的頂點(diǎn)序列，頂點(diǎn)序列存在 path中， path和 visited數(shù)組，頂點(diǎn)計(jì)數(shù)器 num，均是全局變量，都已初始化。 void SPathdfs(v0) //判斷無(wú)向圖Ｇ中是否存在以 v0 為起點(diǎn)，包含圖中全部頂點(diǎn)的簡(jiǎn)單路徑。 {visited[v0]=1。 path[++num]=v0。 if (num==nodes(G) //有一條簡(jiǎn)單路徑，輸出之。 {for (i=1。i=num。i++) printf( %3d,path[i])。 printf( \n)。 exit(0)。} //if p=g[v0].firstarc。 while (p) {if (visited[padjvex]==0) SPathdfs(padjvex)。 //深度優(yōu)先遍歷。 p=pnext。 //下一個(gè)鄰接點(diǎn)。 }//while visited[v0]=0。 num。 //取消訪問(wèn)標(biāo)記，使該頂點(diǎn)可重新使用。 }//SPathdfs 26. 與上題類似，這 里給出非遞歸算法，頂點(diǎn)信息仍是編號(hào)。 void AllSPdfs(AdjList g,vertype u,vertype v) //求有向圖 g中頂點(diǎn) u到頂點(diǎn) v的所有簡(jiǎn)單路徑，初始調(diào)用形式： AllSPdfs(g,u,v) { int top=0,s[]。 s[++top]=u。 visited[u]=1。 while (top0 || p) {p=g[s[top]].firstarc。 //第一個(gè)鄰接點(diǎn)。 while (p!=null amp。amp。 visited[padjvex]==1) p=pnext。 //下一個(gè)訪問(wèn)鄰接點(diǎn)表。 if (p==null) top。 //退棧。 else { i=padjvex。 //取鄰接點(diǎn)（編號(hào)）。 if (i==v) //找到從 u到 v的一條簡(jiǎn)單路徑，輸出。 {for (k=1。k=top。k++) printf( %3d,s[k])。 printf( %3d\n,v)。}//if else { visited[i]=1。 s[++top]=i。 } //else深度優(yōu)先遍歷。 }//else }//while }// AllSPdfs 類似本題的另外敘述的第（ 2）題 ： u到 v有三條簡(jiǎn)單路徑： uabfv， ucdv， ucdefv。 27. （ 1） [題目分析 ]D_搜索類似 BFS，只是用棧代 替隊(duì)列，入出隊(duì)列改為入出棧。查某頂點(diǎn)的鄰接點(diǎn)時(shí)，若其鄰接點(diǎn)尚未遍歷，則遍歷之，并將其壓入棧中。當(dāng)一個(gè)頂點(diǎn)的所有鄰接點(diǎn)被搜索后，棧頂頂點(diǎn)是下一個(gè) 搜索出發(fā)點(diǎn) 。 void D_BFS(AdjList g ,vertype v0) // 從 v0頂點(diǎn)開(kāi)始，對(duì)以鄰接表為存儲(chǔ)結(jié)構(gòu)的圖 g進(jìn)行 D_搜索。 { int s[], top=0。 //棧，棧中元素為頂點(diǎn)，仍假定頂點(diǎn)用編號(hào)表示。 for (i=1,i=n。i++) visited[i]=0。 //圖有 n個(gè)頂點(diǎn)， visited數(shù)組為全局變量。 for (i=1,i=n。i++) //對(duì) n個(gè)頂點(diǎn)的圖 g進(jìn)行 D_搜索。 if (visited[i]==0) {s[++top]=i。 visited[i]=1。 printf( %3d,i)。 while (top0) {i=s[top]。 //退棧 p=g[i].firstarc。 //取第一個(gè)鄰接點(diǎn) while (p!=null) //處理頂點(diǎn)的所有鄰接點(diǎn) {j=padjvex。 if (visited[j]==0) //未訪問(wèn)的鄰接點(diǎn)訪問(wèn)并入棧。 {visited[j]=1。 printf( %3d,i)。s[++top]=j。} p=pnext。 } //下一個(gè)鄰接點(diǎn) }//while(top0) } //if }//D_BFS （ 2） D_搜索序列： 1234675，生成樹(shù)如圖： 28， [題目分析 ] 本題的含義是對(duì)有向無(wú)環(huán)圖 (DAG)的頂點(diǎn)，以整數(shù)適當(dāng)編號(hào)后，可使其鄰接矩陣中對(duì)角線以下元素全部為零。根據(jù)這一要求，可以按各頂點(diǎn)出度大小排序，使出度最大1 5 3 2 4 7 二部圖 非二部圖 的頂點(diǎn)編號(hào)為 1，出度次大者編號(hào)為 2，出度為零的頂點(diǎn)編號(hào)為 n。這樣編號(hào)后，可能出現(xiàn)頂點(diǎn)編號(hào) ij，但卻有一條從頂點(diǎn)到 j到 i的弧。這時(shí)應(yīng)進(jìn)行調(diào)整，即檢查每一條弧，若有i,j，且 ij，則使頂點(diǎn) j的編號(hào)在頂點(diǎn) i的編號(hào)之前。 void Adjust(AdjMatrix g1 ,AdjMatrix g2) //對(duì)以鄰接矩陣存儲(chǔ)的 DAG圖 g1重新編號(hào)，使若有 i,j，則編號(hào) ij，重新編號(hào)后的圖以鄰接矩陣 g2存儲(chǔ)。 {typedef struct { int vertex ,out ,count }node 。 //結(jié)點(diǎn)結(jié)構(gòu)：頂點(diǎn)，出度，計(jì)數(shù)。 node v[]。 //頂點(diǎn)元素?cái)?shù)組。 int c[]。 //中間變量 for (i=1。i=n。i++) //頂點(diǎn)信息數(shù)組初始化，設(shè)圖有 n個(gè)頂點(diǎn)。 {v[i].vertex=i。 v[i].out=0。 v[i].count=1。 c[i]=1。} //count=1為最小 for (i=1。i=n。i++) //計(jì)算每個(gè)頂點(diǎn)的出度。 for (j=1。j=n。j++) v[i].out+=g1[i][j]。 for (i=n。i=2。i) //對(duì) v的出度域進(jìn)行計(jì)數(shù)排序，出度大者， count域中值小。 for (j=i1。j=1。j) if (v[i].count=v[j].count) v[i].count++。 else v[j].count++。 for (i=1。i=n。i++) //第二次調(diào)整編號(hào)。若 i,j且 ij，則頂點(diǎn) j 的編號(hào)在頂點(diǎn) i的編號(hào)之前 for (j=i。j=n。j++) if(g1[i][j]==1 amp。amp。 v[i].countv[j].count) {v[i].count=v[j].count。v[j].count++。} for (i=n。i=2。i)) //對(duì) v的計(jì)數(shù)域 v[i].count排序，按 count域從小到大順序存到數(shù)組 c中。 for (j=i1。j=1。j) if (v[i].countv[j].count) c[j]++。 else c[i]++。 for (i=1。i=n。i++) v[i].count=c[i]。 //將最終編號(hào)存入 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]。 }//算法結(jié)束 29. [題目分析 ] 將頂點(diǎn)放在兩個(gè)集合 V1 和 V2。對(duì)每個(gè)頂點(diǎn)，檢查其和鄰接點(diǎn)是否在同一個(gè)集合中，如是，則為非二部圖。為此，用整數(shù) 1和 2表示兩個(gè)集合。再用一隊(duì)列結(jié)構(gòu)存放圖中訪問(wèn)的頂點(diǎn)。 int BPGraph (AdjMatrix g) //判斷以鄰接矩陣表示的圖 g是否是二部圖。 {int s[]。 //頂點(diǎn)向量，元素值表示其屬于那個(gè)集合（值 1和 2表示兩個(gè)集合） int Q[]。//Q為隊(duì)列，元素為圖的頂點(diǎn)，這里設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)。 int f=0,r,visited[]。 //f和 r分別是隊(duì)列的頭尾指針 ,visited[]是訪問(wèn)數(shù)組 for (i=1。i=n。i++) {visited[i]=0。s[i]=0。} //初始化，各頂點(diǎn)未確定屬于那個(gè)集合 Q[1]=1。 r=1。 s[1]=1。//頂點(diǎn) 1放入集合 S1 while(fr) {v=Q[++f]。 if (s[v]==1) jh=2。 else jh=1。//準(zhǔn)備 v的鄰接點(diǎn)的集合號(hào) if (!visited[v]) {visited[v]=1。 //確保對(duì)每一個(gè)頂點(diǎn)，都要檢查與其鄰接點(diǎn)不應(yīng)在一個(gè)集合中 for (j=1,j=n。j++) if (g[v][j]==1){if (!s[j]) {s[j]=jh。 Q[++r]=j。} //鄰接點(diǎn)入隊(duì)列 else if (s[j]==s[v]) return(0)。} //非二部圖 }//if (!visited[v]) }//while return(1)。 }//是二部圖 [算法討論 ] 題目給的是連通無(wú)向圖，若非連通，則算法要修改。 30. [題目分析 ] 連通圖的生成樹(shù)包括圖中的全部 n 個(gè)頂點(diǎn)和足以使圖連通的 n1條邊，最小生成樹(shù)是邊上權(quán)值之和最小的生成樹(shù)。故可按權(quán)值從大到小對(duì)邊進(jìn)行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測(cè)試圖是否仍連通，若不再連通，則將該邊恢復(fù)。若仍連通，繼續(xù)向下刪；直到剩 n1條邊為止。 void SpnTree (AdjList g) //用“破圈法”求解帶權(quán)連通無(wú)向圖的一棵最小代價(jià)生成樹(shù)。 {typedef struct {int i,j,w}node。 //設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)，權(quán)是整型數(shù) node edge[]。 scanf( %d%d,amp。e,amp。n) 。 //輸入邊數(shù)和頂點(diǎn)數(shù)。 for (i=1。i=e。i++) //輸入 e條邊：頂點(diǎn)，權(quán)值。 scanf(%d%d%d ,amp。edge[i].i ,amp。edge[i].j ,amp。edge[i].w)。 for (i=2。i=e。i++) //按邊上的權(quán)值大小，對(duì)邊進(jìn)行逆序排序。 {edge[0]=edge[i]。 j=i1。 while (edge[j].wedge[0].w) edge[j+1]=edge[j]。 edge[j+1]=edge[0]。 }//for k=1。 eg=e。 while (eg=n) //破圈，直到邊數(shù) e=n1. {if (connect(k)