數(shù)據(jù)結(jié)構(gòu)--圖

0.什么是圖耸袜？

<0>：表示“多對多”的關(guān)系

<2>：包括

i：一組頂點(diǎn)：通常用V（Vertex）表示頂點(diǎn)的集合

ii：一組邊：通常用E（Edge）表示邊的集合

（1）：邊是頂點(diǎn)對： $（v什湘，e）\in E，$ 其中 $v奈惑，w\in V$ ? ?v-------w

（2）：有向邊<v趣席，w>表示從v指向w的邊（單行線）? ?v------>w

（3）：不考慮重邊和自回路

<3>：圖的兩種定義

i：二元組定義：一張圖G是一個二元組(V, E)，其中V稱為頂點(diǎn)集杂曲，E稱為邊集诈火。他們也可以寫成V(G)和E(G)兽赁。E的元素是一個二元組對，用(x, y)表示柄瑰，其中 $x, y\in V$ .

ii：三元組定義：一張圖G是一個三元組(V, E, I)闸氮，其中V稱為頂點(diǎn)集(Vertices set)，E稱為邊集(Edges set)教沾，E與V兩兩不相交；I稱為關(guān)聯(lián)函數(shù)译断，I將E中的每一個元素映射到V x V授翻。如果I(e)=(u, v)( $e \in E, v \in V$ )那么稱邊e連接頂點(diǎn)u，v孙咪，而u堪唐，v稱為e的端點(diǎn)，u翎蹈，v此時關(guān)于e相鄰淮菠。同時若兩條邊i，j有一個公共頂點(diǎn)u荤堪，那么稱i合陵，j關(guān)于u相鄰。

1.圖的分類

<1>：有向圖澄阳、無向圖

如果給圖中每條邊規(guī)定一個方向拥知，那么得到的圖稱為有向圖，其邊也稱為有向邊碎赢。在有向圖中低剔，與一個節(jié)點(diǎn)相關(guān)聯(lián)的邊有出邊和入邊之分，而與一個有向邊關(guān)聯(lián)的兩個點(diǎn)又有始點(diǎn)和終點(diǎn)之分。相反襟齿，邊沒有方向的圖稱為無向圖姻锁。

<2>：簡單圖

一個圖如果：

1.沒有兩條邊，它們所關(guān)聯(lián)的兩個點(diǎn)都相同

2.每條邊所關(guān)聯(lián)的是兩個不同的頂點(diǎn)猜欺。

則稱為簡單圖屋摔。簡單的有向圖和無向圖都可以使用以上的“二元組定義”。但形如（x, x）的序?qū)Σ粚儆贓替梨。而無向圖的邊集必須是對稱的钓试，即如果 $(x, y)\in E, 那么(y, x) \in E$ .

<3>：多重圖

若允許兩結(jié)點(diǎn)間的邊數(shù)多于一條，又允許頂點(diǎn)通過同一條邊和自己關(guān)聯(lián)副瀑，則為多重圖的概念弓熏。它只能用“三元組的定義”。

2.關(guān)于圖的一些重要的概念術(shù)語

（1）：階(Order)：圖G中頂集V的大小稱為圖G的階糠睡。

（2）：子圖(Sub-Graph)：圖G'稱作是圖G的子圖挽鞠，如果

