如何用Python寫深度優先搜尋演算法？

如何用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中文網其他相關文章！