南開(kāi)2008暑假集訓(xùn)圖論基礎(chǔ)

1、圖論基礎(chǔ)07軟件AngelClover內(nèi)容內(nèi)容n圖的表示圖的表示n圖的廣度優(yōu)先遍歷圖的廣度優(yōu)先遍歷n圖的深度優(yōu)先遍歷圖的深度優(yōu)先遍歷n拓?fù)渑判蛲負(fù)渑判騨強(qiáng)連通分量強(qiáng)連通分量I.圖的表示n鄰接矩陣表示： 3 1 2 (a) 無(wú)向圖 G3 (b)有向圖 G4 1 2 4 3 0111101011011010 001100110 (a) G3 的鄰接矩陣 (b) G4 的鄰接矩 在鄰接矩陣表示中，除了存放頂點(diǎn)本身信息外，還用一個(gè)矩陣表示各個(gè)頂點(diǎn)之間的關(guān)系。若（i,j）E(G)或i,jE(G),則矩陣中第i行 第j列元素值為1（帶權(quán)圖為權(quán)值），否則為0 。n圖的鄰接矩陣定義為：n 1 （帶權(quán)圖為權(quán)值）

2、 若（i,j）E(G)或i,jE(G)n Aij= n 0 其它情形 n鄰接矩陣的特點(diǎn)：n查詢O(1)n不能用來(lái)表示多重圖（即2個(gè)頂點(diǎn)之間有多條直接相連的邊）n空間開(kāi)銷是|V|*|V|n鄰接表表示： 1 2 4 3 1 2 3 4 2 4 1 3 4 2 4 1 2 3 (a)無(wú)向圖 G3 的鄰接表 3 1 2 1 2 3 2 3 3 1 1 2 3 3 1 1 3 (b) 有向圖 G4 的鄰接表 (c) 有向圖 G4 的逆鄰接表 n在鄰接矩陣表示中，節(jié)點(diǎn)u所指向的每個(gè)節(jié)點(diǎn)存放一個(gè)與之相臨的點(diǎn)，這樣每個(gè)節(jié)點(diǎn)v代表一條由u指向v的邊。n在帶權(quán)圖中，每個(gè)節(jié)點(diǎn)再加上一個(gè)權(quán)值域，這樣在訪問(wèn)到邊的同時(shí)，

3、也可以查詢到此邊的權(quán)值。n鄰接表的特點(diǎn)：n查詢不支持O(1)n可以表示多重圖n空間開(kāi)銷是|V|+|E|II廣度優(yōu)先遍歷n為了記錄搜索的軌跡，我們將每個(gè)頂點(diǎn)來(lái)著為白色，灰色或黑色。n白色頂點(diǎn)：在搜索過(guò)程中的某一時(shí)刻未被發(fā)現(xiàn)的點(diǎn)。n灰色頂點(diǎn)：已經(jīng)被發(fā)現(xiàn)還未擴(kuò)展的點(diǎn)。n黑色頂點(diǎn)：已經(jīng)擴(kuò)展完畢的點(diǎn)。nBFS(G,s)nFor each vertex uVG-sn do coloru - WHITEn du - oon u - NILLncolors - GRAYnDs - 0ns - NILLnENQUEUE(Q,s)nWhile Q n do u - DEQUEUE(Q)n for each u A

4、djun do if colorv = WHITEn then colorv - GRAYn dv - du + 1n v - un ENQUEUE(Q,v)n color - BLACKn通過(guò)分析廣度優(yōu)先遍歷的過(guò)程，我們可以得到以下結(jié)論：n1.設(shè)G=(V,E)是一個(gè)有向圖或無(wú)向圖，sV 為 G的任意一個(gè)頂點(diǎn)，則對(duì)任意(u,v)E,有n dist(s,v) dist(s,u)+1n dist(s,v)表示從s到v的最短距離n2.G=(V,E)是一個(gè)有向或無(wú)向圖，從s開(kāi)始進(jìn)行廣度優(yōu)先遍歷。在執(zhí)行終止時(shí)，對(duì)于每個(gè)頂點(diǎn)vV,有n dv dists,vn3.在BFS中的某一時(shí)刻，隊(duì)列Q中包含的頂點(diǎn)為V

5、1,V2,V3,Vr,V1是隊(duì)列的頭，Vr是隊(duì)列的尾，則有n dVr dv1+1且dVi dV(i+1)n(i=1,2,.r-1)n4.如果在BFS的執(zhí)行過(guò)程中，頂點(diǎn)Vi先于Vj入隊(duì)，則當(dāng)Vj入隊(duì)時(shí)，有：n dVi dVjn5.從源點(diǎn)s出發(fā)所能到達(dá)的vV,在運(yùn)行終止時(shí)，有n dv=dists,vn此外，對(duì)于所有從s出發(fā)可以達(dá)到的vV,其最短路徑是從s到v的路徑加上(v,v)n廣度優(yōu)先樹(shù)n在BFS搜索過(guò)程中我們形成了一個(gè)廣度優(yōu)先樹(shù)n對(duì)于所有可以從s出發(fā)到達(dá)的頂點(diǎn)v他，它們的前驅(qū)子圖是一棵廣度優(yōu)先樹(shù)n由于每個(gè)點(diǎn)最多只進(jìn)行一次ENQUEUE操作，所以該過(guò)程的運(yùn)行時(shí)間是一個(gè)線形函數(shù)，即時(shí)間復(fù)雜度為O(

6、V)n我們?cè)倩貋?lái)看點(diǎn)的著色問(wèn)題n由于每個(gè)點(diǎn)只會(huì)進(jìn)出隊(duì)列各一次n當(dāng)前隊(duì)列里的店都是灰色的n而已經(jīng)出過(guò)隊(duì)的點(diǎn)就是黑色的n而還未入隊(duì)的點(diǎn)就是白色的III深度優(yōu)先搜索n在這里，我們?cè)俣x一個(gè)時(shí)間戳。當(dāng)結(jié)點(diǎn)v被發(fā)現(xiàn)時(shí)我們蓋上第一個(gè)時(shí)間戳dv，當(dāng)我們結(jié)束對(duì)它的訪問(wèn)的時(shí)候蓋上第二個(gè)時(shí)間戳fv。n于是，對(duì)于任意結(jié)點(diǎn)uV，我們有 dufvn結(jié)合我們?cè)贐FS中對(duì)顏色的定義，對(duì)于頂點(diǎn)uV,以及時(shí)刻T，我們有1.u是白色的，當(dāng)時(shí)刻T在du之前2.u是灰色的，當(dāng)時(shí)刻T在du和fu之間3.u是黑色的，當(dāng)時(shí)刻T在fu之后n偽代碼：nDFS(G)nfor each uVGn coloru - WHITEn u - NULLnTime f(C)f(C)為C中點(diǎn)f(v)的最大值n3.設(shè)C，C是兩個(gè)不同的強(qiáng)連通分支，邊(u,v)ET,其中uC，vC，則f(C)f(C)。Poj2186 popular cowsn已知一些牛之間的關(guān)系，即一只認(rèn)為另一只更受歡迎。這個(gè)關(guān)系可