圖的基本概念

圖由結(jié)點的有窮集合V和邊的集合E組成翩活。圖中常常將結(jié)點成為頂點，邊是頂點的有序偶對便贵。若兩個頂點之間存在一條邊菠镇，則表示這兩個頂點具有相鄰關(guān)系。
邊有方向的稱為有向圖承璃，沒有方向的稱為無向圖利耍。
弧：在有向圖中盔粹，通常將邊稱為弧隘梨，含箭頭的一端成為弧頭，另一端稱為弧尾舷嗡，記作<vi,vj>轴猎，它表示從頂點vi到頂點vj有一條邊。
有向完全圖：若有向圖有n個頂點进萄，則最多有n(n-1)條邊（圖中任意兩個頂點都有兩條邊相連）捻脖，將具有n(n-1)條邊的有向圖稱為有向完全圖。
無向完全圖：若無向圖中有n個頂點中鼠，則最多有n(n-1)/2條邊（任意兩個頂點之間都有一條邊）可婶，將具有n(n-1)/2條邊的無向圖稱為無向完全圖。

圖的存儲結(jié)構(gòu)

1.鄰接矩陣
鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣援雇。設(shè)G=(V, E)是具有n個頂點的圖矛渴，頂點序號依次為0,1,...,n-1，則G的鄰接矩陣是具有如下定義的n階方陣A：
A[i][j]=1,表示頂點i與頂點j鄰接惫搏，即i與j之間存在邊或者痪呶隆；
A[i][j]=0,表示頂點i與頂點j不鄰接筐赔。
鄰接矩陣是圖的順序存儲結(jié)構(gòu)铣猩。
對于無向圖，鄰接矩陣是對稱的川陆，矩陣中“1”的個數(shù)為圖中總邊數(shù)的兩倍剂习，矩陣中第i行或第i列的元素之和即為頂點i的度。
對于有向圖较沪，矩陣中1的個數(shù)為圖的邊數(shù)鳞绕，矩陣中第i行的元素之和為頂點i的出度，第j列元素之和即為頂點j的出度尸曼。
鄰接矩陣的結(jié)構(gòu)型定義如下：

typedef struct {
  int no; /* 頂點編號 */
  char info; /* 頂點其他信息 */
}VertexType; //頂點類型

typedef struct {
  int edges[maxSize][maxSize];
  int n, e;
  VertexType vex[maxSize];
}MGraph;   //圖的鄰接矩陣類型

2.鄰接表
鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)们何。所謂鄰接表就是對圖中的每個頂點i建立一個單鏈表，每個單鏈表的第一個結(jié)點存放有關(guān)頂點的信息控轿，把這一結(jié)點看作鏈表的表頭冤竹，其余結(jié)點存放有關(guān)邊的信息。它的缺點是不方便判斷兩個頂點之間是否有邊茬射，但是相對鄰接矩陣來說更省空間鹦蠕。

無向圖的鄰接表.png

有向圖的鄰接表.png

圖的遍歷算法操作

1.深度優(yōu)先搜索遍歷DFS

Depth First Search
圖的DFS類似于二叉樹的先序遍歷。它的基本思想是：首先訪問出發(fā)點v在抛，并將其標(biāo)記為已訪問過钟病；然后選取與v鄰接的未被訪問的任意一個頂點w，并訪問它刚梭；再選取與w鄰接的未被訪問的任一頂點并訪問肠阱，以此重復(fù)進(jìn)行。當(dāng)一個頂點所有的鄰接頂點都被訪問過時朴读，則依次退回到最近被訪問過的頂點屹徘，若該頂點還有其他鄰接頂點未被訪問，則從這些未被訪問的頂點中取一個并重復(fù)上述訪問過程衅金，直至圖中所有頂點都被訪問過為止噪伊。
算法執(zhí)行過程：選取一個頂點，訪問之氮唯，然后檢查這個頂點的所有鄰接頂點酥宴，遞歸訪問其中未被訪問過的頂點。

2.廣度優(yōu)先搜索遍歷BFS

