圖論101

The City of Königsberg, Historic Cities Research Project

圖論是數學的一個非常廣泛的分支，非常適用於現實世界中的問題。 最初，圖論是"發明"來解決現實問題的，此後，它像所有其他數學分支一樣，被抽象數學家所劫持。

在本教程和後續教程中，我們將介紹一些圖論算法及其在Python中的實現。 現在，回到主題。

什麼是圖？

簡而言之，圖是一組頂點/節點和邊。 如果您對" set"不滿意，請用collection代替。

A simple graph showing connections among people. Image From William Fiset

什麼是頂點/節點？

在上圖中，頂點/節點將是人物。

頂點是圖的基本單位。 它幾乎可以代表任何實體，通常以圓圈表示。

什麼是邊？

在上圖中，連接人的線是邊。

頂點之間的線或連接稱為邊。 它可以表示頂點之間的任何類型的關係。

圖的類型

有向圖

邊上具有方向的圖稱為有向圖。 它可以用來顯示與前輩（從父母到孩子的箭頭）或祖先（從孩子到父母的箭頭）的關係。

A Directed Graph. Image From William Fiset

無向圖

邊上沒有方向的邊的圖稱為無向圖。 它可用於顯示雙向道路。

A Un-Directed Graph. Image From William Fiset

加權圖

邊上帶有數字的圖形，代表交易成本，旅途公平，城市之間的距離等。它可以具有任何類型的邊。

A Weighted Graph. Image From William Fiset

樹

沒有循環的無向圖是一棵樹。 在這裡，循環意味著只有一種方法可以通過跟隨給定其他節點的邊緣來到達節點。

一棵樹的所有節點都通過一條邊連接到其他某個節點，並且有N個節點的N-1個邊。

Trees. Image From William Fiset

表示圖

A Graph Example. Image From William Fiset

表示圖形的方法有很多，最常見的兩種是：

鄰接矩陣

假設圖中有N個節點。 我們可以使用具有N行和N列的矩陣來表示它，其中該矩陣的行和列將代表一個節點，並且其中的條目代表有向邊（有或沒有權重）。

它們形成代表行的節點到代表列的節點。 通常，0或無窮大用於表示節點之間沒有邊緣。 在Python中，鄰接矩陣可以表示為：

<code>idxMap = {"A":0, "B":1, "C":2, "D":3}
adjacencyMatrix=[
[0, 4, 1, 9],  # A
[3, 0, 6, 11], # B
[4, 1, 0, 2],  # C
[6, 5, -4, 0]  # D
]
#A  B  C  D/<code>

鄰接表

類似地，對於N個節點的圖，我們可以使用鄰接表來表示該圖，其中節點的所有邊都保留在元組列表（節點，權重）中。 在python中，它可以表示為：

<code>idxMap = {"A":0, "B":1, "C":2, "D":3}
adjacencyMatrix=[
[0, 4, 1, 9],  # A
[3, 0, 6, 11], # B
[4, 1, 0, 2],  # C
[6, 5, -4, 0]  # D
]
#A  B  C  D/<code>

嵌套字典

我使用嵌套字典（這就是我所說的）和帶集合的字典（如果節點沒有權重的邊）來表示圖。

<code>Graph = { 

"A", {"B":4,"C":1},
"B", {"C":6},
"C", {"A":4,"B":1, "D":2},
"D", {},
}/<code>

在下一篇文章中，我將使用不同的方法發佈精心設計的圖類的Python代碼，我們將使用該代碼來實現圖算法。

(本文翻譯自sleepingFish的文章《Graph Theory Algorithms "Simplified"》，參考：https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222)

閱讀更多 聞數起舞 的文章

關鍵字: 數學 算法 Python