圖是由頂點的有窮非空集合和頂點之間的邊的集合組成幽纷，通常表示為：G（V式塌，E），其中友浸，G表示一個圖峰尝，V是圖中的頂點的集合，E是圖G中邊的集合收恢。
- 線性表中的數(shù)據(jù)元素叫元素武学，樹中的數(shù)據(jù)元素叫結(jié)點祭往，圖中的數(shù)據(jù)元素叫頂點。
- 線性表中可以沒有元素火窒，叫空表硼补，樹中可以沒有結(jié)點，叫空樹熏矿，而圖中不能沒有頂點已骇，在定義中，V是頂點的集合曲掰，有窮且非空。
- 線性表中奈辰，相鄰的數(shù)據(jù)元素具有線性關(guān)系栏妖，樹結(jié)構(gòu)中，相鄰兩層的結(jié)點具有層次關(guān)系奖恰，而圖中任意兩個頂點之間都可能有關(guān)系吊趾，頂點之間的邏輯關(guān)系用邊來表示，邊集可以是空的瑟啃。
關(guān)于圖的各種定義：
無向邊&無向圖
若頂點Vi到頂點Vj之間的邊沒有方向论泛，則稱這條邊為無向邊，用無序偶對（Vi蛹屿，Vj）來表示屁奏。如果任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖错负。無向圖表示法：G=（V1坟瓢，{E1}），其中V1={A,B,C,D}犹撒，E1={（A,B）折联，（B,C），（C,D）识颊，（A,C）} (無向邊小括號)
有向邊&有向圖
若頂點Vi到頂點Vj的邊有方向诚镰，稱該邊為有向邊，也叫作弧祥款。使用有序偶<Vi,Vj>表示清笨，Vi為弧尾，Vj為弧頭刃跛。如果任意兩個頂點之間的邊為有向邊函筋，則稱該圖為有向圖。有向圖的表示法：G=（V2奠伪，{E2}）跌帐，其中V2={A,B,C,D}首懈，E2={<A,D>,<B,C>,<C,A>,<B,A>} ( 有向邊尖括號)
相關(guān)術(shù)語
在圖中，如果不存在頂點到自身的邊谨敛，且同一條邊不重復(fù)再出現(xiàn)究履，則稱該圖為 簡單圖
在無向圖中，如果任意兩個頂點之間都存在邊脸狸，則稱該圖為無向完全圖最仑。n的頂點的無向完全圖的邊的數(shù)目：n*(n-1)/2
在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩條弧炊甲，則稱該圖為有向完全圖泥彤。n個頂點的有向完全圖的弧的數(shù)目：n*(n-1)
有些圖的邊或弧具有與他相關(guān)的數(shù)字，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)卿啡，帶權(quán)的圖通常稱為 網(wǎng)吟吝。
圖G=（V，{E}）颈娜，圖G'=(V'剑逃，{E'})，且 V屬于V’官辽，E屬于E'蛹磺，稱G為G'的子圖。
無向圖中同仆，頂點v的度為與該頂點相關(guān)聯(lián)的邊的數(shù)目萤捆，即為TD（v）。圖中邊的數(shù)目為各頂點的度的和的一半俗批。
有向圖中鳖轰，頂點v的度為入度和出度之和，入度為以頂點V為頭的弧扶镀，記作ID（v）蕴侣，出度為以頂點V為尾的弧，記作OD（v）臭觉。有向圖中的邊的數(shù)目為頂點的ID（v）,或者OD（v）昆雀。
圖中頂點V到頂點V'之間的路徑為頂點的序列，對于無向圖該序列中相鄰的點之間的邊屬于無向圖的邊的集合蝠筑，對于有向圖該序列中的相鄰點組成的具有方向性狞膘，屬于有向圖的弧的集合。路徑的長度為弧或邊的數(shù)目什乙。
連通圖相關(guān)術(shù)語
在無向圖中挽封，如果頂點V到頂點V'有路徑，稱為V和V'是連通的臣镣。如果對于圖中任意兩個頂點都是連通的辅愿，則稱該圖為連通圖智亮。
無向圖中的極大連通子圖稱為連通分量，連通分量強調(diào)：
- 要是子圖
- 子圖要是連通的
- 連通子圖含有極大頂點數(shù)
- 具有極大頂點數(shù)的連通子圖包含依附于這些頂點的所有邊
而有向圖中点待，如果對于每一對屬于頂點集的Vi阔蛉，Vj，從Vi到Vj和從Vj到Vi都存在路徑癞埠，則稱該有向圖為強連通圖状原，有向圖中的極大強連通子圖稱作有向圖的強連通分量。
連通圖的生成樹
一個連通圖的生成樹是一個極小的連通子圖苗踪，含有圖中全部的n個頂點颠区，但只有足以構(gòu)成一棵樹的n-1條邊。
如果一個有向圖恰有一個頂點的入度為0通铲，其他頂點的入度均為1毕莱，則是一棵有向樹。一個有向圖由若干有向樹構(gòu)成森林测暗。
圖存儲結(jié)構(gòu)
-
鄰接矩陣
圖的鄰接矩陣存儲方式是用兩個數(shù)組來表示圖央串。一個一維數(shù)組存儲圖中頂點信息磨澡，一個二維數(shù)組（為鄰接矩陣）存儲圖中的邊或弧的信息
無向圖：
有向圖：
image
無向圖的鄰接矩陣是對稱陣碗啄，有向圖的鄰接矩陣不一 定是對稱陣
網(wǎng)中存儲權(quán)值：
image
image -
鄰接表
對于邊數(shù)相對于頂點較少的圖，使用鄰接矩陣會對存儲空間造成一定的浪費稳摄。這時可以采用將數(shù)組與鏈表相結(jié)合的存儲方式稚字，稱為鄰接表。
頂點數(shù)組中存儲頂點信息和一個指向第一個鄰接點的指針厦酬，邊表結(jié)點由存儲某頂點的下標(biāo)和邊表中下一個結(jié)點的指針域構(gòu)成
無向圖鄰接表
有向圖鄰接表
image
有向圖有方向胆描，邊表中可以按照以該頂點的弧尾儲存，或者弧頭存儲
帶權(quán)值的網(wǎng)圖：
image
邊表再添加權(quán)值域存儲權(quán)值 -
十字鏈表
對于有向圖來說仗阅，鄰接鏈表是有缺陷的昌讲。關(guān)心出度問題，想了解入度情況减噪，需要遍歷整個圖短绸。將鄰接鏈表和逆鄰接鏈表結(jié)合。
頂點數(shù)組的數(shù)據(jù)元素除了數(shù)據(jù)域和出度指針域外筹裕，添加入度指針域醋闭，即指向弧頭為該頂點的弧邊結(jié)點
弧邊結(jié)點為兩個數(shù)據(jù)域兩個指針域，數(shù)據(jù)域分別記錄該弧的弧頭和弧尾的頂點下標(biāo)朝卒，指針域一個指向頂點出度的弧证逻，一個指向頂點入度的弧
十字鏈表將鄰接表和逆鄰接表結(jié)合，可以方便找出某一個頂點的入度和出度的弧抗斤，因此在有向圖中囚企，十字鏈表是非常好的數(shù)據(jù)結(jié)構(gòu)丈咐。 -
鄰接多重表
對于無向圖的鄰接表，若關(guān)注的重點是頂點洞拨，那么鄰接表可以滿足要求扯罐，若是更關(guān)注邊的操作，如對已訪問的邊做標(biāo)記烦衣，刪除一條邊等歹河，那么使用鄰接表就會相對比較麻煩，要找到這條邊對應(yīng)的兩個節(jié)點進行處理花吟。使用鄰接多重表結(jié)構(gòu)：
| ivex | ilink | jvex | jlink |
ivex和jvex是與某條邊依附的兩個頂點在頂點表中的下標(biāo)秸歧，ilink是頂點ivex所指的下一條邊，jlink是頂點jvex所指的下一條邊衅澈，在構(gòu)造圖的邊結(jié)點時采用頭插法键菱，這樣每個邊結(jié)點會被兩個指針?biāo)福?br> -
邊集數(shù)組
邊集數(shù)組有兩個一維數(shù)組構(gòu)成。一個存儲頂點信息今布，一個存儲邊的信息经备，邊數(shù)組的每個數(shù)據(jù)元素由每條邊的起點下標(biāo)和終點下標(biāo)以及權(quán)重組成。邊集數(shù)組關(guān)注的是邊的集合部默，邊集數(shù)組中查找頂點的度需要掃描整個邊數(shù)組侵蒙，效率不高，更適合對邊依次處理的操作傅蹂，不適合對頂點的相關(guān)操作纷闺。
圖的遍歷
從圖中某一頂點出發(fā)訪遍圖中其與頂點，且使每一個頂點僅被訪問一次份蝴，該過程叫做圖的遍歷
深度優(yōu)先遍歷DFS
也稱為深度優(yōu)先搜索犁功，簡稱DFS。從圖中某個頂點v出發(fā)婚夫，訪問此頂點浸卦，然后從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到案糙。這里是對于連通圖限嫌，若是非連通圖，則對其連通分量扥別進行深度優(yōu)先遍歷侍筛，即在先前一個頂點進行一次深度優(yōu)先遍歷后萤皂，若圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點匣椰，重復(fù)上述過程裆熙，直至圖中所有頂點都被訪問到為止。
深度優(yōu)先其實就是一個遞歸過程，類似一棵樹的前根序遍歷過程入录。
廣度優(yōu)先遍歷BFS
廣度優(yōu)先搜索類似于樹的層序遍歷蛤奥，將與該頂點的鄰接的頂點通過入隊和出隊，完成層序搜索僚稿。
深度優(yōu)先適合有明確的目標(biāo)凡桥，以找到目標(biāo)為主要目的的情況，而廣度優(yōu)先適合在不斷擴大搜索范圍以找到相對最優(yōu)解的情況蚀同。
最小生成樹
一個連通圖的生成樹是一個極小的連通子圖缅刽，包含圖中所有的頂點，只有足以構(gòu)成一棵樹的n-1條邊蠢络。構(gòu)造連通網(wǎng)的最小代價生成樹稱為最小生成樹衰猛。找出最小生成樹的常用算法：
Prim算法
Prim算法從某一頂點開始
- 遍歷該頂點與其他頂點的之間的邊的權(quán)值，并存入權(quán)值數(shù)組
- 并找出其中權(quán)值最小的邊的對應(yīng)頂點刹孔，記錄下該頂點下標(biāo)
- 同時將最小權(quán)值的邊的兩個頂點做標(biāo)記啡省，避免重復(fù)檢索
- 將記錄的頂點與其他頂點的權(quán)值與之前的權(quán)值數(shù)組比較
- 更新權(quán)值數(shù)組，記錄下兩者中較小的權(quán)值髓霞，如果有更新將記錄的頂點的下標(biāo)存入對應(yīng)位置的下標(biāo)數(shù)組
這樣一輪檢測完時卦睹，權(quán)值數(shù)組中儲存的權(quán)值表示與當(dāng)前權(quán)值最小的邊的頂點有鄰接關(guān)系的頂點對應(yīng)的邊的權(quán)值，下標(biāo)數(shù)組中存儲的是與當(dāng)前權(quán)值最小的邊的其中一個頂點鄰接的未檢索的其他頂點方库。對其他頂點重復(fù)進行上述操作结序，時間復(fù)雜度為0(n^2)，針對上圖的Prim算法結(jié)果：
Kruskal算法
Kruskal算法從邊開始薪捍，依次選擇權(quán)值最小的邊來構(gòu)成最小生成樹笼痹，比較重要的兩步：
- 將邊按照權(quán)值進行排序配喳，從權(quán)值最小的邊開始
- 檢查被選擇的邊是否構(gòu)成環(huán)路酪穿，如沒有構(gòu)成環(huán)路，則記錄邊的頂點下標(biāo)晴裹，否則放棄這條邊
因此被济，針對上圖首先按照權(quán)值對邊進行排序，得到：
使用Kruskal算法結(jié)果：
該算法與邊有關(guān)涧团，與判斷環(huán)路相關(guān)的函數(shù)時間復(fù)雜度為loge 只磷，對e條邊的總體時間復(fù)雜度為O(eloge)
對比兩個算法，Kruskal算法針對邊展開泌绣，對于稀疏圖Kruskal的效率會相對較高钮追，而對于稠密圖，即邊比較多的情況下阿迈，Prim算法效率相對較高元媚。
最短路徑問題
對于非網(wǎng)圖，由于沒有權(quán)值，最短路徑即為兩頂點之間經(jīng)過的邊數(shù)最少的路徑刊棕。
對于網(wǎng)圖炭晒，由于帶有權(quán)值，最短路徑即為兩頂點之間經(jīng)過的邊的權(quán)值之和最小的路徑甥角。
Dijkstra算法
Dijkstra算法是從網(wǎng)圖的源點出發(fā)网严，依次計算到每個頂點的最短路徑，直到最后目標(biāo)點嗤无，并記錄路徑的前驅(qū)下標(biāo)震束。
始終由當(dāng)前的已知最短路徑向與之相連的權(quán)值最小的路徑擴散，此前與某一頂點直接相連的權(quán)值已經(jīng)被記錄在權(quán)值和的數(shù)組中当犯，
若在擴散過程中發(fā)現(xiàn)間接路徑的權(quán)值和小于直接路徑的權(quán)值和驴一，則之前的直接路徑就會被間接路徑覆蓋掉，并更新前驅(qū)數(shù)組
這樣就可以找出源點到其他每一個頂點的最小權(quán)值和路徑灶壶。
對于以下的網(wǎng)圖：
使用Djikstra算法得到的結(jié)果：
final數(shù)組用來確定從源點到哪些點的最短路徑已經(jīng)確定
D數(shù)組用來存儲源點到對應(yīng)的點的最短路徑的權(quán)值和
P數(shù)組用來存儲到對應(yīng)路徑的上一個點的下標(biāo)
該算法的時間復(fù)雜度為O（n2）肝断，如果想要找出所有點對其他點的最短路徑，則需要在外層再循環(huán)圖中頂點個數(shù)次驰凛，時間復(fù)雜度為O（n3）
Floyd算法
Floyd算法是通過找出每一個點與下一個點之間的最短距離胸懈，并記錄下標(biāo)，最后得到完整的路徑恰响。
而判斷每一個點與下一個點的最短距離是通過比較起始點到結(jié)束點是直接路徑短還是通過中間點的路徑短趣钱，如果中間距離短就更新起始點到結(jié)束點的記錄的路徑值。由于需要遍歷計算中間點胚宦，以及起始點和結(jié)束點首有，因此需要3層循環(huán)來確定每一個點到另一個點的最短路徑，時間復(fù)雜度為O（n^3）
對于以下網(wǎng)圖：
使用Floyd算法得到的結(jié)果：
AOV網(wǎng)
在一個表示工程的有向圖中枢劝，用頂點表示活動井联，用弧表示活動之間的優(yōu)先級關(guān)系，這樣的有向圖為頂點表示活動的網(wǎng)您旁，稱之為AOV（Activity On VertexNetwork）網(wǎng)烙常。AOV網(wǎng)中的弧表示活動之間存在某種制約關(guān)系。AOV網(wǎng)中不能存在回路鹤盒。
設(shè)G=（V蚕脏，E）是一個具有n個頂點的有向圖，V中的頂點序列V1,V2,……Vn,滿足若從頂點Vi到Vj有一條路徑侦锯，則在頂點序列中頂點Vi必在頂點Vj之前驼鞭。則稱之為這樣的頂點序列為一個拓?fù)湫蛄小?/p>
拓?fù)渑判?br> 拓?fù)渑判蚴菍σ粋€有向圖構(gòu)造拓?fù)湫蛄械倪^程。構(gòu)造時會有兩個結(jié)果尺碰，如果此網(wǎng)的全部頂點都被輸出挣棕，則說明它是不存在回路的AOV網(wǎng)汇竭；如果輸出頂點少了，即便是少了一個穴张，也說明這個網(wǎng)存在回路细燎，不是AOV網(wǎng)。
拓?fù)渑判蛩惴?br>
對AOV網(wǎng)進行拓?fù)渑判虻幕舅枷胧牵簭腁OV網(wǎng)中選擇一個入度為0的頂點輸出皂甘，然后刪去此頂點玻驻，并刪除以此頂點為弧尾的弧，繼續(xù)重復(fù)此步驟偿枕，直到輸出全部頂點或者AOV網(wǎng)中不存在入度為0的頂點為止璧瞬。
對以下有向無環(huán)圖：
構(gòu)建鄰接表：
采用拓?fù)渑判虻玫降慕Y(jié)果：
最開始將入度為0的頂點入棧，即頂點0,1,3渐夸，然后依次出棧嗤锉，同時刪除該點與鄰接點的連接關(guān)系，即將對應(yīng)鄰接點的入度減一墓塌，若果發(fā)現(xiàn)出現(xiàn)新的入度為0的點瘟忱，再次加入到棧頂，直到最終棧中不存在入度為0的點苫幢。 拓?fù)渑判蛘麄€算法访诱，需要遍歷頂點n次得到初次的入度為0的點，然后執(zhí)行入度減一的次數(shù)為邊數(shù)e
因此整個算法的時間復(fù)雜度為O（n+e）
關(guān)鍵路徑
在一個表示工程的帶權(quán)有向圖中韩肝，用頂點表示事件触菜，用有向邊表示活動，用邊上的權(quán)值表示活動的持續(xù)時間哀峻，這種有向圖的邊表示活動的網(wǎng)涡相，稱之為AOE（Activity On Edge）網(wǎng)。AOE網(wǎng)中沒有入邊的頂點稱為始點或源點剩蟀，沒有出邊的頂點稱為終點或匯點催蝗。對于一個工程一般都有一個開始和結(jié)束，因此正常情況下AOE網(wǎng)有一個源點有一個匯點喻旷。
AOE網(wǎng)路徑上的各個活動所持續(xù)的時間之和稱為路徑長度生逸，從源點到匯點具有最大長度的路徑叫關(guān)鍵路徑牢屋。
關(guān)鍵路徑的算法：
找到AOE圖中的每個活動的最早開始時間和最晚開始時間且预，然后比較他們，如果相等就說明這個活動在路徑中沒有空閑時間烙无，則為關(guān)鍵活動锋谐，活動之間的路徑就為關(guān)鍵路徑
對于以下無環(huán)有向圖，先使用拓?fù)湫蛄兴惴ㄇ蟮酶黜旤c的最早開始時間截酷，再根據(jù)拓?fù)湫蛄械姆聪蝽樞蚰嫦蚯蟾黜旤c的最晚開始時間
使用關(guān)鍵路徑算法得到的結(jié)果：
如果某一個工程存在多個關(guān)鍵路徑涮拗，只提高某一條關(guān)鍵路徑上的關(guān)鍵活動效率并不能提高整個工程的工期，必須同時提高在幾條關(guān)鍵路徑上的活動效率。
