【正文】 vertex info nextarc ?圖 AV BV DV CV B C D ∧ A B D ∧ A C D ∧ A B C ∧ ?圖 AV BV CV C ∧ B C ∧ B ∧ ?對(duì)于 無(wú)向圖 的鄰接表來(lái)說(shuō)，一條邊對(duì)應(yīng)兩個(gè)單鏈表結(jié)點(diǎn)，鄰接表結(jié)點(diǎn)總數(shù)是邊數(shù)的 2倍。 ?有向圖 中某頂點(diǎn)的入度數(shù)，需掃描鄰接表的所有單鏈表，統(tǒng)計(jì)與頂點(diǎn)標(biāo)號(hào)相應(yīng)的結(jié)點(diǎn)個(gè)數(shù)。 /*一條邊的頂點(diǎn) */ } edgenode。 vexnode adjlist[maxvex]。 scanf(“%d,%d”,amp。i=n。 g[i].link=NULL。 scanf(“%d,%d”,amp。 p→adjvex=d 。 p→adjvex=s 。 深度優(yōu)先搜索 (DFS) ? 首先訪問(wèn)圖中某指定起始點(diǎn) Vi ，然后由 Vi出發(fā)訪問(wèn)它的任一相鄰接頂點(diǎn) Vj，再?gòu)?Vj出發(fā)訪問(wèn) Vj的任一未訪問(wèn)過(guò)的相鄰接頂點(diǎn) Vk，再?gòu)?Vk出發(fā)進(jìn)行類(lèi)似訪問(wèn)，如此進(jìn)行下去，直到某頂點(diǎn)已沒(méi)有未被訪問(wèn)過(guò)的相鄰接頂點(diǎn)時(shí)，則退回一步，退到前一個(gè)頂點(diǎn)，找前一個(gè)頂點(diǎn)的其它尚未被訪問(wèn)的相鄰接頂點(diǎn)。 in。 i++) if(visited[i]==0) dfs(adjlist, vi)。 /*P為 v0的鄰接結(jié)點(diǎn) while(p!=NULL) { if(visited[p→vertex]== 0) dfs(adjlist, p→vertex) 。 ?因此，當(dāng)用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索圖的時(shí)間復(fù)雜性為 O(e+n)。 top=1。 /*p臨時(shí)變量 do { while (p!=null) { v=pvertex。 p=adjlist[v].firstarc。 ?廣度優(yōu)先搜索的基本思想是：首先訪問(wèn)圖中某指定的起始點(diǎn) Vi并將其標(biāo)記為已訪問(wèn)過(guò)，然后由 Vi出發(fā)訪問(wèn)與它相鄰接的所有頂點(diǎn) Vj、 Vk…… ，并均標(biāo)記為已訪問(wèn)過(guò)，然后再按照Vj、 Vk…… 的次序，訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)，并均標(biāo)記為已訪問(wèn)過(guò)，下一步再?gòu)倪@些頂點(diǎn)出發(fā)訪問(wèn)與它們相鄰接的尚未被訪問(wèn)的頂點(diǎn)，如此做下去，直到所有的頂點(diǎn)均被訪問(wèn)過(guò)為止。 ?設(shè)此隊(duì)列由一個(gè)一維數(shù)組構(gòu)成，數(shù)組名為Queue，隊(duì)首指針和隊(duì)尾指針?lè)謩e為 front和rear。 被訪問(wèn)過(guò)的頂點(diǎn)入隊(duì)； 當(dāng)隊(duì)列非空時(shí) ， 進(jìn)行下面的循環(huán) { （ 1） 被訪問(wèn)過(guò)的頂點(diǎn)出隊(duì)； （ 2） 對(duì)所有與該頂點(diǎn)相鄰接的頂點(diǎn) w if (visited[w]==0) { (a)訪問(wèn) w頂點(diǎn)； (b)visited[w]=1。 void bfs(adjlist adj,int v) { int front=0,rear=1,v。 queue[rear]=v。 /*找 v的鄰接頂點(diǎn) */ while(p!=NULL) { if (visited[padjvex]==0) { visited[padjvex]=1。 } p=pnext。 返回 最小生成樹(shù) ?在一個(gè)無(wú)向連通圖 G中，如果取它的全部頂點(diǎn)和一部分邊構(gòu)成一個(gè)子圖 G’，若邊集 E(G’)中的邊剛好將圖的所有頂點(diǎn)連通但又不形成環(huán)路，我們就稱子圖 G’是原圖 G的生成樹(shù)（ Spanning tree）。我們把生成樹(shù)各邊的權(quán)值總和稱為該生成樹(shù)的權(quán)。 首先從某一結(jié)點(diǎn) U。 , 并加入集合 TE中，同時(shí)， V。 假設(shè) G=(V, E)是一個(gè)具有 n 個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)， T=(U,TE)是 G的最小生成樹(shù)，其中 U是 T的頂點(diǎn)集， TE是 T的邊集， U和 TE的初值均為空。 ?普里姆算法中每次選取的邊兩端，總是一個(gè)在 U 中，一個(gè)在 VU 中，故這個(gè)邊選取后一定能將未連通頂點(diǎn)連通而又保證不會(huì)形成環(huán)路。 } closedge[1].lowcost=0。 /* j∈V U printf(“… ”, closedge [j]. vex, j)。 k++) if (gn [j, k] closedge [k]. lowcost。 ?然后將 k加入 U頂點(diǎn)集合中，并修改數(shù)組lowcost和 closest。 ?設(shè)此圖是用邊集數(shù)組表示的，邊集數(shù)組是一個(gè)結(jié)構(gòu)數(shù)組，數(shù)組中的每個(gè)元素表示一條邊，組成每條邊的是三元組序列（邊的起始頂點(diǎn)、邊的終止頂點(diǎn)、邊的權(quán)值）。 ?開(kāi)始時(shí)假定 n 個(gè)頂點(diǎn)分屬于 n 個(gè)集合，即每個(gè)集合中有一個(gè)頂點(diǎn)，當(dāng)確定某條邊作為生成樹(shù)的一條邊時(shí)，就將該邊兩端點(diǎn)所屬的兩集合合并為一個(gè)，表示原來(lái)屬于兩個(gè)集合的各個(gè)頂點(diǎn)已被這條新的邊連通。 ?用一個(gè) set[ ]數(shù)組來(lái)表示頂點(diǎn)， set的初值為s[i]=0(i=1,2,…,n), 表示各頂點(diǎn)自成一個(gè)分量。 } typedef struct edges edgeset[MAXE]。 } 克魯斯卡爾算法 void kruskal (edgeset ge, int n, int e) /* ge為權(quán)按從小到大排序的邊集數(shù)組 */ { int set[MAXE], v1, v2, i, j。 /*給 set中每個(gè)元素賦初值 */ i=1。 i=e) /* 檢查該邊是否加入到生成樹(shù)中 */ { v1=seeks(set,ge[i].bv)。 j++。 例： 狄克斯特拉算法 ?狄杰斯特拉于 1959年提出了一個(gè)按路徑“長(zhǎng)度”遞增的次序，逐步得到由給定源點(diǎn)到圖的其余各點(diǎn)間的最短路徑的算法。 in。 } s=[0]。 j=0。amp。 /*集合的并運(yùn)算 For (i=0。 ( dist[i] dist[j] + cost [j, i] ) { dist[i]=dist[j]+ cost [j, i]。 ?在工廠中，一件設(shè)備的生產(chǎn)包括許多工序，各工序之間也存在這兩種關(guān)系。這種圖稱做網(wǎng)絡(luò) (Activity On Vertex work,簡(jiǎn)稱 AOV網(wǎng)絡(luò) )。 ? AOV網(wǎng)絡(luò)中一定不能有有向環(huán)路。 ?由于 AOV網(wǎng)絡(luò)中有些頂點(diǎn)之間沒(méi)有次序要求，它們?cè)谕負(fù)溆行蛐蛄兄械奈恢每梢匀我忸嵉?，所以拓?fù)渑判虻慕Y(jié)果一般并不是唯一的。 圖 拓?fù)渑判蜻^(guò)程 ? AOV網(wǎng)絡(luò) ⑤ ④ ③ ① ② ?輸出 V3后 ⑤ ④ ① ② ?輸出 V4后 ?輸出 V2后 ⑤ ① ② ⑤ ① ⑤ ?輸出 V1后 ?輸出 V5后 ?為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?，?duì)于給定的有向圖，假定采用鄰接表作為它的存儲(chǔ)結(jié)構(gòu)，每個(gè)頂點(diǎn)在鄰接表中對(duì)應(yīng)一個(gè)單鏈表，表示該頂點(diǎn)的各直接后繼頂點(diǎn)。 圖 AOV網(wǎng)絡(luò)的鄰接表 5 ∧ 1 ∧ 1 5 ∧ 2 1 0 0 3 ∧ 2 5 ∧ V1 V2 V3 V4 V5 ?在拓?fù)渑判蜻^(guò)程中，凡入度為零的頂點(diǎn)即是沒(méi)有前趨的頂點(diǎn)，可將其取出列入有序序列中，同時(shí)將該頂點(diǎn)從圖中刪除掉不再考慮。 ?設(shè)計(jì)算法時(shí)，可借用表頭結(jié)點(diǎn)的 Data域構(gòu)成一個(gè)鏈接堆棧。把鄰接表中所有入度為零的頂點(diǎn)進(jìn)棧； ? 2。 struct vexnode *q。i=n。 top=adj[i]data。 while(q!=NULL) { j=qadjvex。 } q=pnext。 ?離開(kāi)某頂點(diǎn)的各條邊所代表的活動(dòng)，只有在該頂點(diǎn)對(duì)應(yīng)的事件出現(xiàn)后才能開(kāi)始。 (若拓?fù)渑判蛐蛄兄械捻旤c(diǎn)個(gè)數(shù)小于網(wǎng)絡(luò) 中的頂點(diǎn)數(shù)，則說(shuō)明網(wǎng)絡(luò)中存在環(huán)路，算 法中止執(zhí)行 .) 3. 從匯點(diǎn) Vn出發(fā)，令 VL[n]=Ve[n]，按逆拓?fù)渑判虻男蛄星笃溆喔鼽c(diǎn)的 最遲發(fā)生時(shí)間 VL(i). ( 用公式 3) 4. 根據(jù)各點(diǎn)的 ve和 VL值 , 求出每條邊 ai的最早開(kāi)始時(shí)間 e(i)和最遲開(kāi)始時(shí)間 L(i) (用公式 1)。 鄰接表中的各單鏈表中的結(jié)點(diǎn)數(shù)除 2為圖的邊數(shù) 。 在鄰接表中的第 i個(gè)單鏈表中有結(jié)點(diǎn)為 j， 或者第 j個(gè)單鏈表中有結(jié)點(diǎn)為 i， 則頂點(diǎn) i與 j有邊相連 。 對(duì)于有向圖鄰接矩陣中第 i行元素之和為 i頂點(diǎn)的入度，第 j列元素之和為 j頂點(diǎn)的出度。 ????????????0111101111011110????????????????0101000001100010100000110(a) (b) 圖 一個(gè)無(wú)向圖 G 5. 分別給出圖 G圖的深度優(yōu)先搜索和廣度優(yōu)先搜索得到的頂點(diǎn)訪問(wèn)序列。 2. 如圖 G，試給出其對(duì)應(yīng)的鄰接矩陣，并寫(xiě)出廣度優(yōu)先算法。 2) 求出圖中每個(gè)頂點(diǎn)的入