在這裡獲取圖形資料結構的要點...

此部落格適合那些想要了解概念要點而不是拐彎抹角的開發人員。我們將在這篇文章中了解圖資料結構。讓我們開始吧。

什麼是圖表？

圖是非線性資料結構，由邊和節點兩個部分組成。

節點是：-

1. 圖形的基本單位，
2. 也稱為一個或多個頂點，以及
3. 可以帶標籤或不帶標籤。

邊緣是:-

1. 兩個節點之間的連接，
2. 也稱為弧線，以及
3. 可以帶標籤或不帶標籤。

圖表類型：-

1. 空圖：沒有邊，
2. 三元圖：只有一個節點，
3. 循環圖：至少包含一個循環，
4. 循環圖：所有節點相連構成一個循環，
5. 有向圖：它的邊有方向，
6. 無向圖：它的邊沒有任何方向，
7. 加權圖：為每條邊分配一些值，
8. 連通圖：我們可以從一個節點存取任何其他節點（它不必是唯一的邊），
9. 未連接圖：某節點至少有一個節點斷開連接，
10. 正規圖：每個頂點都有相同數量的鄰居，
11. 完全圖：每個節點都透過唯一的邊連接到另一個節點，
12. 有向無環圖：沒有環的有向圖，
13. 二部圖：它的節點可以分成2個集合，使得集合之間不存在邊。

我們如何儲存圖表？

有2種方法：

1. 鄰接矩陣，以及
2. 鄰接矩陣

鄰接矩陣是表示圖形資料結構的二維矩陣。行和列代表節點，矩陣中的值代表邊。

在上圖中，4 個節點透過邊連接。節點A與所有節點相連，因此在A（行或列）與其他節點的行或列相交的單元格中，該值被加為1。節點 B 僅連接到節點 A，導致節點 B 與節點 A 相交的單元格中值為 1，其他單元格值為 0。

為相鄰矩陣新增或刪除邊的時間複雜度為 O(1)。它可以在以下情況下使用：-

1. 圖表具有最大可能的邊，
2. 沒有記憶體限制，且
3. 此圖具有複雜的結構。

相鄰清單借助多個鍊錶或陣列來儲存圖形。行代表節點（檢查下圖），行中的值代表鄰居。

上圖中，有 5 個節點。節點 A 連接到節點 B 和節點 D，這就是為什麼第一個陣列具有這些值的原因。類似地，節點 B 連接到節點 A、節點 C、節點 D 和節點 E，因此第二個陣列在第二個陣列中具有這些節點。

檢索或刪除邊的時間複雜度為 O(n)，增加邊的時間複雜度為 O(1)。相鄰列表可以在以下情況下使用： -

1. 節點的邊較少，
2. 存在記憶體限制，且
3. 圖表不太複雜。

圖：相鄰列表和相鄰矩陣之間的視覺比較。

圖表的用例

圖資料結構的一個流行範例是：在足球場上，每個球員都可以被視為一個節點，他們的互動代表邊。

圖的使用場景與前面的範例類似，例如：-

1. 在每個人都是節點的社群網路中，
2. 在以 PC 與路由器為節點的電腦網路中，
3. 交通網等等...

以上是在這裡獲取圖形資料結構的要點...的詳細內容。更多資訊請關注PHP中文網其他相關文章！