（3）：生成子圖：滿足條件V(G') = V(G)的G的子圖G'。

（4）：度(Degree)：一個頂點(diǎn)的度是指與該頂點(diǎn)相關(guān)聯(lián)的總邊數(shù)狈孔，頂點(diǎn)v的度記為d(v)信认，度和邊的關(guān)系有： $\sum_{v\in V}^d(v) = 2 \vert E \vert$ .

（5）：出度(Out-degree)和入度(In-degree)：對有向圖而言，頂點(diǎn)的度還可分為出度和入度均抽。一個頂點(diǎn)的出度為d0嫁赏，是指有d0條邊以該頂點(diǎn)為起點(diǎn)，或說與該點(diǎn)關(guān)聯(lián)的出邊共有d0條油挥。入度的概念也類似潦蝇。

（6）：自環(huán)(Loop)：若一條邊的兩個頂點(diǎn)相同，則此邊稱作自環(huán)深寥。

（7）：路徑(Path)：從頂點(diǎn)u到頂點(diǎn)v的一條路徑是指一個序列v0,e1,v2,e2,.....,vk, ei的起點(diǎn)和重點(diǎn)為vi-1, vi攘乒；k稱作路徑長度。v0 = u惋鹅。稱為路徑起點(diǎn)则酝。vk = v,稱為路徑終點(diǎn)。如果u = v闰集，稱該路徑是閉的沽讹，否則稱之為開的，如果v1.....vk兩兩不等返十，則稱之為簡單路徑(可以是閉環(huán))妥泉。

（8）：行跡(Trace）：如果路徑P(u, v)中各邊各不相同，則該路徑稱為u到v的一條行跡洞坑。

（9）：軌道(Track)：即簡單路徑盲链。

（10）：距離(Distance)：從頂點(diǎn)u出發(fā)到頂點(diǎn)v的最短路徑若存在，則此路徑的長度稱作從u到v的距離。否則稱為u到v的距離為無窮大刽沾。

（11）：橋(Bridge)：若去點(diǎn)一條邊本慕，便會是的整個圖不連通，該邊稱為橋侧漓。

（12）：拓?fù)渑判颍菏且粋€有向無環(huán)圖的所有頂點(diǎn)的線性序列锅尘，該序列必須滿足一下兩個條件：

i：每個頂點(diǎn)出現(xiàn)且只出現(xiàn)以此

ii：若存在一條從頂點(diǎn)A到頂點(diǎn)B的路徑，那么在序列中頂點(diǎn)A出現(xiàn)在頂點(diǎn)B的前面

（13）：連通：如果從v到w存在一條（無向）路徑布蔗，則稱v和w是連通的藤违。

（14）：連通圖：圖中任意兩點(diǎn)均連通。

（15）：連通分量：無向圖的極大連通子圖

3.抽象數(shù)據(jù)類型定義

類型名稱：圖(Graph)

數(shù)據(jù)對象集：G(V, E)由一個非空的有限頂點(diǎn)集合V和一個有限邊集合E組成纵揍。

操作集：對于任意圖 $G\in Graph, v\in V, e\in E$

1.Graph Create():建立并返回空圖

2.Graph InsertVertex(Graph G, Vertex v):將v插入G

3.Graph InsertEdge(Graph G, Edge e):將e插入G

4.void DFS(Graph G, Vertex v):從頂點(diǎn)v出發(fā)的深度優(yōu)先搜索

5.void BFS(Graph G, Vertex v):從頂點(diǎn)v出發(fā)的廣度優(yōu)先搜索

6.void ShortestPath(Graph G, Vertex v, int Dist[ ]):計(jì)算圖G中頂點(diǎn)v到任意其他頂點(diǎn)的最短距離

7.void MST(Graph G):計(jì)算圖G的最小生成樹

4.如何表示一個圖顿乒？

鄰接矩陣、鄰接表

（0）：鄰接矩陣G[N][N]----N個頂點(diǎn)從0~N-1編號泽谨。

G[i][j] = 1 （若<vi璧榄，vj>是G中的邊），否則G[i][j] = 0;

對于有向圖可以這么存儲吧雹，但是對于無向圖來說骨杂，G[i][j] = G[j][i]，所以會造成極大的空間浪費(fèi)雄卷，故此搓蚪，對于無向圖我們可以使用一個長度為N(N+1)/2的一維數(shù)組A進(jìn)行存儲，G[i][j]在A中對應(yīng)的下標(biāo)為：(i*(i+1)/2+j)龙亲，對于網(wǎng)絡(luò)陕凹，我們只要把G[i][j]的值定義為<vi, vj>的權(quán)重即可。

(1)：臨界矩陣的優(yōu)劣：

i：好處：

1.直觀鳄炉，簡單，好理解

2.方便檢查任意一堆頂點(diǎn)之間是否存在邊

3.方便尋找人一丁點(diǎn)的所有"鄰接點(diǎn)"

4.方便計(jì)算任意頂點(diǎn)的"度"

ii：壞處：

1.浪費(fèi)空間搜骡，存在一些稀疏圖

2.浪費(fèi)時間

（2）：鄰接表：G[N]是一個指針數(shù)組拂盯，對應(yīng)矩陣每行一個鏈表，只存非零元素记靡。對于網(wǎng)絡(luò)谈竿，結(jié)構(gòu)中要增加權(quán)重的域。

(3)：鄰接表的優(yōu)劣：

i:優(yōu)點(diǎn)：

1.方便查找任意頂點(diǎn)的所有“鄰接點(diǎn)”

2.節(jié)約稀疏圖的空間

3.方便計(jì)算無向圖的任意頂點(diǎn)的度摸吠、對于有向圖則要構(gòu)造逆鄰接表來方便計(jì)算出度

ii：壞處

1.不方便檢查任意一堆頂點(diǎn)間是否存在邊

5.圖的遍歷方法

<1>:深度優(yōu)先搜索

1.首先將根節(jié)點(diǎn)放入stack中空凸。

2.從stack中取出第一個節(jié)點(diǎn)，并檢查它是否是目標(biāo)寸痢。

? ? ? ?i：如果找到目標(biāo)呀洲，結(jié)束搜索并返回結(jié)果。

? ? ? ii：否則將他的某一個尚未檢驗(yàn)過的直接子節(jié)點(diǎn)加入stack中。

3.重復(fù)步驟2

4.如果不存在為檢驗(yàn)過的直接子節(jié)點(diǎn)

? ? ?i：將上一級節(jié)點(diǎn)加入stack中

? ? ?ii：重復(fù)步驟2

5.重復(fù)步驟4

6.若stack為空道逗，表示整張圖都被檢查過了----即途中沒有所要搜尋的目標(biāo)兵罢，結(jié)束搜索。

<2>.廣度優(yōu)先搜索

1.首先將根節(jié)點(diǎn)放入隊(duì)列中

2.從隊(duì)列中取出第一個節(jié)點(diǎn)滓窍，并檢驗(yàn)他是否為目標(biāo)卖词。

? ? ? i:如果是目標(biāo)，則結(jié)束搜索并回傳結(jié)果吏夯。

? ? ? ii：否則將他所有尚未檢驗(yàn)過的直接子節(jié)點(diǎn)加入到隊(duì)列中此蜈。

3.若隊(duì)列為空，表示整張圖都被檢查過了----即途中沒有所要搜尋的目標(biāo)噪生，結(jié)束搜索裆赵。

4.重復(fù)步驟2。

<3>：如果圖不連通

6.最短路徑問題

<1>：最短路徑問題的抽象

在網(wǎng)絡(luò)中杠园，求兩個不同頂點(diǎn)之間所有路徑中顾瞪，邊的權(quán)值之和最小的那一條路徑。

? ? ?i：這條路徑就是兩點(diǎn)之間的最短路徑

? ? ?ii：第一個頂點(diǎn)是源點(diǎn)抛蚁，最后一個頂點(diǎn)是終點(diǎn)

<2>：問題分類

i：單源最短路徑問題：從某固定源點(diǎn)出發(fā)陈醒，求其到所有其他頂點(diǎn)的最短路徑。

? *：（有向）無權(quán)圖

? **：（有向）有權(quán)圖

ii：多源最短路徑問題：求任意兩點(diǎn)間的最短路徑問題

<3>：無權(quán)圖的單源最短路徑算法

思路：按照遞增（非遞減）的順序找出到各個頂點(diǎn)的最短路

算法：

1.將所有點(diǎn)的距離Dist和Path都設(shè)為-1/無窮大

2.根據(jù)起始點(diǎn)瞧甩，將起始點(diǎn)的Dist設(shè)為0

3.運(yùn)用廣度優(yōu)先遍歷的思路钉跷，依次遍歷下一個頂點(diǎn)，并將下一個頂點(diǎn)的Dist在原來的上一個頂點(diǎn)的基礎(chǔ)上加1肚逸，路徑就是前一個頂點(diǎn)

4.重復(fù)3直至所有頂點(diǎn)遍歷完爷辙，結(jié)束。

這不就是廣度優(yōu)先搜索碼ｋ佟Ｏチ馈！务冕！

<4>：有權(quán)圖的最短路徑算法

i：Dijkstra算法：（單源算法）

1.把所有頂點(diǎn)的路徑長度設(shè)為無窮大（INFINITY）血当，即我們不知道任何通向這些頂點(diǎn)的路徑。

2.將給定的源點(diǎn)加入最小堆（優(yōu)先隊(duì)列）中禀忆，對于該點(diǎn)的所有鄰接頂點(diǎn)進(jìn)行判斷臊旭，如果該點(diǎn)的距離小于原先的值，則將該值進(jìn)行更新箩退。

3.將該點(diǎn)的所有鄰接頂點(diǎn)加入最小堆中

4.從優(yōu)先隊(duì)列中挑選出一個路徑值最小的頂點(diǎn)离熏，彈出作為新的頂點(diǎn)重復(fù)2，3

5.所有的頂點(diǎn)都被處理過戴涝，結(jié)束滋戳。

注意钻蔑，Dijkstra算法是用于權(quán)值都為正的情況

ii：Floyd算法

。胧瓜。矢棚。。

先分割一下府喳，還有一些沒理解到位蒲肋，效率變低了一點(diǎn)，出去打會球钝满！

7.最小生成樹問題(Minimum Spanning Tree)

ps:最小生成樹存在 <--------> 圖連通

定義：最小生成樹是一副連通加權(quán)無向圖中一顆權(quán)值最小的生成樹兜粘。

在一個給定的無向圖G=（V，E）中弯蚜，（u孔轴，v）代表連接頂點(diǎn)u與頂點(diǎn)v的邊，而w（u碎捺，v）代表此邊的權(quán)重路鹰，若存在T為E的子集且（V，T）為樹收厨，使得： $w(T) = \sum_{(u,v)\in T}^n w(u,v)$ 的w(T)最小晋柱，則T為G的最小生成樹。

<1>：Prim算法---讓一個小樹長大(稠密圖比較合算）

（1）以某一個點(diǎn)開始诵叁，尋找當(dāng)前該點(diǎn)可以訪問的所有的邊雁竞；

（2）在已經(jīng)尋找的邊中發(fā)現(xiàn)最小邊，這個邊必須有一個點(diǎn)還沒有訪問過拧额，將還沒有訪問的點(diǎn)加入我們的集合碑诉，記錄添加的邊；

（3）尋找當(dāng)前集合可以訪問的所有邊侥锦，重復(fù)2的過程进栽，直到?jīng)]有新的點(diǎn)可以加入；

