【正文】 2. 如圖 G，試給出其對應的鄰接矩陣，并寫出廣度優(yōu)先算法。 鄰接表中的各單鏈表中的結點數(shù)除 2為圖的邊數(shù) 。 while(q!=NULL) { j=qadjvex。把鄰接表中所有入度為零的頂點進棧； ? 2。 ?由于 AOV網(wǎng)絡中有些頂點之間沒有次序要求，它們在拓撲有序序列中的位置可以任意顛倒，所以拓撲排序的結果一般并不是唯一的。 ( dist[i] dist[j] + cost [j, i] ) { dist[i]=dist[j]+ cost [j, i]。 } s=[0]。 i=e) /* 檢查該邊是否加入到生成樹中 */ { v1=seeks(set,ge[i].bv)。 ?用一個 set[ ]數(shù)組來表示頂點， set的初值為s[i]=0(i=1,2,…,n), 表示各頂點自成一個分量。 k++) if (gn [j, k] closedge [k]. lowcost。 假設 G=(V, E)是一個具有 n 個頂點的連通網(wǎng)絡， T=(U,TE)是 G的最小生成樹，其中 U是 T的頂點集， TE是 T的邊集， U和 TE的初值均為空。 返回 最小生成樹 ?在一個無向連通圖 G中，如果取它的全部頂點和一部分邊構成一個子圖 G’，若邊集 E(G’)中的邊剛好將圖的所有頂點連通但又不形成環(huán)路，我們就稱子圖 G’是原圖 G的生成樹（ Spanning tree）。 void bfs(adjlist adj,int v) { int front=0,rear=1,v。 p=adjlist[v].firstarc。 /*P為 v0的鄰接結點 while(p!=NULL) { if(visited[p→vertex]== 0) dfs(adjlist, p→vertex) 。 p→adjvex=s 。i=n。 ?有向圖 中某頂點的入度數(shù)，需掃描鄰接表的所有單鏈表，統(tǒng)計與頂點標號相應的結點個數(shù)。v2)。鄰接矩陣表示法 ? 鄰接矩陣是表示頂點之間相鄰關系的矩陣。 圖 子圖 ④ ① ② ③ ⑤ 4 ① ② ③ ⑤ ?頂點的度：圖中與每個頂點相連的邊數(shù)，叫該頂點的度 (Degree)，記作 TD（ V）。邊上帶權的圖稱為帶權圖，也稱為網(wǎng)絡(Network)。=V， E39。 j++) adjarry [i][j]=0。 ?在 無向圖 的鄰接表中，各頂點對應的單鏈表的結點數(shù)（不算表頭結點）就等于該頂點的度數(shù)。n,amp。 /*鄰接點序號為 d*/ p→next=g[s] .link。 } adjlist為鄰接表 ， 從 v0開始 深度優(yōu)先 遍歷的 遞歸 算法 void dfs(adjlist , v0) { visited[v0]=1。 if (visited[v]==0) /*若 v未訪問 { stack[++top] =pnext。 (c)w入隊 。 } } } 時間復雜性分析 ?一個有 n個頂點、 e條邊的圖，在廣度優(yōu)先搜索圖的過程中，每個頂點至多進一次隊列，圖的搜索過程實質上是通過邊來找頂點的過程，找鄰接點所需時間為 O(e)。加入 U 中。 /*輸出一條邊 closedge [j]. lowcost=0。如果取到某條邊，發(fā)現(xiàn)它的兩個端點已屬于同一集合時，此邊則應當舍去。 /* i表示獲取的生成樹中的邊數(shù) ， 初值為 1*/ j=1。 i++) /*最短路徑初始化 */ { dist[i]=cost[0,i]。 in。例如在圖， V2是 V3的前趨頂點，V1是 V2的前趨頂點， V3又是 V1的前趨頂點，環(huán)路表示頂點之間的先后關系進入了死循環(huán)。用該數(shù)據(jù)域存放下一個入度為零的頂點標號，將堆棧中的各個單元鏈接起來，再設置一個棧頂指針 top即可。 /*在鏈表中刪除入度為 0的頂點 ， 頂點序號為 i*/ q=adj[i]link。 若某條邊 ai 滿足 e[i]=L[i], 則 ai為關鍵活動。 0 ⑥ ⑤ ④ ① ② ③ ⑦ ⑧ ⑨ 圖 一個帶權連通圖 G 6. 應用 prim算法求圖 最小生成樹。 圖 一個無向圖 G ⑦ ⑥ ⑤ ② ③ ④ ⑧ ① ⑨ 5. 已知一個有 n個頂點的有向圖的鄰接表，設計算法分別實現(xiàn) 1) 求出圖中每個頂點的出度。 ? (2) 對于無向圖 ， 在鄰接矩陣中第 i行第 j列元素為 “ 1”， 或者第 j行第 i列元素為 “ 1”， 則頂點 i與 j有邊相連 。 top=j。 拓撲排序算法 void topsort(adjlist adj, int n) /*adj為鄰接表 */ { int num,i,j,top。 如果進行到某一步，無法找到無前趨的頂點，則說明此 AOV網(wǎng)絡中存在有向回路。 di s t 5 ∞ 25 0 25 ∞ 0 0 0 0 1 0 1 2 3 4 5 6 S 圖 算法動態(tài)執(zhí)行情況 di s t 5 12 25 0 23 ∞ 1 0 0 0 1 0 1 2 3 4 5 6 S di s t 5 12 25 0 21 ∞ 1 1 0 0 1 0 1 2 3 4 5 6 S di s t 5 12 25 0 21 ∞ 1 1 0 0 1 1 1 2 3 4 5 6 S di st 5 12 25 0 21 ∞ 1 1 1 0 1 1 1 2 3 4 5 6 S 返回 拓撲排序 ?在工程實踐中，一個工程項目往往由若干個子項目組成，這些子項目間往往有多種關系： ①先后關系，即必須在一子項目完成后，才能開始實施另一個子項目； ②子項目之間無次序要求，即兩個子項目可以同時進行，互不影響。 k++) { wm=max。 set[v1]=v2。 ?利用克魯斯卡爾構造最小生成樹的邊集數(shù)組結構定義如下： define MAXE 100 struct edges /* 邊集類型 ， 存儲一邊條的起始頂點為 bv,終止頂點為 tv和權 w */ { int bv,tv,w。 } } } 算法分析 ?該算法中每一步執(zhí)行都要掃描數(shù)組 lowcost，在 VU頂點集中找出與 U最近的頂點，令其為 k，并打印邊（ k,closest[k]）。 }； 然后 ,從那些其一個端點已在 U中，另一個端點在 VU中，找一條最短（即權值最?。┑倪?，假定該邊為 (Vi, Vj), 其中 Vi∈ U， Vj∈ VU, 并把該邊 (Vi, Vj)和頂點 Vi分別并入 T的邊集 TE和頂點 集 U中 . 如此進行下去，每次往生成樹里并入一個頂點和一條邊，直到 n1次后，把所有 n 個頂點都并入生成樹 T的頂點集 U中，此時 U=V， TE中包含有（ n1）條邊； 這樣， T就是最后得到的最小生成樹。 ?對于帶權的連通圖（連通網(wǎng)） G，其生成樹也是帶權的。 printf(“%d”,v)。 } while ((p!=null) or (top!=1)) /*為真返回 , } /*為假結束 2. 廣度優(yōu)先搜索 (BFS) ?圖的廣度優(yōu)先搜索（ BFS）類似于樹的按層次遍歷。 ?對輔助數(shù)組初始化時間為 O(n)。 /*將新結點插入頂點 Vd邊表的頭部 */ } } 返回 對有向圖 , 也可采用十字鏈表法 4. 鄰接多重表存儲法 用于無向圖 圖的遍歷 ? 1。g[i].data)。 /*邊的信息 * struct edgenode *nextarc 。 } while(v1!=0 amp。 對無權圖， ??? ???反之邊邊，對有向圖若存在對無向圖若存在0,),(1],[ jiji VVVVjiA圖 無向圖的鄰接矩陣 ○ A ○ B ○C ○ D DCBAA?????????????0111101111011110A B C D 圖 有向圖的鄰接矩陣 ○ A ○ B ○ C A B C CBAB???????????010100110可以看出 : 1. 無向圖的鄰接矩陣是對稱的， 即若 A[i， j]=1，必有 A[j， i]=1。 ?路徑（回路）：若從某頂點 Vp出發(fā)，沿一些邊經(jīng)過頂點 V1,V2,…,V m到達， Vq，則稱頂點序列(Vp, V1,V2,…,V m, Vq)為從 Vp到 Vq的 路徑 (Path)。完全圖中共有 n(n1)/2條邊，（ Complete graph，也稱