【正文】 種存儲結(jié)構(gòu)：數(shù)組表示法（重點是鄰接矩陣），鄰接表與逆鄰接表，這兩種存儲結(jié)構(gòu)對無向圖和有向圖均使用。熟練掌握圖的兩種遍歷算法：深度遍歷和廣度遍歷。深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個算法對圖一章的重要性等同于“先序、中序、后序遍歷”對于二叉樹一章的重要性。掌握圖的兩種遍歷算法的應用，圖一章的算法設計題常常是基于這兩種基本的遍歷算法而設計的。例如，在（強）連通圖中，主過程一次調(diào)用深（廣）度優(yōu)先遍歷過程（DFS/BFS），即可遍歷全部頂點，故可以用此方法求出連通分量的個數(shù)，要會畫出遍歷中形成的深（廣）度優(yōu)先生成樹和生成森林。又如，“求最長的最短路徑問題”和“判斷兩頂點間是否存在長為K的簡單路徑問題”，就用到了廣度遍歷和深度遍歷算法。最小生成樹的概念。連通圖的最小生成樹通常是不唯一的，但最小生成樹邊上的權(quán)值之和是唯一的。掌握最小生成樹的構(gòu)造方法：PRIM算法和KRUSKAL算法，根據(jù)這兩種算法思想用圖示法表示出求給定網(wǎng)的一棵最小生成樹的過程。拓撲排序是在有向圖上對入度（先、后）為零的頂點的一種排序，通常結(jié)果不唯一。拓撲排序有兩種方法，一是無前趨的頂點優(yōu)先算法，二是無后繼的頂點優(yōu)先算法。換句話說，一種是“從前向后”的排序，一種是“從后向前”排。后一種排序出來的結(jié)果是“逆拓撲有序”的。用拓撲排序和深度優(yōu)先遍歷都可判斷圖是否存在環(huán)路。關(guān)鍵路徑問題是圖一章的難點問題。理解關(guān)鍵路徑的關(guān)鍵有三個方面：一是何謂關(guān)鍵路徑，二是最早時間的含義及求解方法，三是最晚時間的含義及求解方法。簡單地說，最早時間是通過“從前向后”的方法求的，而最晚時間是通過“從后向前”的方法求解的，并且，要想求最晚時間必須是在所有的最早時間都已經(jīng)求出來之后才能進行。熟練掌握求解的過程和步驟。關(guān)鍵路徑問題是工程進度控制的重要方法，具有很強的實用性。理解“減少關(guān)鍵活動時間可以縮短工期”是指該活動為所有關(guān)鍵路徑所共有，且減少到尚未改變關(guān)鍵路徑的前提下有效。最短路徑問題也是為圖一章的難點問題。最短路徑問題分為兩種：一是求從某一點出發(fā)到其余各點的最短路徑；二是求圖中每一對頂點之間的最短路徑。解決第一個問題用DIJSKTRA算法，解決第二個問題用FLOYD算法，注意區(qū)分。掌握這兩個算法，并能手工熟練模擬。掌握用求最短路徑問題來解決的應用問題（如旅游景點及旅游路線的選擇問題）。練習題：（一）選擇題：下列哪一種圖的鄰接矩陣是對稱矩陣？（ B ）A. 有向圖 B. 無向圖 C. AOV網(wǎng) D. AOE網(wǎng)當各邊上的權(quán)值（ A ）時，廣度優(yōu)先遍歷算法可用來解決單源最短路徑問題。A. 均相等 B. 均不相等 C. 至少一多半相等 D. 至少一少半相等有n個結(jié)點的無向圖的邊數(shù)最多為（ B ）A．n+1 B．n(n1)/2 C．n(n+1) D．2n(n+1)在一個圖中，所有頂點的度數(shù)之和與圖的邊數(shù)的比是（ C ）A．1:2 B．1:1 C．2:1 D．4:1 已知有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6,v7}，E={v1,v2，v1,v3，v1,v4，v2,v5，v3,v5，v3,v6，v4,v6，v3,v7，v6,v7}，G的拓撲序列是（ A ）。A．v1,v3,v4,v6,v2,v5,v7 B．v1,v3,v2,v6,v4,v5,v7 C．v1,v3,v4,v5,v2,v6,v7 D．v1,v2,v5,v3,v4,v6,v7在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（ C ）條邊。A．n B. n+1 C. n1 D. n/2簡單無向圖的鄰接矩陣是對稱的，可以對其進行壓縮存儲。若無向圖G有n個結(jié)點，其鄰接矩陣為A[1…n,1…n]，且壓縮存儲在B[1…k]，則k的值至少為（ D ）。A．n(n+1)/2 B. n2/2C. (n1)(n+1)/2 D. n(n1)/2分析：簡單無向圖的鄰接矩陣是對稱的，且對角線元素均是0，故壓縮存儲只須存儲下三角或上三角（均不包括對角線）即可。無向圖中一個頂點的度是指圖中（ C ）A．通過該頂點的簡單路徑數(shù)B．通過該頂點的回路數(shù)C．與該頂點相鄰接的頂點數(shù)D．與該頂點連通的頂點數(shù)一個含有n個頂點和e條邊的簡單無向圖，在其鄰接矩陣存儲結(jié)構(gòu)中共有（ D ）個零元素。A．e B. 2eC. n2e D. n22e若采用鄰接矩陣來存儲簡單有向圖，則其某一個頂點i的入度等于該矩陣（ D ）。A．第i行中值為1的元素個數(shù) B. 所有值為1的元素個數(shù)C．第i行及第i列中值為1的元素總個數(shù)D．第i列中值為1的元素個數(shù)若一個具有n個結(jié)點、k條邊的非連通無向圖是一個森林（nk），則該森林中必有（ C ）棵樹。A．k B. nC. nk D. n+k若G是一個具有36條邊的非連通無向圖（不含自回路和多重邊），則圖G至少有（ B ）個頂點。A．11 B. 10C. 9 D. 8（二）應用題用深度優(yōu)先搜索遍歷如下圖所示的無向圖，試給出以A為起點的頂點訪問序列（同一個頂點的多個鄰點，按字母順序訪問），并給出一個最小生成樹。 7CBA41147564845GFED61355624JIH最小生成樹：ADHEFGBIJC321444745深度優(yōu)先搜索頂點訪問序列：A B E D H I F C G J2. 下面是求無向連通圖最小生成樹的一種方法。 將圖中所有邊按權(quán)重從大到小排序為（e1,e2,…,em） i:=1 WHILE (所剩邊數(shù) =頂點數(shù))BEGIN 從圖中刪去ei 若圖不再連通，則恢復ei i:=i+1END.試證明這個算法所得的圖是原圖的最小代價生成樹。答: 無向連通圖的生成樹包含圖中全部n個頂點，以及足以使圖連通的n1條邊。而最小生成樹則是各邊權(quán)值之和最小的生成樹。從算法中WHILE（所剩邊數(shù)=頂點數(shù)）來看，循環(huán)到邊數(shù)比頂點數(shù)少1（即n1）停止，這符合n個頂點的連通圖的生成樹有n1條邊的定義；由于邊是按權(quán)值從大到小排序，刪去的邊是權(quán)值大的邊，結(jié)果的生成樹必是最小生成樹；算法中“若圖不再連通，則恢復ei”，含義是必須保留使圖連通的邊，這就保證了是生成樹，否則或者是有回路，或者成了連通分量，均不再是生成樹。3. 對一個圖進行遍歷可以得到不同的遍歷序列，那么導致得到的遍歷序列不唯一的因素有哪些？答：遍歷不唯一的因素有：開始遍歷的頂點不同；存儲結(jié)構(gòu)不同；在鄰接表情況下鄰接點的順序不同。一個帶權(quán)連通圖的最小生成樹是否唯一？說明在什么情況下最小生成樹有可能不唯一？答：一個帶權(quán)連通圖的最小生成樹有可能不唯一。當圖中依附于某個頂點的多條邊出現(xiàn)權(quán)值相同的邊時，就有可能得到的最小生成樹不唯一。這里所說的最小生成樹不唯一，是指生成樹的形狀不唯一，這些生成樹的權(quán)值之和應該是相同的。abcdegf152846910453125. 已知加權(quán)有向圖G的鄰接矩陣如下：畫出該有向圖G試利用Dijkstra算法求G中從頂點a到其他各頂點間的最短路徑，并給出求解過程。答：（1)（2）終點DistbcdefgSk=115(a,b)2(a,c)12(a,d){a,c}k=215(a,b)12(a,d)10(a,c,e)6(a,c,f){a,c,f}k=315(a,b)11(a,c,f,d)10(a,c,e)16(a,c,f,g){a,c,f,e}k=415(a,b)11(a,c,f,d)16(a,c,f,g){a,c,f,e,d}k=515(a,b)14(a,c,f,d,g){a,c,f,e,d,g}k=615(a,b){a,c,f,e,d,g,b}，有向邊代表交通路線，若要建立一家醫(yī)院，試問建在哪一個村莊能使各村莊總體交通代價最小？04231313454131212156該圖的鄰接矩陣如下：利用Floyd算法可求得兩頂點之間最短路徑長度。最后求得：從A4中可求得每對村莊之間的最少交通代價。假設醫(yī)院建在i村莊時，其他各村莊往返總的交通代價如下所示：醫(yī)院建在村莊0時，各村莊往返總的交通代價為12+16+4+7+13+16+4+18=90；醫(yī)院建在村莊1時，各村莊往返總的交通代價為13+29+17+20+12+11+8+5=115；醫(yī)院建在村莊2時，各村莊往返總的交通代價為16+11+12+6+16+29+12+34=136；醫(yī)院建在村莊3時，各村莊往返總的交通代價為4+8+12+3+4+17+12+22=82；醫(yī)院建在村莊4時，各村莊往返總的交通代價為18+5+34+22+7+20+6+3=115。顯然，把醫(yī)院建在村莊3時總體交通代價最少。（三）算法設計題，求無向圖G（采用鄰接表存儲）的連通分量個數(shù)。解法一：采用深度優(yōu)先遍歷方法。算法如下：void DFS(AGraph *G, int v){ ArcNode *p。 visited[v]=1。 //置已訪問標記 prinf(”%d”,v)。 //輸出被訪問頂點的編號 p=Gadjlist[v].firstarc。 //p指向頂點v的第一條邊的終結(jié)點 while (p!=NULL) { if (visited[padjvex]==0) //若padjvex頂點未訪問，遞歸訪問它 DFS(G,padjvex)。 p=pnextarc。 //p指向頂點v的下一條邊的終結(jié)點}}int ConnNum1(AGraph *G) //求圖G的連通分量{ int i, num=0。 for (i=0。 iGn。 i++)visited[i]=0。 for (i=0。 iGn。 i++)if (visited[i]==0){DFS(G,i)。 //調(diào)用DFS算法num++。} return(num)。}解法二：采用廣度優(yōu)先遍歷方法。算法如下：void BFS(AGraph *G, int v){ ArcNode *p。 int Qu[MAXV]，front=0, rear=0。 //定義循環(huán)隊列并初始化 int w,i。 for (i=0。 iGn。 i++) visited[i]=0。 //訪問標志數(shù)組初始化 prinf(”2%d”,v)。 //輸出被訪問頂點的編號visited[v]=1。 //置已訪問標記 rear=(rear+1)%MAXV。 Qu[rear]=v。 //v入隊 while (front!=rear) //若隊列不空時循環(huán){ front=(front+1)%MAXV。 w=Qu[front]。 //出隊并賦予wp=Gadjlist[w].firstarc。 //找與頂點w鄰接的第一個頂點while (p!=NULL){ if (visited[padjvex]==0) //若當前鄰接頂點未被訪問 {printf(”%2d”, padjvex)。 //訪問相鄰頂點visited[padjvex]=1。 //置該頂點已被訪問的標志rear=(rear+1)%MAXV。 //該頂點入隊Qu[rear]= padjvex。} p=pnextarc。