（4）此時由所有邊構(gòu)成的樹即為最小生成樹恭垦。

<2>：Kruskal算法

1.將每個頂點(diǎn)放入其自身的數(shù)據(jù)集合中泪幌，按照權(quán)值的升序來選擇邊。

2.當(dāng)選擇每條邊時署照，判斷定義邊的頂點(diǎn)是否在不同的數(shù)據(jù)集中。如果是吗浩，將此邊插入最小生成樹的集合中建芙，同時，將集合中包含每個頂點(diǎn)的聯(lián)合體取出懂扼，如果不是禁荸，就移動到下一條邊右蒲。（并查集)

3.重復(fù)這個過程直到所有的邊都探查過。

8.拓?fù)渑判颍ˋOV--Activity On Vertex）

拓?fù)湫颍?/b>如果圖中從v到w有一條有向路徑赶熟，則v一定排在w之前瑰妄。滿足此條件的頂點(diǎn)序列稱為一個拓?fù)湫颉＋@得一個拓?fù)湫虻倪^程就是拓?fù)渑判?/b>

AOV如果有合理的拓?fù)湫蛴匙瑒t必定是有向無環(huán)圖（Directed Acyclic Graph, DAG）

關(guān)鍵路徑問題：AOE（Activity On Edge）網(wǎng)絡(luò)

<1>:一般用于安排項(xiàng)目的工序