Breadth First Search
圖的廣度優(yōu)先搜索遍歷BFS類似于樹的層次遍歷您觉。它的基本思想是：首先訪問起始頂點v拙寡，然后選取與v鄰接的全部頂點w1,w2...wn進(jìn)行訪問，再依次訪問與w1,w2,....wn鄰接的全部頂點（已經(jīng)訪問過的除外）琳水，以此類推肆糕，直到所有頂點都被訪問過為止。
廣度優(yōu)先搜索遍歷圖時在孝，需要用到一個隊列（二叉樹的層次遍歷也要用到隊列）诚啃，算法執(zhí)行過程可簡單概括如下：

1. 任務(wù)圖中一個頂點訪問，入隊私沮，并將這個頂點標(biāo)記為已訪問始赎。
2. 當(dāng)隊列不空時循環(huán)執(zhí)行：出隊，依次檢查出隊頂點的所有鄰接頂點，訪問沒有被訪問過的鄰接頂點并將其入隊造垛。
3. 當(dāng)隊列為空時跳出循環(huán)魔招，廣度優(yōu)先搜索即完成。

生成樹和最小生成樹

一個連通圖的生成樹是該連通圖的一個極小連通子圖五辽，它含有圖中全部頂點办斑，但只有構(gòu)成一棵樹的（n-1）條邊。
對于一個帶權(quán)的連通無向圖的不同生成樹杆逗，各棵樹的邊上的權(quán)值之和可能不同乡翅，邊上的權(quán)值之和最小的樹稱為最小生成樹。

構(gòu)成最小生成樹的主要有：1.普里姆算法prim 2.克魯斯卡爾算法kruskal

prim算法

對于圖G而言罪郊，V是所有頂點的集合蠕蚜；現(xiàn)在，設(shè)置兩個新的集合U和T悔橄，其中U用于存放G的最小生成樹中的頂點波势，T存放G的最小生成樹中的邊。 從所有u?U橄维，v?(V-U) (V-U表示出去U的所有頂點)的邊中選取權(quán)值最小的邊(u, v)尺铣，將頂點v加入集合U中，將邊(u, v)加入集合T中争舞，如此不斷重復(fù)凛忿，直到U=V為止，最小生成樹構(gòu)造完畢竞川，這時集合T中包含了最小生成樹中的所有邊店溢。

kruskal算法

克魯斯卡爾(Kruskal)算法，是用來求加權(quán)連通圖的最小生成樹的算法委乌。
基本思想：按照權(quán)值從小到大的順序選擇n-1條邊床牧，并保證這n-1條邊不構(gòu)成回路。
具體做法：首先構(gòu)造一個只含n個頂點的森林遭贸，然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中戈咳，并使森林中不產(chǎn)生回路，直至森林變成一棵樹為止壕吹。

最短路徑

在無權(quán)圖中著蛙，把路徑長度最短（即經(jīng)過的邊數(shù)最少）的那條路徑叫做最短路徑，其路徑長度叫做最短路徑長度或最短距離耳贬。
在帶權(quán)圖中踏堡，把帶權(quán)路徑長度最短的那條路徑稱為最短路徑，其路徑長度（權(quán)值之和）稱為最短路徑長度或者最短距離咒劲。
求圖的最短路徑長度的問題分為兩個方面：1.求圖中的一個頂點到其余各頂點的最短路徑(dijkstra迪杰斯特拉算法)
2.求圖中每對頂點之間的最短路徑（floyd算法）

迪杰斯特拉算法

迪杰斯特拉算法是典型的最短路徑算法顷蟆，用于計算一個節(jié)點到其他節(jié)點的最短路徑
它的主要特點是以起始點為中心向外層層擴展（廣度優(yōu)先搜索思想）诫隅，直到擴展到終點為止。

基本思想

