目錄
1 基本原理
2 DFS算法流程
3 時(shí)間復(fù)雜度
4 空間復(fù)雜度
5 DFS算法應(yīng)用案例：
5.1 解決路徑查找問(wèn)題?
5.2 解決圖的連通性問(wèn)題
5.3? 拓?fù)渑判?/p>
5.4? 在樹(shù)結(jié)構(gòu)中進(jìn)行深度遍歷
深度優(yōu)先搜索（DFS）是一種重要的圖遍歷算法，用于探索圖中的節(jié)點(diǎn)和邊。
1 基本原理
- DFS 是一種遞歸或棧（堆棧）數(shù)據(jù)結(jié)構(gòu)的算法，用于圖的遍歷。
- 從一個(gè)起始節(jié)點(diǎn)開(kāi)始，盡可能深入圖的分支，直到無(wú)法繼續(xù)深入，然后回溯并探索其他分支。
- 通過(guò)標(biāo)記已訪問(wèn)的節(jié)點(diǎn)來(lái)避免重復(fù)訪問(wèn)。
2 DFS算法流程
創(chuàng)建一個(gè)空的棧（Stack）數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)待訪問(wèn)的節(jié)點(diǎn)。
從起始節(jié)點(diǎn)開(kāi)始，將其標(biāo)記為已訪問(wèn)并入棧。
重復(fù)以下步驟，直到棧為空： a. 出棧一個(gè)節(jié)點(diǎn)，并標(biāo)記為已訪問(wèn)。 b. 檢查該節(jié)點(diǎn)的所有未被訪問(wèn)的鄰居節(jié)點(diǎn)。 c. 對(duì)于每個(gè)未訪問(wèn)的鄰居節(jié)點(diǎn)，將其標(biāo)記為已訪問(wèn)并入棧。
如果無(wú)法再繼續(xù)，即沒(méi)有未訪問(wèn)的鄰居節(jié)點(diǎn)，返回上一個(gè)節(jié)點(diǎn)并繼續(xù)。
重復(fù)步驟2-4，直到遍歷整個(gè)圖。
3 時(shí)間復(fù)雜度
- 在最壞情況下，DFS的時(shí)間復(fù)雜度可以是O(V + E)，其中V是節(jié)點(diǎn)數(shù)，E是邊數(shù)。
- 由于DFS可能訪問(wèn)整個(gè)圖，因此在稠密圖中可能效率較低。
4 空間復(fù)雜度
- 空間復(fù)雜度取決于遞歸深度或堆棧的大小，通常為O(V)?
5 DFS算法應(yīng)用案例：
5.1 解決路徑查找問(wèn)題?
????????一個(gè)常見(jiàn)的應(yīng)用案例是查找從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑。例如，在以下示例圖中，我們要查找從節(jié)點(diǎn)A到節(jié)點(diǎn)G的路徑。
下面是一個(gè)簡(jiǎn)單的Python代碼示例，用于執(zhí)行DFS算法，找到從節(jié)點(diǎn)A到節(jié)點(diǎn)G的路徑。
# 定義示例圖
GRAPH = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': ['G'],
'G': []
}
# 定義DFS算法，查找從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑
def dfs(graph, start, end, path=[]):
# 將當(dāng)前節(jié)點(diǎn)添加到路徑中
path = path + [start]
# 如果當(dāng)前節(jié)點(diǎn)等于目標(biāo)節(jié)點(diǎn)，返回找到的路徑
if start == end:
return path
# 如果當(dāng)前節(jié)點(diǎn)不在圖中，返回None
if start not in graph:
return None
# 遍歷當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)
for node in graph[start]:
# 如果鄰居節(jié)點(diǎn)不在已訪問(wèn)的路徑中，繼續(xù)DFS
if node not in path:
new_path = dfs(graph, node, end, path)
# 如果找到路徑，返回該路徑
if new_path:
return new_path
# 如果無(wú)法找到路徑，返回None
return None
# 調(diào)用DFS算法查找從A到G的路徑
path = dfs(GRAPH, 'A', 'G')
if path:
print("Path from A to G:", path)
else:
print("No path found.")
輸出：
5.2 解決圖的連通性問(wèn)題：查找下圖中的連通組件
import networkx as nx
import matplotlib.pyplot as plt
# 定義一個(gè)有向圖的鄰接列表表示
graph = {
'A': ['B', 'C'],
'B': ['A'],
'C': ['A'],
'D': ['E'],
'E': ['D'],
'F': [],
}
def find_connected_components(graph):
def dfs(node, component):
visited.add(node)
component.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor, component)
visited = set()
connected_components = []
for node in graph:
if node not in visited:
component = []
dfs(node, component)
connected_components.append(component)
return connected_components
# 查找連通組件
components = find_connected_components(graph)
# 打印連通組件
for i, component in enumerate(components, start=1):
print(f"Connected Component {i}: {component}")
# 創(chuàng)建有向圖
G = nx.DiGraph(graph)
# 繪制圖形
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=500, node_color='lightblue', font_size=10, font_color='black', font_weight='bold')
# 添加邊的標(biāo)簽
labels = {}
for node in G.nodes():
labels[node] = node
edge_labels = {(u, v): v for u, v in G.edges()}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=8)
plt.show()
輸出：
? ????????示例創(chuàng)建
find_connected_components函數(shù)，用于查找圖中的連通組件。它使用深度優(yōu)先搜索（DFS）來(lái)遍歷圖，找到連通組件，并將它們添加到connected_components列表中。解析如下：
find_connected_components(graph)函數(shù)接受一個(gè)有向圖的鄰接列表表示為輸入，并返回圖中的連通組件。內(nèi)部嵌套的
dfs(node, component)函數(shù)是深度優(yōu)先搜索函數(shù)。它采用兩個(gè)參數(shù)：
node表示當(dāng)前遍歷的節(jié)點(diǎn)。component是一個(gè)列表，用于存儲(chǔ)當(dāng)前連通組件中的節(jié)點(diǎn)。
dfs函數(shù)的目標(biāo)是遍歷與node相關(guān)聯(lián)的節(jié)點(diǎn)，并將它們添加到component中。
visited是一個(gè)集合，用于跟蹤已訪問(wèn)的節(jié)點(diǎn)。一開(kāi)始，它是空的。
connected_components是一個(gè)列表，用于存儲(chǔ)找到的連通組件。開(kāi)始時(shí)，它也是空的。外部的
for循環(huán)遍歷圖中的每個(gè)節(jié)點(diǎn)，以確保所有節(jié)點(diǎn)都被覆蓋。對(duì)于每個(gè)節(jié)點(diǎn)，它執(zhí)行以下操作：
- 如果該節(jié)點(diǎn)尚未在
visited中，表示它是一個(gè)新的連通組件的起始節(jié)點(diǎn)。- 創(chuàng)建一個(gè)新的空列表
component，用于存儲(chǔ)該連通組件的節(jié)點(diǎn)。- 調(diào)用
dfs(node, component)函數(shù)，開(kāi)始深度優(yōu)先搜索，并將所有與該節(jié)點(diǎn)相連的節(jié)點(diǎn)添加到component中。- 將
component添加到connected_components中，表示已找到一個(gè)連通組件。最后，函數(shù)返回
connected_components列表，其中包含了所有找到的連通組件。
5.3? 拓?fù)渑判?/h3>
????????拓?fù)渑判蚴怯糜诖_定有向圖中節(jié)點(diǎn)的線性順序，使得圖中的每一條有向邊都是從前面的節(jié)點(diǎn)指向后面的節(jié)點(diǎn)。在拓?fù)渑判蛑校瑳](méi)有環(huán)路存在。
應(yīng)用示例：
????????假設(shè)有一個(gè)有向圖如下，表示課程之間的依賴(lài)關(guān)系，您需要找到一個(gè)可以完成所有課程的順序。如果存在環(huán)路，表示存在無(wú)法解決的依賴(lài)關(guān)系，您需要找到一個(gè)沒(méi)有環(huán)路的順序。
import networkx as nx
import matplotlib.pyplot as plt
def topological_sort(graph):
def dfs(node):
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor)
result.append(node)
visited = set()
result = []
for node in graph:
if node not in visited:
dfs(node)
return result[::-1]
# 定義有向圖的依賴(lài)關(guān)系
courses = {
'CSC300': ['CSC100', 'CSC200'],
'CSC200': ['CSC100'],
'CSC100': [],
'CSC400': ['CSC300', 'CSC200'],
}
# 創(chuàng)建一個(gè)有向圖
G = nx.DiGraph(courses)
# 調(diào)用拓?fù)渑判蛩惴?topological_order = topological_sort(courses)
if topological_order:
print("Topological Order of Courses:", topological_order)
else:
print("No valid topological order (contains a cycle).")
# 繪制有向圖
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=500, node_color='lightblue', font_size=10, font_color='black', font_weight='bold')
# 添加邊的標(biāo)簽
labels = {}
for node in G.nodes():
labels[node] = node
edge_labels = {(u, v): v for u, v in G.edges()}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=8)
plt.show()
輸出為：
????????示例定義了
topological_sort函數(shù)，用于執(zhí)行拓?fù)渑判?。這個(gè)函數(shù)使用深度優(yōu)先搜索（DFS）來(lái)查找圖的拓?fù)渑判?。如果圖中存在環(huán)路，該函數(shù)仍然會(huì)返回一個(gè)排序結(jié)果，但它不保證是一個(gè)有效的拓?fù)渑判颉?/p>
5.4? 在樹(shù)結(jié)構(gòu)中進(jìn)行深度遍歷
import networkx as nx
import matplotlib.pyplot as plt
class TreeNode:
def __init__(self, value):
self.value = value
self.children = []
def add_child(self, child_node):
self.children.append(child_node)
def depth_first_search(node, graph, parent=None):
if node is None:
return
graph.add_node(node.value) # 添加節(jié)點(diǎn)到圖中
if parent is not None:
graph.add_edge(parent.value, node.value) # 添加邊連接父節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)
print(node.value) # 在DFS時(shí)輸出節(jié)點(diǎn)值
for child in node.children:
depth_first_search(child, graph, node) # 遞歸遍歷子節(jié)點(diǎn)
# 創(chuàng)建一個(gè)較復(fù)雜的樹(shù)結(jié)構(gòu)
root = TreeNode("A")
b = TreeNode("B")
c = TreeNode("C")
d = TreeNode("D")
e = TreeNode("E")
f = TreeNode("F")
g = TreeNode("G")
h = TreeNode("H")
i = TreeNode("I")
root.add_child(b)
root.add_child(c)
b.add_child(d)
b.add_child(e)
c.add_child(f)
c.add_child(g)
g.add_child(h)
h.add_child(i)
# 創(chuàng)建一個(gè)有向圖
G = nx.DiGraph()
# 執(zhí)行深度優(yōu)先搜索并創(chuàng)建圖
depth_first_search(root, G)
# 繪制樹(shù)結(jié)構(gòu)圖
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=500, node_color='lightblue', font_size=10, font_color='black', font_weight='bold')
# 添加邊的標(biāo)簽
labels = {}
for node in G.nodes():
labels[node] = node
edge_labels = {(u, v): v for u, v in G.edges()}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=8)
plt.show()
?????????這段代碼用于創(chuàng)建一個(gè)樹(shù)結(jié)構(gòu)，然后執(zhí)行深度優(yōu)先搜索（DFS），最后繪制樹(shù)結(jié)構(gòu)圖并添加標(biāo)簽。以下是對(duì)代碼的詳細(xì)解析：
首先，定義了一個(gè)樹(shù)結(jié)構(gòu)的節(jié)點(diǎn)類(lèi)
TreeNode，其中每個(gè)節(jié)點(diǎn)具有一個(gè)值和子節(jié)點(diǎn)列表。在
depth_first_search函數(shù)中，執(zhí)行深度優(yōu)先搜索。它接受三個(gè)參數(shù)：
node：當(dāng)前要處理的節(jié)點(diǎn)。graph：用于構(gòu)建樹(shù)結(jié)構(gòu)圖的 NetworkX 有向圖對(duì)象。parent：父節(jié)點(diǎn)，用于添加邊。在函數(shù)中，執(zhí)行以下操作：
- 添加當(dāng)前節(jié)點(diǎn)到圖中（
graph.add_node(node.value)）。- 如果存在父節(jié)點(diǎn)，添加從父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的邊（
graph.add_edge(parent.value, node.value)）。- 打印當(dāng)前節(jié)點(diǎn)的值，以在DFS期間輸出節(jié)點(diǎn)值。
- 遞歸遍歷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)，使用當(dāng)前節(jié)點(diǎn)作為父節(jié)點(diǎn)。
創(chuàng)建一個(gè)較復(fù)雜的樹(shù)結(jié)構(gòu)：
- 根節(jié)點(diǎn)為 "A"，有兩個(gè)子節(jié)點(diǎn) "B" 和 "C"。
- 節(jié)點(diǎn) "B" 有兩個(gè)子節(jié)點(diǎn) "D" 和 "E"。
- 節(jié)點(diǎn) "C" 有兩個(gè)子節(jié)點(diǎn) "F" 和 "G"。
- 節(jié)點(diǎn) "G" 有一個(gè)子節(jié)點(diǎn) "H"。
- 節(jié)點(diǎn) "H" 有一個(gè)子節(jié)點(diǎn) "I"。
創(chuàng)建一個(gè) NetworkX 有向圖對(duì)象
G，用于存儲(chǔ)樹(shù)結(jié)構(gòu)圖。執(zhí)行深度優(yōu)先搜索，從根節(jié)點(diǎn) "A" 開(kāi)始。深度優(yōu)先搜索會(huì)遞歸遍歷樹(shù)的每個(gè)分支，并在DFS期間輸出節(jié)點(diǎn)值。
使用 NetworkX 繪制樹(shù)結(jié)構(gòu)圖：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-734863.html
nx.spring_layout用于確定節(jié)點(diǎn)的位置。nx.draw用于繪制節(jié)點(diǎn)和邊，設(shè)置節(jié)點(diǎn)的大小、顏色和標(biāo)簽。nx.draw_networkx_edge_labels用于添加邊的標(biāo)簽。最后，通過(guò)
plt.show()顯示繪制的樹(shù)結(jié)構(gòu)圖。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-734863.html
到了這里，關(guān)于【Python搜索算法】深度優(yōu)先搜索（DFS）算法原理詳解與應(yīng)用，示例+代碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
