圖的表示

1.鄰接矩陣
2.鄰接表

圖的遍歷
DFS(深度優先遍歷)
BFS(廣度優先遍歷)

拓撲排序
最小生成樹
Prim算法

圖可以用G=(V,E)來表示，每個圖都包括一個頂點集合V和一個邊集合E，頂點總數記為|V|，邊總數記為|E|
稀疏圖：邊數較少的圖
密集圖：邊數較多的圖
完全圖：包含所有可能邊的圖
帶權圖：邊上標有權的圖
鄰接點：一條邊所連的兩個頂點
簡單路徑：路徑上不包含重復頂點的圖
回路：將某個頂點連接到本身，且長度大于等于3的路徑
無環圖：不帶回路的圖
圖的表示
圖有兩種常用的表示方法：
1.鄰接矩陣
2.鄰接表
1.鄰接矩陣
使用一個二維矩陣來表示圖:
1.(i,j)=1，表示頂點i到頂點j之間有一條邊（非帶權圖）
2.(i,j)=n，表示頂點i到頂點j之間有一條權重為n的邊（帶權圖）

使用鄰接矩陣的空間代價總是O(|V|^2)
2.鄰接表

鄰接表使用一個頂點指針數組來表示：
1.數組的元素i表示頂點i的指針，它是一個鏈表的頭結點
2.鏈表其余的頂點表示與頂點i之間存在邊的頂點

鄰接表的空間代價與圖中邊的數目和頂點的數目均有關系。每個頂點要占據一個數組元素的位置，且每條邊必須出現在其中某個頂點的邊鏈表中
圖的遍歷
DFS(深度優先遍

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的C++图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。