如何用Python寫深度優先搜尋演算法？
深度優先搜尋（Depth-First Search，簡稱DFS）是常用的圖遍歷演算法。在深度優先搜尋中，從起始節點開始，不斷探索鄰接節點，直到無法繼續探索，然後回退到上一節點，繼續遍歷還未探索的鄰接節點，直至所有節點都被存取。
下面是一個用Python編寫的深度優先搜尋演算法範例：
# 定义图的类
class Graph:
def __init__(self, vertices):
self.V = vertices # 节点数量
self.adj = [[] for _ in range(self.V)] # 存储节点的邻接节点
# 添加边
def add_edge(self, u, v):
self.adj[u].append(v)
# DFS递归函数
def dfs_util(self, u, visited):
visited[u] = True # 标记当前节点为已访问
print(u, end=' ') # 输出当前节点
# 遍历当前节点的所有邻接节点
for i in self.adj[u]:
if not visited[i]:
self.dfs_util(i, visited)
# 对外接口，执行DFS
def dfs(self, u):
visited = [False] * self.V # 标记所有节点均未访问
self.dfs_util(u, visited)
# 测试代码
if __name__ == '__main__':
# 创建一个具有4个节点的图
g = Graph(4)
# 添加图的边
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("深度优先遍历结果：")
g.dfs(2)以上程式碼實作了一個Graph類別來表示圖的結構，其中包含了初始化節點數量和鄰接節點的定義。接著定義了新增邊的函數add_edge。
DFS演算法在dfs_util遞歸函數的輔助下進行，函數接受兩個參數：目前節點u和一個陣列visited，用於標記節點是否已經存取。演算法首先將目前節點標記為已訪問，並輸出該節點的值。然後遍歷當前節點的所有鄰接節點，如果鄰接節點尚未被訪問，則遞歸呼叫dfs_util函數。
最後，dfs函數作為對外接口，接受起始節點作為參數，並建立一個visited陣列初始化為False。呼叫dfs_util函數開始DFS遍歷。
在測試程式碼中，我們建立了一個具有4個節點的圖，並加入了一些邊。然後使用起始節點2進行DFS遍歷，並輸出結果。
希望這個程式碼範例能夠幫助你理解如何用Python寫深度優先搜尋演算法。你也可以根據自己的需求對程式碼進行修改和優化。
以上是如何用Python寫深度優先搜尋演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
