數(shù)據(jù)結(jié)構(gòu)：圖結(jié)構(gòu)的實(shí)現(xiàn)
【各種東拼西湊來(lái)的】
圖(Graph)是由頂點(diǎn)和連接頂點(diǎn)的邊構(gòu)成的離散結(jié)構(gòu)。在計(jì)算機(jī)科學(xué)中，圖是最靈活的數(shù)據(jù)結(jié)構(gòu)之一，很多問(wèn)題都可以使用圖模型進(jìn)行建模求解。例如：生態(tài)環(huán)境中不同物種的相互競(jìng)爭(zhēng)、人與人之間的社交與關(guān)系網(wǎng)絡(luò)、化學(xué)上用圖區(qū)分結(jié)構(gòu)不同但分子式相同的同分異構(gòu)體、分析計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)確定兩臺(tái)計(jì)算機(jī)是否可以通信、找到兩個(gè)城市之間的最短路徑等等。
1 圖的概念
1.1 圖的基礎(chǔ)概念串講
圖的結(jié)構(gòu)很簡(jiǎn)單，就是由頂點(diǎn)$V$集和邊$E$集構(gòu)成，因此圖可以表示成$G=(V, E)$。
注意：頂點(diǎn)有時(shí)也稱為節(jié)點(diǎn)或者交點(diǎn)，邊有時(shí)也稱為鏈接。
無(wú)向圖
我們可以說(shuō)這張圖中，有點(diǎn)集$V=\{1, 2, 3, 4, 5, 6\}$，邊集$E=\{(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)\}$。在無(wú)向圖中，邊$(u, v)$和邊$(v, u)$是一樣的，因此只要記錄一個(gè)就行了。簡(jiǎn)而言之，對(duì)稱。
有向圖
也很好理解，就是加上了方向性，頂點(diǎn)$(u, v)$之間的關(guān)系和頂點(diǎn)$(v,u)$之間的關(guān)系不同，后者或許不存在。例如，地圖應(yīng)用中必須存儲(chǔ)單行道的信息，避免給出錯(cuò)誤的方向。
加權(quán)圖：
權(quán)：與圖的邊或弧相關(guān)的數(shù)叫做權(quán)。
與加權(quán)圖對(duì)應(yīng)的就是無(wú)權(quán)圖，或叫等權(quán)圖。如果一張圖不含權(quán)重信息，我們就認(rèn)為邊與邊之間沒(méi)有差別。不過(guò)，具體建模的時(shí)候，很多時(shí)候都需要有權(quán)重，比如對(duì)中國(guó)重要城市間道路聯(lián)系的建模，總不能認(rèn)為從北京去上海和從北京去廣州一樣遠(yuǎn)(等權(quán))。
還有很多細(xì)化的概念，比如：無(wú)向圖中，任意兩個(gè)頂點(diǎn)間都有邊，稱為無(wú)向完全圖；加權(quán)圖起一個(gè)新名字，叫網(wǎng)(network)……然而，如無(wú)必要，毋增實(shí)體。
兩個(gè)重要關(guān)系：
鄰接(adjacency)：鄰接是兩個(gè)頂點(diǎn)之間的一種關(guān)系。如果圖包含$(u,v)$，則稱頂點(diǎn)$v$與頂點(diǎn)$u$鄰接。當(dāng)然，在無(wú)向圖中，這也意味著頂點(diǎn)$u$與頂點(diǎn)$v$鄰接。
關(guān)聯(lián)(incidence)：關(guān)聯(lián)是邊和頂點(diǎn)之間的關(guān)系。在有向圖中，邊$(u,v)$從頂點(diǎn)$u$開(kāi)始關(guān)聯(lián)到$v$，或者相反，從$v$關(guān)聯(lián)到$u$。注意，有向圖中，邊不一定是對(duì)稱的，有去無(wú)回是完全有可能的。細(xì)化這個(gè)概念，就有了頂點(diǎn)的入度(in-degree)和出度(out-degree)。無(wú)向圖中，頂點(diǎn)的度就是與頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，沒(méi)有入度和出度。在有向圖中，我們以圖1-2為例，頂點(diǎn)10有2個(gè)入度，$3\rightarrow10$，$11\rightarrow10$，但是沒(méi)有從10指向其它頂點(diǎn)的邊，因此頂點(diǎn)10的出度為0。
路徑(path)：依次遍歷頂點(diǎn)序列之間的邊所形成的軌跡。注意，依次就意味著有序，先1后2和先2后1不一樣。
簡(jiǎn)單路徑: 沒(méi)有重復(fù)頂點(diǎn)的路徑稱為簡(jiǎn)單路徑。說(shuō)白了，這一趟路里沒(méi)有出現(xiàn)繞了一圈回到同一點(diǎn)的情況，也就是沒(méi)有環(huán)。
環(huán)/回路：包含相同的頂點(diǎn)兩次或者兩次以上。圖1-3中的頂點(diǎn)序列$<1,2,4,3,1>$，1出現(xiàn)了兩次，當(dāng)然還有其它的環(huán)，比如$<1,4,3,1>$。
簡(jiǎn)單回路/簡(jiǎn)單環(huán)：除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路
無(wú)環(huán)圖：沒(méi)有環(huán)的圖，其中，有向無(wú)環(huán)圖有特殊的名稱，叫做DAG(Directed Acyline Graph)（最好記住，DAG具有一些很好性質(zhì)，比如很多動(dòng)態(tài)規(guī)劃的問(wèn)題都可以轉(zhuǎn)化成DAG中的最長(zhǎng)路徑、最短路徑或者路徑計(jì)數(shù)的問(wèn)題）。
下面這個(gè)概念很重要：
兩個(gè)連通分支：
連通的：無(wú)向圖中每一對(duì)不同的頂點(diǎn)之間都有路徑。如果這個(gè)條件在有向圖里也成立，那么就是強(qiáng)連通的。
連通分量：無(wú)向圖中的極大連通子圖。
兩點(diǎn)強(qiáng)連通：在有向圖G中，如果兩點(diǎn)互相可達(dá)
強(qiáng)連通圖：如果有向圖G的每?jī)蓚€(gè)頂點(diǎn)都強(qiáng)連通（任意兩點(diǎn)互相可達(dá)），稱G是一個(gè)強(qiáng)連通圖。
強(qiáng)連通分量：非強(qiáng)連通有向圖的極大強(qiáng)連通子圖，稱為強(qiáng)連通分量(strongly connected components)。
關(guān)節(jié)點(diǎn)(割點(diǎn))：某些特定的頂點(diǎn)對(duì)于保持圖或連通分支的連通性有特殊的重要意義。如果移除某個(gè)頂點(diǎn)將使圖或者分支失去連通性，則稱該頂點(diǎn)為關(guān)節(jié)點(diǎn)。（在某圖中，若刪除頂點(diǎn)V以及V相關(guān)的邊后，圖的一個(gè)連通分量分割為兩個(gè)或兩個(gè)以上的連通分量，則稱頂點(diǎn)V為該圖的一個(gè)關(guān)節(jié)點(diǎn)）。
橋(割邊)：和關(guān)節(jié)點(diǎn)類似，刪除一條邊，就產(chǎn)生比原圖更多的連通分支的子圖，這條邊就稱為割邊或者橋。
雙連通圖：在無(wú)向連通圖中，如果刪除該圖的任何一個(gè)結(jié)點(diǎn)都不能改變?cè)搱D的連通性，則該圖為雙連通的無(wú)向圖。個(gè)人理解就是一個(gè)雙連通圖沒(méi)有割點(diǎn)，沒(méi)有橋的圖。
1.2 一些有趣的圖概念
這一部分屬于圖論的內(nèi)容，基礎(chǔ)圖算法不會(huì)用到，但是我覺(jué)得挺有意思的，小記如下?！具@部分我沒(méi)看，照搬過(guò)來(lái)了】
同構(gòu)4：圖看起來(lái)結(jié)構(gòu)不一樣，但它是一樣的。假定有$G_1$和$G_2$，那么你只要確認(rèn)對(duì)于$G_1$中的所有的兩個(gè)相鄰點(diǎn)$a$和$b$，可以通過(guò)某種方式$f$映射到$G_2$，映射后的兩個(gè)點(diǎn)$f(a)$、$f(b)$也是相鄰的。換句話說(shuō)，當(dāng)兩個(gè)簡(jiǎn)單圖同構(gòu)時(shí)，兩個(gè)圖的頂點(diǎn)之間保持相鄰關(guān)系的一一對(duì)應(yīng)。
圖1-7就展示了圖的同構(gòu)，這里頂點(diǎn)個(gè)數(shù)很少判斷圖的同構(gòu)很簡(jiǎn)單。我們可以把v1看成u1，自然我們會(huì)把u3看出v3。用數(shù)學(xué)的語(yǔ)言就是$f(u_1)=v_1$，$f(u_3)=v_3$。u1的另外一個(gè)連接是到u2，v1的另外一個(gè)連接是到v4，不難從相鄰頂點(diǎn)的關(guān)系驗(yàn)證$f(u_2)=v_4$，$f(u_4)=v_2$。
歐拉回路(Euler Circuit)：小學(xué)數(shù)學(xué)課本上的哥尼斯堡七橋問(wèn)題，能不能從鎮(zhèn)里的某個(gè)位置出發(fā)不重復(fù)的經(jīng)過(guò)所有橋(邊)并且返回出發(fā)點(diǎn)。這也就小學(xué)的一筆畫問(wèn)題，歐拉大神解決里這個(gè)問(wèn)題，開(kāi)創(chuàng)了圖論。結(jié)論很簡(jiǎn)單：至少2個(gè)頂點(diǎn)的連通多重圖存在歐拉回路的充要條件是每個(gè)頂點(diǎn)的度都是偶數(shù)。證明也很容易，大家有興趣可以閱讀相關(guān)資料。結(jié)論也很好理解，從某個(gè)起點(diǎn)出發(fā)，最后要回起點(diǎn)，中間無(wú)論路過(guò)多少次起點(diǎn)，都會(huì)再次離開(kāi)，進(jìn)、出的數(shù)目必然相等，故一定是偶數(shù)。
哈密頓回路(Hamilton Circuit)：哈密頓回路條件就比歐拉回路嚴(yán)格一點(diǎn)，不能重復(fù)經(jīng)過(guò)點(diǎn)。你可能會(huì)感到意外，對(duì)于歐拉回路，我們可以輕而易舉地回答，但是我們卻很難解決哈密頓回路問(wèn)題，實(shí)際上它是一個(gè)NP完全問(wèn)題。這個(gè)術(shù)語(yǔ)源自1857年愛(ài)爾蘭數(shù)學(xué)家威廉·羅萬(wàn)·哈密頓爵士發(fā)明的智力題。哈密頓的智力題用到了木質(zhì)十二面體（如圖1-8(a)所示，十二面體有12個(gè)正五邊形表面）、十二面體每個(gè)頂點(diǎn)上的釘子、以及細(xì)線。十二面體的20個(gè)頂點(diǎn)用世界上的不同城市標(biāo)記。智力題要求從一個(gè)城市開(kāi)始，沿十二面體的邊旅行，訪問(wèn)其他19個(gè)城市，每個(gè)恰好一次，最終回到第一個(gè)城市。
因?yàn)樽髡卟豢赡芟蛎课蛔x者提供帶釘子和細(xì)線的木質(zhì)十二面體，所以考慮了一個(gè)等價(jià)的問(wèn)題：對(duì)圖1-8(b)的圖是否具有恰好經(jīng)過(guò)每個(gè)頂點(diǎn)一次的回路？它就是對(duì)原題的解，因?yàn)檫@個(gè)平面圖同構(gòu)于十二面體頂點(diǎn)和邊。
著名的旅行商問(wèn)題(TSP)要求旅行商訪問(wèn)一組城市所應(yīng)當(dāng)選取的最短路線。這個(gè)問(wèn)題可以歸結(jié)為求完全圖的哈密頓回路，使這個(gè)回路的邊的權(quán)重和盡可能的小。同樣，因?yàn)檫@是個(gè)NP完全問(wèn)題，最直截了當(dāng)?shù)姆椒ň蜋z查所有可能的哈密頓回路，然后選擇權(quán)重和最小的。當(dāng)然這樣效率幾乎難以忍受，時(shí)間復(fù)雜度高達(dá)$O(n!)$。在實(shí)際應(yīng)用中，我們使用的啟發(fā)式搜索等近似算法，可以完全求解城市數(shù)量上萬(wàn)的實(shí)例，并且甚至能在誤差1%范圍內(nèi)估計(jì)上百萬(wàn)個(gè)城市的問(wèn)題。
關(guān)于旅行商問(wèn)題目前的研究進(jìn)展，可以到http://www.math.uwaterloo.ca/...。
1.3 小結(jié)
以為可以一帶而過(guò)，結(jié)果寫了那么多。也沒(méi)什么好總結(jié)的了，當(dāng)然這些也至是圖論概念的一小部分，還有一些圖可能我們以后也會(huì)見(jiàn)到，比如順著圖到網(wǎng)絡(luò)流，就會(huì)涉及二分圖，不過(guò)都很好理解，畢竟有圖。
圖的存儲(chǔ)結(jié)構(gòu)
1、數(shù)組（鄰接矩陣）
2、鄰接表
3、十字鏈表
4、鄰接多種表
