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