如何使用圖算法，幫助我們理解和處理復雜的關系型數據
算法是編碼面試中最常見的主題之一。為了在面試中獲得優勢，非常熟悉頂級算法及其實現非常重要。
在次此篇文章中，我們將探索圖算法。我們將從圖論和圖算法的介紹開始。接下來，我們將學習如何實現圖。
今天，我們將學習：
- 什么是圖算法？
- 圖的屬性
- 如何在代碼中表示圖形
- 如何實現廣度優先遍歷
- 如何實現深度優先遍歷
- 如何去除邊緣
什么是圖算法？
算法是使用明確定義或最佳步驟數解決問題的數學過程。它只是用于完成特定工作的基本技術。
圖是一種抽象符號，用于表示所有對象對之間的連接。圖是廣泛使用的數學結構，由兩個基本組成部分可視化：節點和邊。
圖算法用于解決將圖表示為網絡的問題，例如航空公司航班、互聯網如何連接或微信、QQ、微博上的社交網絡連接。它們在NLP和機器學習中也很流行，用于形成網絡。
一些頂級的圖形算法包括：
- 實現廣度優先遍歷
- 實現深度優先遍歷
- 計算圖級別中的節點數
- 查找兩個節點之間的所有路徑
- 查找圖的所有連通分量
- Dijkstra 算法在圖數據中查找最短路徑
- 移除邊緣
雖然圖是離散數學不可或缺的一部分，但它們在計算機科學和編程中也有實際用途，包括以下內容：
- 計算機程序中以圖形表示的調用者-被調用者關系
- 網站的鏈接結構可以用有向圖來表示
- 神經網絡
圖的屬性
由 G 表示的圖由一組頂點 (V)或在邊 (E)處鏈接的節點表示。邊的數量取決于頂點。邊緣可以是有向的或無向的。
在有向圖中，節點沿一個方向鏈接。這里的邊顯示了一種單向關系。
在無向圖中，邊是雙向的，顯示出雙向關系。
示例：無向圖的一個很好的用例是微信好友建議算法。用戶（節點）有一個邊緣運行到朋友 A（另一個節點），而朋友 A 又連接（或有一個邊緣運行）到朋友 B。然后將朋友 B 推薦給用戶。
還有許多其他復雜類型的圖屬于不同的子集。例如，當每個頂點都可以從其他每個頂點到達時，有向圖就具有強連通分量。
頂點
頂點是多條線相交的點。它也稱為節點。
邊緣
邊是一個數學術語，用于表示連接兩個頂點的線。許多邊可以由單個頂點形成。然而，沒有頂點，就無法形成邊。每條邊必須有一個起始和結束頂點。
路徑
圖中的路徑G=( V ,E ）是頂點 v1, v2, …, vk 的序列，其屬性是之間有邊 vi 和 vi +1。我們說路徑從v1到vk 。
序列 6,4,5,1,26,4,5,1,2 定義從節點 6 到節點 2 的路徑。
類似地，可以通過遍歷圖的邊來創建其他路徑。如果路徑的頂點全部不同，則路徑很簡單。
行走
行走是路徑，但它們不需要一系列不同的頂點。
連通圖
如果對于每對頂點，則圖是連通的v和v，有一條路徑從v到v。
循環
循環是一條路徑 v1, v2, …, vk，滿足以下條件：
- k>2k>2k>2k _>2
- 首先k-1頂點都不同
- v1=vk
樹
樹是不包含環的連通圖。
環形
在圖中，如果從頂點到自身繪制一條邊，則稱為環。在圖中，V 是一個頂點，其邊 (V, V) 形成一個環。
如何在代碼中表示圖形
在我們繼續使用圖算法解決問題之前，首先了解如何在代碼中表示圖非常重要。圖可以表示為鄰接矩陣或鄰接列表。
鄰接矩陣
鄰接矩陣是由圖頂點標記的方陣，用于表示有限圖。矩陣的條目指示頂點對在圖中是否相鄰。
在鄰接矩陣表示中，需要迭代所有節點來識別節點的鄰居。
a b c d e
a 1 1 - - -
b - - 1 - -
c - - - 1 -
d - 1 1 - -鄰接表
鄰接表用于表示有限圖。鄰接列表表示允許輕松地遍歷節點的鄰居。列表中的每個索引代表頂點，與該索引鏈接的每個節點代表其相鄰頂點。
1 a -> { a b }
2 b -> { c }
3 c -> { d }
4 d -> { b c }對于下面的基圖類，我們將使用鄰接列表實現，因為它對于本文后面的算法解決方案執行得更快。
圖類（Graph Class）
我們的圖實現的要求相當簡單。我們需要兩個數據成員：圖中頂點的總數和存儲相鄰頂點的列表。我們還需要一種添加邊或一組邊的方法。
class AdjNode:
"""
表示節點鄰接表的 類
"""
def __init__(self, data):
"""
構造函數
:參數數據 : 頂點
"""
self.vertex = data
self.next = None
class Graph:
"""
圖類 ADT
"""
def __init__(self, vertices):
"""
構造函數
:param vertices : 圖中的總頂點數
"""
self.V = vertices
self.graph = [None] * self.V
# 在無向圖中添加邊的函數
def add_edge(self, source, destination):
"""
添加邊緣
:param source: 源頂點
:param destination: 目標頂點
"""
# 將節點添加到源節點
node = AdjNode(destination)
node.next = self.graph[source]
self.graph[source] = node
# 如果無向圖，將源節點添加到目標節點
# 故意注釋這一行，方便理解
#node = AdjNode(source)
#node.next = self.graph[destination]
#self.graph[destination] = node
def print_graph(self):
"""
打印圖標的函數
"""
for i in range(self.V):
print("Adjacency list of vertex {}\n head".format(i), end="")
temp = self.graph[i]
while temp:
print(" -> {}".format(temp.vertex), end="")
temp = temp.next
print(" \n")
# 主程序
if __name__ == "__main__":
V = 5 # 頂點總數
g = Graph(V)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.print_graph()在上面的示例中，我們看到了Python graph class。我們已經奠定了圖形類的基礎。變量 V 包含一個整數，指定頂點總數。下面示例的代碼都會用到這個類。
如何實現廣度優先遍歷
給定一個表示為鄰接列表和起始頂點的圖，代碼應該輸出一個字符串，其中包含以正確的遍歷順序列出的圖的頂點。當從起始頂點遍歷圖形時，將首先打印每個節點的右子節點，然后是左子節點。
為了解決這個問題，前面已經實現了 Graph 類。
輸入：表示為鄰接列表和起始頂點的圖。
輸出：一個字符串，其中包含以正確的遍歷順序列出的圖的頂點。
示例輸出：
result = "02143"
or
result = "01234"在開始實施之前，先看一下并設計一個分步算法。首先嘗試自己解決。如果遇到困難，可以隨時參考解決方案部分提供的解決方案。
bfs：
def bfs(graph, source):
"""
打印圖的 BFS 的函數
:param graph: 圖表
:param source: 起始頂點
:return:
"""
# 寫你的代碼
pass解決方案
bfs：
def bfs(my_graph, source):
"""
打印圖的 BFS 函數
:param graph: 圖表
:param source: 起始頂點
:return:
"""
# 將所有的頂點標識為未訪問過
visited = [False] * (len(my_graph.graph))
# 創建 BFS 隊列
queue = []
# 結果字符串
result = ""
# 將源節點表示為 訪問過并將其排入隊列
queue.append(source)
visited[source] = True
while queue:
# 經一個頂點重隊列中取出
# 排隊并打印
source = queue.pop(0)
result += str(source)
# 取出相鄰的頂點
# 出對的頂點源，
#如果一個相鄰的還沒有訪問過，那么標記一下
# 訪問過并將其排入隊列
while my_graph.graph[source] is not None:
data = my_graph.graph[source].vertex
if not visited[data]:
queue.append(data)
visited[data] = True
my_graph.graph[source] = my_graph.graph[source].next
return result
# 主要測試上面的程序
if __name__ == "__main__":
V = 5
g = Graph(V)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
print(bfs(g, 0))我們從選定的節點開始，逐層遍歷圖。探索所有鄰居節點。然后，我們進入下一個級別。我們水平遍歷圖表，也就是每一層。
圖表可能包含循環。為了避免再次處理同一節點，我們可以使用布爾數組來標記訪問過的數組?？梢允褂藐犃衼泶鎯濣c并將其標記為已訪問。隊列應遵循先進先出（FIFO）排隊方法。
如何實現深度優先遍歷
在這個問題中，你必須實現深度優先遍歷。為了解決這個問題，之前實現的圖類已經提供了。
輸入：表示為鄰接列表和起始頂點的圖。
輸出：一個字符串，其中包含以正確的遍歷順序列出的圖的頂點。
示例輸出：
result = "01342"
or
result = "02143"在開始實施之前，先看一下并設計一個分步算法。首先嘗試自己解決。如果遇到困難，可以隨時參考解決方案部分提供的解決方案。
dfs：
def dfs(graph, source):
"""
打印圖的 DFS 的函數
:param graph: 圖表
:param source: 起始頂點
:return:
"""
# 在這里寫下你的代碼!
pass解決方案
dfs：
def dfs(my_graph, source):
"""
打印圖的DFS的函數
:param graph: 圖表
:param source: 起始頂點
:return: 以字符串形式返回遍歷結果
"""
# 將所有頂點標記為未訪問過
visited = [False] * (len(my_graph.graph))
# 創建 DFS 堆棧
stack = []
# 結果字符串
result = ""
# 拼接字符
stack.append(source)
while stack:
# 從堆棧中彈出一個頂點
source = stack.pop()
if not visited[source]:
result += str(source)
visited[source] = True
# 獲取彈出頂點源的所有相鄰頂點
# 如果相鄰的未必訪問過，則將其壓入
while my_graph.graph[source] is not None:
data = my_graph.graph[source].vertex
if not visited[data]:
stack.append(data)
my_graph.graph[source] = my_graph.graph[source].next
return result
# 主程序運行
if __name__ == "__main__":
V = 5
g = Graph(V)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
print(dfs(g, 0))深度優先圖算法利用了回溯的思想。這里的“回溯”是指只要當前路徑上沒有更多的節點，就向前移動，然后在同一條路徑上向后移動，尋找要遍歷的節點。
如何去除邊緣
在此問題中，必須實現remove_edge以源和目標作為參數的函數。如果兩者之間存在邊，則應將其刪除。
輸入：圖形、源（整數）和目標（整數）。
輸出：對圖進行 BFS 遍歷，并刪除源和目標之間的邊。
首先，在開始實施之前仔細研究這個問題并設計一個分步算法。
remove_edge：
def remove_edge(graph, source, destination):
"""
刪除邊緣函數
:param graph: 圖表
:param source: 源頂點
:param destination: 目標頂點
"""
# 寫代碼
pass解決方案
如果熟悉的話，這個解決方案與鏈表中的刪除非常相似。
我們的頂點存儲在一個鏈接列表中。首先，我們訪問source鏈表。如果源鏈表的頭節點持有要刪除的鍵，我們將頭向前移動一步并返回圖。
如果要刪除的鍵位于鏈表的中間，我們會跟蹤前一個節點，并在目的地遇到時將前一個節點與下一個節點連接起來。
總結
圖算法是用于解決圖（Graph）數據結構中的各種問題的算法，對廣度優先和深度優先做了一些示例，還有注釋，我們可以私下練習一下。
圖算法能夠幫助我們理解和處理復雜的關系型數據，并在實際應用中提供解決方案。
