G=（V,E）由頂點（vertex）集合V和邊（edge）集合E組成。
邊有兩個頂點構成，還有可能有權，路徑是一個頂點序列w1，w2，…wn，路徑的長是路徑上的邊數，等于n-1。
包括有向圖和無向圖，有向無圈圖簡稱DAG（Directed Acyclic Graph） 。
如果一個無向圖中從每一個頂點到每個其他頂點都存在一條路徑，稱該無向圖是連通的。
具有這樣性質的有向圖稱強連通圖，如果一個有向圖不是強連通的，但是它的基礎圖（即去掉方向變成無向圖）是連通的，那麼稱該有向圖是弱連通圖。
完全圖是其每一對頂點間都存在一條邊的圖。
1.圖的表示
鄰接矩陣，用二維數組，對于每條邊（u,v），設定A[u][v]=1或者權重，否則等于0。
該表示法空間需求是O(|v|^2)，如果圖的邊較少（稀疏），則數組大部分都是0，代價很大。
如果是稀疏圖，可以用鄰接表，即對每一個頂點，用一個連結清單存放所有鄰接的頂點。空間需求是O(|E|+|V|)。
如果需求中頂點名字不是數字，一般将名字散列成數字（維護一個map或者用struct儲存資料），然後再用數字進行操作。
2.拓撲排序（針對DAG）
針對有向無圈圖（DAG）的頂點的一種排序，它使得如果存在一條從Vi到Vj的路徑，那麼在排序中Vj出現在Vi的後面。
一個簡單的求拓撲排序的算法是先找出任意一個沒有入度的頂點，然後顯示出該頂點，并将它和它的邊一起從圖中删除。然後，對圖的其餘部分應用同樣的辦法處理。
可以使用一個隊列，初始狀态把圖中入度為0的點全部入隊，然後每次pop一個頂點，并且減少該頂點的鄰接頂點的入度，若減少後入度為0則入隊，直到隊列為空。最後判斷輸出點數是否等于頂點數，若不是則表示該圖有環。
3.最短路徑
針對有向圖圖，求兩個頂點間權重和最小的路徑，不考慮存在負值權重的圖，因為如果存在負值，路徑可以無限長（一直在負值的路徑上循環走）。
3.1 無權最短路徑
隻對包含在路徑中的邊數有關系，是以可以設定所有的邊權1。
可以用廣度優先搜尋（Breadth-First Search）的方法：按層處理頂點，距離開始點最近的頂點首先被指派，最遠的那些頂點最後被指派。（樹的層次周遊）
同樣使用一個隊列，首先起點入隊，起點距離=0。然後每次pop一個頂點，周遊該頂點的鄰接點，如果鄰接點中的距離沒有沒更新（依然是初始化值Infinity），則更新該鄰接點的距離=目前頂點距離+1，記錄path值=目前頂點，然後該鄰接點入隊。如果已經更新了不做任何操作。
3.2 帶權圖最短路徑 Dijkstra算法
每個階段選擇一個頂點v，它在所有未知頂點中具有最小的dv，同時算法聲明s到v的最短路徑是已知的，階段的其餘部分由dw值的更新工作組成。
假設頂點開始節點s是v1，第一個選擇v1，路徑長為0，标記為已知。然後調整鄰接到v1的頂點的距離。
下一步選v4并标記為已知，更新v4的鄰接點v3，v5，v6，v7（圖9-23）。
接着選v2，v4是已知的是以不更新。v5目前值<經過v2的值（2+10=12），是以不更新。（圖9-24）
下一個選v5，v7鄰接但是不更新（3+6>5)。然後選v3，更新v6.（圖9-25）
接下來選v7，更新v6（5+1=6）。（圖9-26）
最後選擇v6。（圖9-27）
每次查找需要O(|V|)，整個算法需要O(|V|^2)，每次更新dw常數時間，每條邊最多有一次更新，總計O(|E|)，是以總得運作時間是O(|E|+|V|^2)=O(|V|^2)。如果圖是稠密的，邊數|E|約=|V|^2，算法基本上最優，運作時間與邊數成線性關系。
如果圖稀疏的，邊數|E|約=|V|，算法就比較慢，這種情況下距離需要存儲在優先隊列中。
但是使用優先隊列需要更新d的值，需要使用decreaseKey，這個至少std自帶的優先隊列中不提供，是以很難辦。
一個解決方法是插入的時候把舊值和新值同時插入優先隊列中，這樣隊列中每個頂點就可能有多于一個的代表，并且DeleteMin的時候要循環知道一個未知的頂點合并為止。
除了優先隊列，還有配對堆的實作和斐波那契堆的實作。（不太清楚，或許以後了解了會補上）
3.3 無圈圖
如果圖是無圈的，頂點選取法則可以用來改進Dijkstra算法，新法則以拓撲順序選擇頂點。由于選擇和更新可以在拓撲順序執行的時候進行，是以算法能夠一趟完成。
因為一個頂點v被選擇以後，按照拓撲排序的法則，它沒有從未知頂點發出的進入邊，是以它的距離d可以不再被降低。這種選取法則不需要優先隊列。
無圈圖一個重要的用途是關鍵路徑分析法，下圖中每個節點表示一個必須執行的動作以及完成動作所花費的時間，稱為動作節點圖。
這種類型的圖用來模拟方案的建構。比如方案最早完成時間是何時？從圖中可以看出，沿路徑A、C、F、H需要10個時間機關。另一個問題是哪些動作可以延遲，延遲多長而不至于影響最少完成時間。A、C、F、H中的任一個延遲都影響最少完成時間，而B可以被延遲2個時間機關而不至于影響最後完成時間。
4.網絡流問題
給定邊容量，求發點s到收點t的最大流量。下圖最大流是5。
5.最小生成樹
一個無向圖的最小生成樹就是由該圖的那些連接配接G的所有頂點的邊構成的樹，且權重之和最低。
5.1 Prim算法
算法的每個階段，都把頂點集合分成已經添加到樹上的頂點集和未加到樹上的頂點集，然後選擇邊（u，v），使得u在樹上而v不在樹上且（u，v）的權重最小，然後把v和邊（u，v）加到樹上。
5.2 Kruskal算法
每個階段都按照最小的權選擇邊，并且當所選的邊不産生圈的時候就把它作為取定的邊。
起初每個頂點是在它自己的集合中，如果u和v在同一個集合中，那麼連接配接它們的邊就要放棄，因為他們已經連通了。如果這兩個頂點不在集合中，加入該邊，并合并兩個頂點的集合。
6. 深度優先搜尋
DFS可以生成深度優先生成樹。
周遊過程中處理（v，w）時，如果w是未被标記的，就用樹的一條邊表示。如果處理（v，w）時w已經被标記了，就用虛線表示，稱之為背向邊（虛線其實不是樹的一部分）。
6.1.歐拉回路
給出一個無向圖，在圖中找出一條路徑，使得該路徑對圖的每條邊恰好通路一次。（附加問題：結束的頂點要與開始的頂點一樣）
充分必要條件：
圖中每一個頂點的度（邊的條數）必須是偶數。
思路：
從起點開始用DFS，每次回到起點時結束。然後把路徑上的邊從原圖删掉，然後再對剩下圖選之前路徑上的有尚未通路的邊的第一個頂點，進行另外一次DFS。并且把第二次DFS路徑拼接到第一次DFS上。繼續該過程直到所有的邊都被周遊。