圖論其實不難入門

對於有多年的程式設計經驗的開發者來說，圖的概念並不陌生。許多頂尖公司在技術面試中測試對圖論的理解。其實，開發者無需處理高階問題即可利用這些概念。要明白這一點，我們可以先回顧為什麼圖是流行的資料結構以及如何在程式碼中實現它們。

關係模型

無論編碼經驗如何，開發者都應該對陣列和字典的資料類型有所了解。這些集合是大多數語言中使用的標準概念，在呈現基於列表的內容時效果很好：

 

大多數情況下，列表是從資料庫或基於REST的查詢中顯示資訊的完美解決方案。然而，有時列表需要提供存在相互關聯的上下文的記錄。此時，將資料組織為圖表變得方便。

對於圖表，主要目標不是列出資訊（儘管這一點可以做到），而是定義物件之間的關係。為什麼定義物件之間的關係會有用？不妨看看以下幾個例子。

 

一個有兩個頂點和一個邊的無向圖

（1）地圖應用程式：

如果在技術面試中被問到，你將如何組織數據，以便重新創建地圖服務（如Apple 或Google Maps）？除了在資料庫中提供所有已知道路的清單外，你創建的模型還需要根據一天中的時間、交通和單行道等因素來確定到達目的地的最佳方式。要使這大量的數據有效，您需要知道一條道路與模型中的所有其他街道之間的關係。

（2）社群媒體：

一個社群媒體的價值，通常由用戶追蹤或追蹤用戶的人數來衡量。像Twitter這樣的網路平台可以讓用戶與任何人聯繫，並接收他們的最新動態，從而吸引了大量用戶。

 LinkedIn模式更為詳細，因為除非接收者接受使用者的連線要求，否則使用者無法將某人新增至該使用者的網路。在這種情況下，LinkedIn連結代表雙向關係。順著這個思路，使用者也可以搜尋其人際網絡中是否有人與其想要的工作機會相關聯。在這種情況下，「網路」可能意味著直接或間接的聯繫。這樣一個強大的模型不僅僅是基於一個簡單的列表，它還包含了確定所有配置文件如何關聯的智慧。

圖形元件

現在我們已經了解了圖在日常應用程式中的使用方式，下面我們來介紹圖的組成部分。

圖中的節點稱為頂點。雖然可以將圖建構成單一頂點，但包含多個頂點的模型可以更好地代表現實世界的應用。

圖中的物件透過稱為邊的連接相互關聯。

根據您的需求，頂點可以透過邊連接到一個或多個物件上，也可以建立一個沒有邊的頂點。

最後，與堆疊或佇列等其他標準結構不同，圖通常沒有指定的起點或終點。以下是一些範例圖形配置：

 

一個有兩個頂點和一個邊的無向圖

 

一個有兩個頂點和一個邊的無向圖

 

一個有兩個頂點和一個邊的無向圖

有向與無向

在無向圖中，源頂點和目標之間的連接是相等的。這些模型代表雙向連接——類似於地圖應用程式中的雙向街道。

要定義單向連接，我們可以使用線和箭頭將模型更新為有向圖：

# 

三個頂點和三個邊的有向圖

連通性水準

有時，我們必須表示圖中頂點之間的連結程度。這種技術在量化節點之間的距離、時間或嚴重性時效果很好。 權值通常與一邊相關，是用來追蹤的比較變數。  。

 

三個頂點和三個邊的有向圖，其中邊加權

 

圖頂點

有了對圖論的基本了解後，讓我們看看如何在程式碼中複製這些模型。下面我們建立了一個支援自訂通用物件 (T) 的頂點。 tvalue變數表示該類型保存的數據，包括單一字串、int或自訂類型（例如，街道名稱或社交媒體資料）。

另外，注意要讓我們的類型符合流行的Equatable協定 (Swift)。這可以讓我們在需要時比較特定頂點實例是否相等。

public class Vertex <t> : Equatable {<br><br>​var tvalue: T?<br>​var neighbors = Array<edge>>()<br>​let uuid = UUID()<br><br>​public init(with name: T) {<br>self.tvalue = name<br>​}<br><br>​//equatable conformance<br>​public static func == (lhs: Vertex, rhs: Vertex) -> Bool {<br> return lhs.uuid == rhs.uuid<br>​}<br>}</edge></t>

 

鄰接表

鄰接表表示與其他頂點的連接。如前面所述，每個頂點可以連接到一個或多個鄰接的點。這種關係清單有時稱為“鄰接表”，可以用來解決許多高階問題。

var neighbors = Array<edge>>()</edge>

圖邊

在建立頂點時，我們新增了一個鄰接屬性來儲存自訂邊類型的陣列。下面一邊為後續的相鄰頂點及其潛在的邊的權值提供參考。

public class Edge <t> {<br><br>​var neighbor: Vertex<t><br>​var weight: Int<br><br>​init() {<br> weight = 0<br> self.neighbor = Vertex<t>()<br>​}<br>}</t></t></t>

建立畫布

有了頂點和邊對象，我們現在可以將它們添加到中央儲存結構中，我們稱之為圖形畫布。儘管我們的畫佈在技術上是一個數組，但我們的目標是將集合視覺化為一組關係。借助addVertex 函數，我們可以為畫布添加單一通用頂點，同時addEdge方法可提供邊所需的參考資訊。

最後，我們的程式碼假設圖是有向的，因為邊（僅）被加入到來源頂點鄰接表中。

public class Graph <t> {<br><br>​var canvas: Array<vertex>><br><br> public init() {<br> canvas = Array<vertex>()<br>​}<br><br>​//add vertex to graph canvas<br>​public func addVertex(element: Vertex<t>) {<br> canvas.append(element)<br>​}<br>/add edge<br>​public func addEdge(source: Vertex<t>, neighbor: Vertex<t>, weight: Int) {<br><br> //create a new edge<br> let newEdge = Edge<t>()<br><br> //connect source vertex to neighboring edge<br> newEdge.neighbor = neighbor<br> newEdge.weight = weight<br><br> source.neighbors.append(newEdge)<br>​}<br>}</t></t></t></t></vertex></vertex></t>

#

總之，我們介紹了圖的有關知識，並了解如何使用它們來表示物件之間的關係，還回顧了配置圖的幾種方法以及用於描述不同模型的組件。

定義了模型後，我們就為更進階的功能奠定了基礎，包括圖形導航和遍歷演算法，如廣度優先搜尋。

譯者介紹

康少京，51CTO社群編輯，目前從事通訊類產業，底層驅動開發崗位，研究過資料結構，Python，現對作業系統和資料庫等相關領域感興趣。

 原文標題：The complete beginner's guide to graph theory，作者：Wayne Bishop

連結：

https://stackoverflow.blog/2022/05/26/the -complete-beginners-guide-to-graph-theory/

以上是圖論其實不難入門的詳細內容。更多資訊請關注PHP中文網其他相關文章！