Python で深さ優先検索アルゴリズムを記述するにはどうすればよいですか?

Python で深さ優先検索アルゴリズムを作成するにはどうすればよいですか?

深さ優先検索 (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 の 2 つのパラメータを受け入れます。を使用して、ノードが訪問されたかどうかをマークします。このアルゴリズムはまず、現在のノードを訪問済みとしてマークし、ノードの値を出力します。次に、現在のノードのすべての隣接ノードを走査します。隣接ノードがまだ訪問されていない場合は、dfs_util 関数が再帰的に呼び出されます。

最後に、dfs 関数は外部インターフェイスとして機能し、開始ノードをパラメーターとして受け取り、False に初期化された visited 配列を作成します。 dfs_util 関数を呼び出して、DFS トラバーサルを開始します。

テスト コードでは、4 つのノードを持つグラフを作成し、いくつかのエッジを追加します。次に、開始ノード 2 を使用して DFS トラバーサルを実行し、結果を出力します。

このコード例が、Python で深さ優先検索アルゴリズムを作成する方法を理解するのに役立つことを願っています。独自のニーズに応じてコードを変更および最適化することもできます。

以上がPython で深さ優先検索アルゴリズムを記述するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。