DSA 圖
圖
圖是一種非線性資料結構，由頂點（節點）和邊組成。
頂點，也稱為節點，是圖中的一個點或物件，而邊用於連線兩個頂點。
圖是非線性的，因為與陣列或連結串列等線性資料結構不同，圖結構允許我們有多條路徑從一個頂點到達另一個頂點。
圖用於表示和解決資料包含物件及其之間關係的問題，例如：
- 社交網路：每個人是一個頂點，而關係（如友誼）是邊。演算法可以推薦潛在的朋友。
- 地圖和導航：地點，如城鎮或公交車站，儲存為頂點，道路儲存為邊。當儲存為圖時，演算法可以找到兩個地點之間的最短路徑。
- 網際網路：可以表示為一個圖，網頁是頂點，超連結是邊。
- 生物學：圖可以模擬神經網路或疾病傳播等系統。
圖的屬性
使用下面的動畫來了解不同的圖屬性，以及這些屬性如何組合。
加權圖是指邊具有值的圖。邊的權重值可以表示距離、容量、時間或機率等。
連通圖是指所有頂點都透過邊以某種方式連線的圖。不連通的圖是具有孤立（不相交）子圖或單個孤立頂點的圖。
有向圖，也稱為圖，是指頂點對之間的邊具有方向。邊的方向可以表示層次結構或流動。
迴圈圖的定義取決於它是否有向
- 有向迴圈圖是指您可以沿著有向邊沿著一條路徑前進，該路徑形成一個迴圈。移除動畫中從 F 到 G 的有向邊，有向圖就不再是迴圈圖了。
- 無向迴圈圖是指您可以在不使用同一條邊兩次的情況下，回到您開始的同一個頂點。上面的無向圖是迴圈的，因為我們可以在不重複使用相同邊的情況下，從頂點 C 開始並最終回到頂點 C。
自環，也稱為自我迴圈，是從同一頂點開始並結束於同一頂點的邊。自環是僅由一條邊組成的迴圈。透過在動畫中頂點 A 新增自環，圖就變成了迴圈圖。
圖的表示
圖的表示告訴我們圖是如何儲存在記憶體中的。
不同的圖表示可以
- 佔用更多或更少的空間。
- 搜尋或操作速度更快或更慢。
- 根據我們擁有的圖的型別（加權、有向等）以及我們想用圖做什麼，而更適合。
- 比其他表示更容易理解和實現。
下面是對不同圖表示的簡要介紹，但在本教程接下來的部分，我們將使用鄰接矩陣作為圖的表示，因為它易於理解和實現，並且適用於本教程中的所有相關情況。
圖的表示儲存有關哪些頂點是相鄰的以及頂點之間的邊是如何連線的資訊。如果邊是有向的或加權的，圖的表示會略有不同。
如果兩個頂點之間存在邊，則它們是相鄰的或鄰居。
鄰接矩陣圖表示
鄰接矩陣是我們將在本教程中使用的圖表示（結構）。
如何實現鄰接矩陣將在下一頁展示。
鄰接矩陣是一個二維陣列（矩陣），其中索引 (i,j) 處的單元格儲存有關從頂點 i 到頂點 j 的邊資訊。
下面是一個帶有鄰接矩陣表示的圖。
及其鄰接矩陣
上面的鄰接矩陣表示一個無向圖，因此值“1”僅表示邊的位置。此外，鄰接矩陣中的值是對稱的，因為邊是雙向的（無向圖）。
要建立帶有鄰接矩陣的有向圖，我們必須透過在正確索引 (i,j) 處插入值來決定邊的起點和終點。要表示加權圖，我們可以使用比“1”更大的值放入鄰接矩陣。
下面是一個帶有鄰接矩陣表示的有向加權圖。
及其鄰接矩陣。
在上面的鄰接矩陣中，索引 (0,1) 處的值 3 表示從頂點 A 到頂點 B 有一條邊，該邊的權重為 3。
正如您所見，權重直接放置在對應邊的鄰接矩陣中，對於有向圖，鄰接矩陣不必是對稱的。
鄰接表圖表示
如果我們的圖是“稀疏”的，並且有許多頂點，那麼與使用鄰接矩陣相比，使用鄰接表可以節省空間，因為鄰接矩陣將為不存在的邊保留大量記憶體用於空陣列元素。
“稀疏”圖是指每個頂點只與圖中的一小部分其他頂點有邊的圖。
鄰接表有一個包含圖中所有頂點的陣列，並且每個頂點都有一個連結串列（或陣列）儲存該頂點的邊。
及其鄰接表。
在上面的鄰接表中，頂點 A 到 D 放置在一個數組中，並且陣列中的每個頂點旁邊都寫有其索引。
陣列中的每個頂點都有一個指向連結串列的指標，該連結串列表示該頂點的邊。更具體地說，連結串列包含相鄰（鄰居）頂點的索引。
例如，頂點 A 有一個指向包含值 3、1 和 2 的連結串列的連結。這些值是 A 的相鄰頂點 D、B 和 C 的索引。
鄰接表也可以表示有向加權圖，如下所示：
及其鄰接表。
在上面的鄰接表中，頂點儲存在陣列中。每個頂點都有一個指向連結串列的指標，其中邊儲存為 i,w，其中 i 是邊指向的頂點索引，w 是該邊的權重。
例如，節點 D 有一個指向連結串列的指標，該連結串列有一個指向頂點 A 的邊。值 0,4 表示頂點 D 有一條指向索引為 0（頂點 A）的頂點邊的邊，該邊的權重為 4。
