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

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

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

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

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

如果一個(gè)圖存在一筆畫，則一筆畫的路徑叫做歐拉路，如果最后又回到起點(diǎn)，那這個(gè)路徑叫做歐拉回路。我們定義奇點(diǎn)是指跟這個(gè)點(diǎn)相連的邊數(shù)目有奇數(shù)個(gè)的點(diǎn)。對(duì)于能夠一筆畫的圖，我們有以下兩個(gè)定理。定理1：存在歐拉路的條件：圖是連通的，有且只有2個(gè)奇點(diǎn)。定理2：存在歐拉回路的條件：圖是連通的，有0個(gè)奇點(diǎn)。兩個(gè)定理的正確性是顯而易見的，既然每條邊都要經(jīng)過一次，那么對(duì)于歐拉路，除了起點(diǎn)和終點(diǎn)外，每個(gè)點(diǎn)如果進(jìn)入了一次，顯然一定要出去一次，顯然是偶點(diǎn)。對(duì)于歐拉回路，每個(gè)點(diǎn)進(jìn)入和出去次數(shù)一定都是相等的，顯然沒有奇點(diǎn)。求歐拉路的算法很簡單，使用深度優(yōu)先遍歷即可。根據(jù)一筆畫的兩個(gè)定理，如果尋找歐拉回路，對(duì)任意一個(gè)點(diǎn)執(zhí)行深度優(yōu)先遍歷；找歐拉路，則對(duì)一個(gè)奇點(diǎn)執(zhí)行DFS，時(shí)間復(fù)雜度為O(m+n)，m為邊數(shù)，n是點(diǎn)數(shù)。【課堂練習(xí)】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)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點(diǎn)序列正確的是（

）。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ī)則進(jìn)行搜索，得到序列{a,b,e,d,f,c}。2、【NOIP2002提高組】在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（

）倍。A．1/2B．1C．2D．4【答案】B【分析】在有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和。3、【NOIP2003提高組】假設(shè)我們用d=(a1,a2,...,a5),表示無向圖G的5個(gè)頂點(diǎn)的度數(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【分析】每條邊被兩個(gè)頂點(diǎn)計(jì)算度數(shù)，因此度數(shù)和必為偶數(shù)，ACD的度數(shù)和為奇數(shù)，因此正確答案為BE。4、【NOIP2004普及組】在下圖中，從頂點(diǎn)（

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

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

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

）。

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

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

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

D.存在一條回路,通過每個(gè)頂點(diǎn)恰好一次

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

C0,C1C1,C2C3C3,C7C0C6【答案】D【分析】拓?fù)渑判颍涸趯W(xué)習(xí)C5之前要先學(xué)習(xí)C3和C7，D答案的C5排在了C3前面。

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