Pythonで深さ優先探索アルゴリズムを実装する方法

2年 ago
優斗, 朝陽
1 minute

深さ優先探索はよく使われるグラフ探索法で、再帰またはスタックを使って実装できます。

再帰的に深さ優先探索アルゴリズムを実装するには、以下の手順に従います。

  1. DFS関数を定義します。引数は現在のノードと訪問状態の集合です。初期状態は未訪問です。
  2. 現在のノードを訪問済みとしてマークします。
  3. 現在のノードの隣接ノードを調べて、隣接ノードが未訪問の場合、再帰的にDFS関数を実行します。
  4. 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)

再帰を使わなければ、スタックを用いて深さ優先探索アルゴリズムを実現できる。スタックとは後入れ先出しの原理のデータ構造であり、訪問すべきノードを格納するのに利用できる。具体的な手順は以下のとおりである。

  1. スタックを作成し、先頭節点を追加します。
  2. ノードのアクセス状況を記録するためのコレクションを作成します。
  3. スタックが空になるまでループを続ける
  1. スタックのトップノードをポップし、それを訪れたものとしてマークする。
  2. 現在のノードの近接ノードをすべて回り、その近接ノードが訪問済みでない場合、スタックにプッシュする。

以下に、スタックを用いて深さ優先探索 (DFS) を実装した例を示します。

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)

一般的な2つの深さ優先探索アルゴリズムの実装方法について説明しました。さまざまなニーズに応じて、適切な方法を選択してください

bannerAds