1、圖的表示
圖的表示
G = ( V , E ) G=(V,E) G=(V,E)
圖G由結點的集合V 和 邊的集合E 組成
可以用兩種方法表示，一種是鄰接連結清單（下圖b），一種是鄰接矩陣（下圖c）。
鄰接連結清單一般用于表示稀疏圖（邊數 ∣ E ∣ |E| ∣E∣遠小于 ∣ V ∣ 2 |V|^2 ∣V∣2），預設都使用鄰接連結清單表示。在稠密圖（ ∣ E ∣ |E| ∣E∣接近 ∣ V ∣ 2 |V|^2 ∣V∣2）的情況下，傾向使用鄰接矩陣。
無向圖：
有向圖：
鄰接連結清單表示
由一個連結清單數組 A d j Adj Adj組成，數組大小為 ∣ V ∣ |V| ∣V∣，連結清單 A d j [ u ] Adj[u] Adj[u]存儲了結點 u u u出發的邊的終點。
比如上面無向圖中，從結點1出發有兩條邊，邊的終點分别是2和4，反應到鄰接連結清單中就是 A d j [ 1 ] Adj[1] Adj[1]存儲了兩個節點2和4。
鄰接連結清單需要的存儲空間為 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)
鄰接矩陣表示
由一個 ∣ V ∣ × ∣ V ∣ |V|×|V| ∣V∣×∣V∣的矩陣 A = ( a i j ) A=(a_{ij}) A=(aij)表示，并滿足以下條件：
a i j = { 1 i f ( i , j ) ∈ E , 0 o t h e r , a_{ij} = \left \{ \begin{aligned} & 1 & if (i, j) \in E, &\\ & 0 & other, & \end{aligned} \right. aij={10if(i,j)∈E,other,
當邊有權重時， a i j a_{ij} aij可以存儲權重值。
鄰接矩陣需要的存儲空間為 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)
一些術語
一個結點的出度為，從這個結點觸發的邊的個數。
一個結點的入度為，到達這個結點的邊的個數。
2、深度優先搜尋
基本思想：盡可能的深入。總是對最近發現的結點 v v v出發的邊進行探索，直到結點 v v v出發的邊全部被發現時，回溯到 v v v的前驅結點繼續探索，直到從源節點出發所有可以到達的結點都被發現。這時如果還有未被搜尋的結點，則再随機找一個未被搜尋的結點作為源節點進行搜尋。
因為可能從一個源節點出發不能搜尋到所有結點，是以深度優先搜尋會産生多個深度優先樹組成深度優先深林。
輔助的給每個結點加入四個屬性：
- c o l o r color color：白色表示還未被搜尋，灰色表示已被發現但出發的邊還沒搜尋完，黑色表示已被發現并且出發的邊已被搜尋完
- d d d：該節點的發現時間
- f f f：該結點出發搜尋結束的時間
- π π π：該結點的前驅（結點第一次被發現時，正在查詢的結點）
下面是深度優先搜尋的僞代碼和事例：
結點中的x/y表示該結點的發現時間為x，完成時間為y
圖中樹邊被标記為灰色，向前，橫向，向前的邊分别被标記為B, C, F
深度優先搜尋的性質
（1）括号花定理
如上圖b所示，每個結點的發現時間和完成時間組成一個括号花結構。
對于兩個結點u和v，如果區間[u.d, u.f] 和 [v.d, v.f] 不相交，則u不是v的後代，v也不是u的後代；
如果[u.d, u.f] 包含在 [v.d, v.f] 内，則u是v後代，反之亦然。
（2）白色路徑定理
如果結點v是u的後代，當u.d時間時，存在一條從u到v全部由白色結點組成的路徑。
3、廣度優先搜尋
基本思路：利用一個隊列，首先将頭結點插入隊列，循環的取出隊列中的一個結點，并
将于該結點相連的結點加入隊列，直到隊列變空，搜尋結束。
輔助的給每個結點加入三個屬性：
- color：白色表示還未被搜尋，灰色表示加入隊列，黑色表示從隊列裡出來
- d：該節點在第幾輪被發現
- ππ：該結點的前驅（結點第一次被發現時，正在查詢的結點）
下面是廣度優先搜尋的僞代碼和示例：
廣度優先搜尋的性質
（1）最短路徑
從某個結點u做廣度優先搜尋，可以找出這個結點到其他結點的最短路徑。
結點v和結點u的最短路徑距離為v.d
從結點v開始 循環列舉前驅結點，就是結點v和結點u的最短路徑中經過的結點。
（2）廣度優先樹
廣度優先搜算中，我們在π屬性中存儲了每個結點的前驅結點，另前驅結點作為該結點的父節點，我們可以得到一個廣度優先樹。發現新結點的邊為樹邊。