對于有多年的編程經驗的開發者來說，圖的概念并不陌生。許多頂級公司在技術面試中測試對圖論的理解。 其實，開發者無需處理高級問題即可利用這些概念。要想明白這一點，我們可以先回顧一下為什么圖是流行的數據結構以及如何在代碼中實現它們。
關系模型
無論編碼經驗如何，開發者都應該對數組和字典的數據類型有所了解。 這些集合是大多數語言中使用的標準概念，在呈現基于列表的內容時效果很好：
大多數情況下，列表是從數據庫或基于 REST 的查詢中顯示信息的完美解決方案。 然而，有時列表需要提供存在相互關聯的上下文的記錄。此時，將數據組織為圖表變得方便。
對于圖表，主要目標不是列出信息（盡管這一點可以做到），而是定義對象之間的關系。為什么定義對象之間的關系會有用？不妨看看以下幾個例子。
一個有兩個頂點和一個邊的無向圖
（1）地圖應用程序：
如果在技術面試中被問到，你將如何組織數據，以便重新創建地圖服務（如 Apple 或 Google Maps）？除了在數據庫中提供所有已知道路的列表外，你創建的模型還需要根據一天中的時間、交通和單行道等因素確定到達目的地的最佳方式。要使這大量的數據有效，您需要知道一條道路與模型中的所有其他街道之間的關系。
（2）社交媒體：
一個社交媒體的價值，通常由用戶關注或關注用戶的人數來衡量。像Twitter這樣的網絡平臺可以讓用戶與任何人聯系，并接收他們的最新動態，從而吸引了大量用戶。
LinkedIn模型更為詳細，因為除非接收者接受用戶的連接請求，否則用戶無法將某人添加到該用戶的網絡中。在這種情況下，LinkedIn連接代表雙向關系。順著這個思路，用戶也可以搜索其人際網絡中是否有人與其想要的工作機會相關聯。在這種情況下，“網絡”可能意味著直接或間接的聯系。這樣一個強大的模型不僅僅是基于一個簡單的列表，它還包含了確定所有配置文件如何關聯的智慧。
圖形組件
現在我們已經了解了圖在日常應用程序中的使用方式，下面我們來介紹圖的組成部分。
圖中的節點稱為頂點。雖然可以將圖構建為單個頂點，但包含多個頂點的模型可以更好地代表現實世界的應用。
圖中的對象通過稱為邊的連接相互關聯。
根據您的需求，頂點可以通過邊連接到一個或多個物體上，也可以創建一個沒有邊的頂點。
最后，與堆棧或隊列等其他標準結構不同，圖通常沒有指定的起點或終點。 以下是一些示例圖形配置：
一個有兩個頂點和一個邊的無向圖
一個有兩個頂點和一個邊的無向圖
一個有兩個頂點和一個邊的無向圖
有向與無向
在無向圖中，源頂點和目標之間的連接是相等的。這些模型代表雙向連接——類似于地圖應用程序中的雙向街道。
要定義單向連接，我們可以使用線和箭頭將模型更新為有向圖：
三個頂點和三個邊的有向圖
連通性水平
有時，我們必須表示圖中頂點之間的連接程度。這種技術在量化節點之間的距離、時間或嚴重性時效果很好。權值通常與一條邊相關，是一個用于跟蹤的比較變量。 。
三個頂點和三個邊的有向圖，其中邊加權
圖頂點
有了對圖論的基本了解后，讓我們看看如何在代碼中復制這些模型。下面我們創建了一個支持自定義通用對象 (T) 的頂點。 tvalue變量表示該類型保存的數據，包括單個字符串、int或自定義類型（例如，街道名稱或社交媒體資料）。
另外，注意要讓我們的類型符合流行的Equatable協議 (Swift)。這可以讓我們在需要時比較特定頂點實例是否相等。
public class Vertex <T> : Equatable {
?var tvalue: T?
?var neighbors = Array<Edge<T>>()
?let uuid = UUID()
?public init(with name: T) {
self.tvalue = name
?}
?//equatable conformance
?public static func == (lhs: Vertex, rhs: Vertex) -> Bool {
return lhs.uuid == rhs.uuid
?}
}
鄰接表
鄰接表表示與其他頂點的連接。如前面所述，每個頂點可以連接到一個或多個鄰接的點。 這種關系列表有時稱為“鄰接表”，可以用來解決許多高級問題。
var neighbors = Array<Edge<T>>()
圖邊
在創建頂點時，我們添加了一個鄰接屬性來存儲自定義邊類型的數組。 下面一條邊為后續的相鄰頂點及其潛在的邊的權值提供參考。
public class Edge <T> {
?var neighbor: Vertex<T>
?var weight: Int
?init() {
weight = 0
self.neighbor = Vertex<T>()
?}
}構建畫布
有了頂點和邊對象，我們現在可以將它們添加到中央存儲結構中，我們稱之為圖形畫布。盡管我們的畫布在技術上是一個數組，但我們的目標是將集合可視化為一組關系。 借助addVertex 函數，我們可以向畫布添加單個通用頂點，同時addEdge方法可提供邊所需的參考信息。
最后，我們的代碼假設圖是有向的，因為邊（僅）被添加到源頂點鄰接表中。
public class Graph <T> {
?var canvas: Array<Vertex<T>>
public init() {
canvas = Array<Vertex>()
?}
?//add vertex to graph canvas
?public func addVertex(element: Vertex<T>) {
canvas.append(element)
?}
/add edge
?public func addEdge(source: Vertex<T>, neighbor: Vertex<T>, weight: Int) {
//create a new edge
let newEdge = Edge<T>()
//connect source vertex to neighboring edge
newEdge.neighbor = neighbor
newEdge.weight = weight
source.neighbors.append(newEdge)
?}
}總之，我們介紹了圖的有關知識，并了解了如何使用它們來表示對象之間的關系，還回顧了配置圖的幾種方法以及用于描述不同模型的組件。
定義了模型后，我們就為更高級的功能奠定了基礎，包括圖形導航和遍歷算法，如廣度優先搜索。
譯者介紹
康少京，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/
