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