第2章 第6節(jié) 圖論

第6節(jié)圖圖(Graph)是一種復雜的非線性結構。在人工智能、工程、數(shù)學、物理、化學、生物和計算機科學等領域中，圖結構有著廣泛的應用。奧林匹克信息學競賽的許多試題，亦需要用圖來描述數(shù)據(jù)元素間的聯(lián)系。圖G由兩個集合V和E組成，記為：G=(V，E)，其中：V是頂點的有窮非空集合，E是V中頂點偶對(稱為邊)的有窮集。通常，也將圖G的頂點集和邊集分別記為V(G)和E(G)。E(G)可以是空集。若E(G)為空，則圖G只有頂點而沒有邊。一、什么是圖？

很簡單，點用邊連起來就叫做圖，嚴格意義上講，圖是一種數(shù)據(jù)結構，定義為：graph=（V，E）。V是一個非空有限集合，代表頂點（結點），E代表邊的集合。二、圖的一些定義和概念1.(a)有向圖：圖的邊有方向，只能按箭頭方向從一點到另一點。(a)就是一個有向圖。2.(b)無向圖：圖的邊沒有方向，可以雙向。(b)就是一個無向圖。3.結點的度：無向圖中與結點相連的邊的數(shù)目，稱為結點的度。4.結點的入度：在有向圖中，以這個結點為終點的有向邊的數(shù)目。5.結點的出度：在有向圖中，以這個結點為起點的有向邊的數(shù)目。6.權值：邊的“費用”，可以形象地理解為邊的長度。7.連通：如果圖中結點U，V之間存在一條從U通過若干條邊、點到達V的通路，則稱U、V是連通的8.回路：起點和終點相同的路徑，稱為回路，或“環(huán)”。9.完全圖：一個n階的完全無向圖含有n*(n-1)/2條邊；一個n階的完全有向圖含有n*(n-1)條邊；稠密圖：一個邊數(shù)接近完全圖的圖。稀疏圖：一個邊數(shù)遠遠少于完全圖的圖。10.強連通分量：有向圖中任意兩點都連通的最大子圖。下圖中1-2-5構成一個強連通分量。特殊地，單個點也算一個強連通分量，所以右圖有三個強連通分量：1-2-5，4，3。12345(a)12345(b)12345

三、圖的存儲結構1.二維數(shù)組鄰接矩陣存儲定義intG[101][101];G[i][j]的值，表示從點i到點j的邊的權值，定義如下：上圖中的3個圖對應的鄰接矩陣分別如下：0111011∞58∞3G（A）=1011G（B）=0015∞2∞61100010G（C）=82∞1041100∞∞10∞1136411∞四、深度優(yōu)先與廣度優(yōu)先遍歷從圖中某一頂點出發(fā)系統(tǒng)地訪問圖中所有頂點，使每個頂點恰好被訪問一次，這種運算操作被稱為圖的遍歷。為了避免重復訪問某個頂點，可以設一個標志數(shù)組visited[i]，未訪問時值為false，訪問一次后就改為true。圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方法，兩者的時間效率都是O(n*n)。1.深度優(yōu)先遍歷深度優(yōu)先遍歷與深搜DFS相似，從一個點A出發(fā)，將這個點標為已訪問visited[i]:=true;，然后再訪問所有與之相連，且未被訪問過的點。當A的所有鄰接點都被訪問過后，再退回到A的上一個點（假設是B），再從B的另一個未被訪問的鄰接點出發(fā)，繼續(xù)遍歷。例如對右邊的這個無向圖深度優(yōu)先遍歷，假定先從1出發(fā)程序以如下順序遍歷：

1→2→5，然后退回到2，退回到1。從1開始再訪問未被訪問過的點3，3沒有未訪問的鄰接點，退回1。再從1開始訪問未被訪問過的點4，再退回1。起點1的所有鄰接點都已訪問，遍歷結束。123452.廣度優(yōu)先遍歷廣度優(yōu)先遍歷并不常用，從編程復雜度的角度考慮，通常采用的是深度優(yōu)先遍歷。廣度優(yōu)先遍歷和廣搜BFS相似，因此使用廣度優(yōu)先遍歷一張圖并不需要掌握什么新的知識，在原有的廣度優(yōu)先搜索的基礎上，做一點小小的修改，就成了廣度優(yōu)先遍歷算法。五、一筆畫問題

