圖的定義
圖就是由頂點(diǎn)碉咆、邊骏庸、權(quán)重的集合。
頂點(diǎn)
頂點(diǎn)一般表示對象屬性特征
邊
邊表示對象事物的關(guān)系
權(quán)重
權(quán)重表示關(guān)系的比重
度
連接某一個頂點(diǎn)的邊個數(shù)之和
若邊一旦有方向景东，就把度分類成入度和出度
圖的表示
鄰接列表
每一個頂點(diǎn)會存儲一個從它這里開始的邊的列表
鄰接列表只描述出度的邊，即指向該頂點(diǎn)之外的邊和頂點(diǎn)
如下圖：
AdjacencyList.png
鄰接矩陣
矩陣行和列都表示頂點(diǎn)捆探，由兩個頂點(diǎn)共同決定兩個頂點(diǎn)是否相連然爆、如果相連這個值表示的是相連邊的權(quán)重。
如下圖：
AdjacencyMatrix.png
小結(jié)
在 稀疏圖的情況下黍图，每一個頂點(diǎn)都只會和少數(shù)幾個頂點(diǎn)相連曾雕，這種情況下相鄰列表是最佳選擇。如果這個圖比較密集雌隅，每一個頂點(diǎn)都和大多數(shù)其他頂點(diǎn)相連翻默，那么相鄰矩陣更合適。
常用的圖的遍歷算法
- 廣度優(yōu)先算法
- 深度優(yōu)先算法
- 最小生成樹算法
- 最小路徑算法
鏈接：
http://www.reibang.com/p/70952b51f0c8
參考
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Graph
