圖的表示（Adjacency List + Adjacency Matrix）

1 圖的表示

1、對于圖 G = （ V ， E ） G = （V，E） G=（V，E），存在兩種标準表示方法

• 鄰接連結清單：由一個包含 ∣ V ∣ |V| ∣V∣ 條連結清單的數組構成，每個節點有一條連結清單；
• 鄰接矩陣；
• 兩種表示方法既可表示無向圖，也可表示有向圖；

2、選擇鄰接連結清單的情況

• 稀疏圖（邊的條數 ∣ E ∣ |E| ∣E∣ 遠遠小于 ∣ V ∣ 2 |V|^2 ∣V∣2 的圖）一般采用鄰接連結清單方式表示；

3、選擇鄰接矩陣的情況

• 稠密圖（邊的條數 ∣ E ∣ |E| ∣E∣ 接近 ∣ V ∣ 2 |V|^2 ∣V∣2 的圖）一般采用鄰接矩陣方式表示；
• 鄰接矩陣表示法更為簡單，當圖規模較小時，一般采用鄰接矩陣方式表示；
• 如果需要快速判斷兩個節點之間是否相連，一般采用鄰接矩陣方式表示；

2 鄰接連結清單（Adjacency List）

• 不論是有向圖還是無向圖，鄰接連結清單的存儲空間需求均為 O ( V + E ) O(V + E) O(V+E) ；
• 存在一個缺陷：無法快速判斷一條邊 ( u , v ) (u, v) (u,v) 是否是圖中的一條邊（或快速擷取一條邊的權重）；

3 鄰接矩陣（adjacency Matrix）

• 不管一個圖中存在多少條邊，鄰接矩陣的空間需求均為 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)；
• 可以快速判斷一條邊 ( u , v ) (u, v) (u,v) 是否是圖中的一條邊（或快速擷取一條邊的權重）