如果一個圖存在一筆畫，則一筆畫的路徑叫做歐拉路，如果最后又回到起點，那這個路徑叫做歐拉回路。我們定義奇點是指跟這個點相連的邊數(shù)目有奇數(shù)個的點。對于能夠一筆畫的圖，我們有以下兩個定理。定理1：存在歐拉路的條件：圖是連通的，有且只有2個奇點。定理2：存在歐拉回路的條件：圖是連通的，有0個奇點。兩個定理的正確性是顯而易見的，既然每條邊都要經(jīng)過一次，那么對于歐拉路，除了起點和終點外，每個點如果進入了一次，顯然一定要出去一次，顯然是偶點。對于歐拉回路，每個點進入和出去次數(shù)一定都是相等的，顯然沒有奇點。求歐拉路的算法很簡單，使用深度優(yōu)先遍歷即可。根據(jù)一筆畫的兩個定理，如果尋找歐拉回路，對任意一個點執(zhí)行深度優(yōu)先遍歷；找歐拉路，則對一個奇點執(zhí)行DFS，時間復雜度為O(m+n)，m為邊數(shù)，n是點數(shù)?！菊n堂練習】1、【NOIP2001提高組】無向圖G=(V，E)，其中V={a,b,c,d,e,f}E={(a,b),(a,e),(a,c),(b,e)，(c,f),(f,d),(e,d)}，對該圖進行深度優(yōu)先遍歷,得到的頂點序列正確的是（

）。A．a(chǎn),b,e,c,d,f

B．a(chǎn),c,f,e,b,d

C．a(chǎn),e,b,c,f,d

D．a(chǎn),b,e,d,f,c【答案】D【分析】依題中描述將無向圖畫出如圖所示：按照深度優(yōu)先搜索的規(guī)則進行搜索，得到序列{a,b,e,d,f,c}。2、【NOIP2002提高組】在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（

）倍。A．1/2B．1C．2D．4【答案】B【分析】在有向圖中，所有頂點的入度之和等于所有頂點的出度之和。3、【NOIP2003提高組】假設我們用d=(a1,a2,...,a5),表示無向圖G的5個頂點的度數(shù)，下面給出的哪（些）組d值合理（

）。A．{5，4，4，3，1}B．{4，2，2，1，1}C．{3，3，3，2，2}D．{5，4，3，2，1}E．{2，2，2，2，2}【答案】BE【分析】每條邊被兩個頂點計算度數(shù)，因此度數(shù)和必為偶數(shù)，ACD的度數(shù)和為奇數(shù)，因此正確答案為BE。4、【NOIP2004普及組】在下圖中，從頂點（

）出發(fā)存在一條路徑可以遍歷圖中的每條邊一次，而且僅遍歷一次。A.A點B.B點C.C點D.D點E.E點【答案】E【分析】歐拉圖問題，E是奇點。5、【NOIP2005普及組】平面上有五個點A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以這五點作為完全圖G的頂點，每兩點之間的直線距離是圖G中對應邊的權值。以下哪條邊不是圖G的最小生成樹中的邊（

）。A.ADB.BDC.CDD.DEE.EA【答案】D【分析】笛卡爾坐標系畫出來,生成樹是n-1條總長最短的邊連所有點。6、【NOIP2005提高組】平面上有五個點A(5,3)，B(3,5),，C(2,1),，D(3,3)，E(5,1)。以這五點作為完全圖G的頂點，每兩點之間的直線距離是圖G中對應邊的權值。圖G的最小生成樹中的所有邊的權值綜合為（

）?！敬鸢浮緿【分析】根據(jù)kruskal算法,選取權值最小的、且不構成回路的邊來產(chǎn)生最小生成樹,因此,選出的邊為(A,D),(A,E),(B,D),(C,D),其權值和為(2+2+2+sqrt(5)),即答案為D。7、【NOIP2007提高組】歐拉圖G是指可以構成一個閉回路的圖，且圖G的每一條邊恰好在這個閉回路上出現(xiàn)一次（即一筆畫成）。在以下各個描述中,不一定是歐拉圖的是（

）。

A.圖G中沒有度為奇數(shù)的頂點

B.包括歐拉環(huán)游的圖(歐拉環(huán)游是指通過圖中每邊恰好一次的閉路徑)

C.包括歐拉閉跡的圖(歐拉跡是指通過途中每邊恰好一次的路徑)

D.存在一條回路,通過每個頂點恰好一次

E.本身為閉跡的圖【答案】D【分析】通過每個頂點一次的是哈密爾頓圖，歐拉圖是每條邊一次，一筆畫問題，閉跡回到起點封口。8、【NOIP2004普及組】某大學計算機專業(yè)的必修課及其先修課程如下表所示：課程代號C0C1C2C3C4C5C6C7課程名稱高等數(shù)學程序設計語言離散數(shù)學數(shù)據(jù)結構編譯技術操作系統(tǒng)普通物理計算機原理先修課程

C0,C1C1,C2C3C3,C7C0C6【答案】D【分析】拓撲排序：在學習C5之前要先學習C3和C7，D答案的C5排在了C3前面。

A.C0,C6,C7,C1,C2,C3,C