python深度優先搜索算法怎么實現

173次閱讀

共計 898 個字符，預計需要花費 3 分鐘才能閱讀完成。

深度優先搜索（Depth First Search，DFS）是一種常用的圖遍歷算法，可以使用遞歸或者棧來實現。
遞歸實現深度優先搜索算法可以按照以下步驟進行：

定義一個 DFS 函數，參數為當前節點和訪問狀態的集合，初始狀態為未訪問。
將當前節點標記為已訪問。
遍歷當前節點的鄰接節點，如果鄰接節點未訪問，則遞歸調用 DFS 函數。
遞歸調用 DFS 函數后，回溯到上一個節點，繼續遍歷下一個未訪問的鄰接節點。

以下是一個使用遞歸實現深度優先搜索的例子：

def dfs(node, visited):
visited.add(node)  # 標記當前節點為已訪問
# 遍歷當前節點的鄰接節點
for neighbor in node.neighbors:
if neighbor not in visited:  # 如果鄰接節點未訪問，則遞歸調用 DFS 函數
dfs(neighbor, visited)
# 使用示例
visited = set()  # 記錄訪問狀態的集合
dfs(start_node, visited)

如果不使用遞歸，可以使用棧來實現深度優先搜索算法。棧的原理是先進后出，可以用來保存待訪問的節點。具體步驟如下：

創建一個棧，并將起始節點入棧。
創建一個集合來記錄節點的訪問狀態。
進入循環，直到棧為空：

彈出棧頂節點，并將其標記為已訪問。
遍歷當前節點的鄰接節點，如果鄰接節點未訪問，則將其入棧。

以下是一個使用棧實現深度優先搜索的例子：

def dfs(start_node):
stack = [start_node]  # 創建一個棧，并將起始節點入棧
visited = set()  # 記錄訪問狀態的集合
while stack:
node = stack.pop()  # 彈出棧頂節點
visited.add(node)  # 標記當前節點為已訪問
# 遍歷當前節點的鄰接節點
for neighbor in node.neighbors:
if neighbor not in visited:  # 如果鄰接節點未訪問，則將其入棧
stack.append(neighbor)
# 使用示例
dfs(start_node)

以上是兩種常見的深度優先搜索算法的實現方式，可以根據具體的需求選擇適合的方法來實現。

丸趣 TV 網 – 提供最優質的資源集合！

正文完