通過Dijkstra計算圖G中的最短路徑時帐偎，需要指定起點s(即從頂點s開始計算)逐纬。
此外，引進(jìn)兩個集合S和U肮街。S的作用是記錄已求出最短路徑的頂點(以及相應(yīng)的最短路徑長度)，而U則是記錄還未求出最短路徑的頂點(以及該頂點到起點s的距離)判导。
初始時嫉父，S中只有起點s；U中是除s之外的頂點眼刃，并且U中頂點的路徑是"起點s到該頂點的路徑"绕辖。然后，從U中找出路徑最短的頂點擂红，并將其加入到S中仪际；接著，更新U中的頂點和頂點對應(yīng)的路徑昵骤。 然后树碱，再從U中找出路徑最短的頂點，并將其加入到S中变秦；接著成榜，更新U中的頂點和頂點對應(yīng)的路徑。 ... 重復(fù)該操作蹦玫，直到遍歷完所有頂點赎婚。

操作步驟

(1) 初始時，S只包含起點s樱溉；U包含除s外的其他頂點挣输，且U中頂點的距離為"起點s到該頂點的距離"[例如，U中頂點v的距離為(s,v)的長度福贞，然后s和v不相鄰撩嚼，則v的距離為∞]。
(2) 從U中選出"距離最短的頂點k"挖帘，并將頂點k加入到S中绢馍；同時，從U中移除頂點k肠套。
(3) 更新U中各個頂點到起點s的距離舰涌。之所以更新U中頂點的距離，是由于上一步中確定了k是求出最短路徑的頂點你稚，從而可以利用k來更新其它頂點的距離瓷耙；例如朱躺，(s,v)的距離可能大于(s,k)+(k,v)的距離。
(4) 重復(fù)步驟(2)和(3)搁痛，直到遍歷完所有頂點长搀。

迪杰斯特拉算法示例.png

弗洛伊德算法

迪杰斯特拉算法是求圖中某一頂點到其余各頂點的最短路徑，如果求圖中任意一對頂點間的最短路徑鸡典，則通常用弗洛伊德算法源请。

基本思想

通過Floyd計算圖G=(V,E)中各個頂點的最短路徑時，需要引入一個矩陣S彻况，矩陣S中的元素a[i][j]表示頂點i(第i個頂點)到頂點j(第j個頂點)的距離谁尸。
假設(shè)圖G中頂點個數(shù)為N，則需要對矩陣S進(jìn)行N次更新纽甘。初始時良蛮，矩陣S中頂點a[i][j]的距離為頂點i到頂點j的權(quán)值；如果i和j不相鄰悍赢，則a[i][j]=∞决瞳。 接下來開始，對矩陣S進(jìn)行N次更新左权。第1次更新時皮胡，如果"a[i][j]的距離" > "a[i][0]+a[0][j]"(a[i][0]+a[0][j]表示"i與j之間經(jīng)過第1個頂點的距離")，則更新a[i][j]為"a[i][0]+a[0][j]"赏迟。 同理胸囱，第k次更新時，如果"a[i][j]的距離" > "a[i][k]+a[k][j]"瀑梗，則更新a[i][j]為"a[i][k]+a[k][j]"烹笔。更新N次之后，操作完成抛丽！

弗洛伊德算法示例.png

初始狀態(tài)：S是記錄各個頂點間最短路徑的矩陣谤职。
第1步：初始化S。
矩陣S中頂點a[i][j]的距離為頂點i到頂點j的權(quán)值亿鲜；如果i和j不相鄰允蜈，則a[i][j]=∞。實際上蒿柳，就是將圖的原始矩陣復(fù)制到S中饶套。
注:a[i][j]表示矩陣S中頂點i(第i個頂點)到頂點j(第j個頂點)的距離。
第2步：以頂點A(第1個頂點)為中介點垒探，若a[i][j] > a[i][0]+a[0][j]妓蛮，則設(shè)置a[i][j]=a[i][0]+a[0][j]。
以頂點a[1]6圾叼，上一步操作之后蛤克，a[1][6]=∞捺癞；而將A作為中介點時，(B,A)=12构挤，(A,G)=14髓介，因此B和G之間的距離可以更新為26。
同理筋现，依次將頂點B,C,D,E,F,G作為中介點唐础，并更新a[i][j]的大小。