幅優先探索（breadth first search: BFS）#
まず、根ノードに隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。
幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。
最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。
from typing import List
from queue import Queue
def get_adjacent_nodes(edges: List[list]) -> List[list]:
"""各nodeと隣接したnodeのリストを作る"""
nodes = set(sum(edges, []))
adjacent_nodes = []
for node in nodes:
adjacent_node = []
for edge in edges:
if node in edge:
e = [e for e in edge if e != node][0]
adjacent_node.append(e)
adjacent_nodes.append(adjacent_node)
return adjacent_nodes
def bfs(edges: List[list]):
"""幅優先探索（breadth first search）"""
adjacent_nodes = get_adjacent_nodes(edges)
n_edge: int = len(set(sum(edges,[])))
# その頂点を検知済みかどうかを表す配列
searched: List[bool] = [False] * n_edge
# 検知したがまだ訪問済みでない頂点の集合 (保留中の頂点の集合)
todo = Queue()
# root nodeをtodoに入れる
searched[0] = True
todo.put(0)
while not todo.empty():
target_node: int = todo.get()
print(f"searching a node '{target_node}'")
for adj_node in adjacent_nodes[target_node]:
if not searched[adj_node]:
print(f"{adj_node} is found and enqueued to todo")
todo.put(adj_node)
searched[adj_node] = True
# 隣接リスト表現 (adjacency-list representation)したグラフ
edges: List[list] = [
[0, 1], # 0 - 1 の辺
[0, 2],
[1, 3]
]
bfs(edges)
searching a node '0'
1 is found and enqueued to todo
2 is found and enqueued to todo
searching a node '1'
3 is found and enqueued to todo
searching a node '2'
searching a node '3'
最良優先探索（best-first search）#
幅優先探索を拡張し、最も望ましいノードを選択するようにしたもの
深さ優先探索（depth-first search）#
根ノードから子ノードへとどんどん深く探索していき、行き着いたらバックトラック（一歩逆戻り）して別のノードを探索する
from typing import List
def get_adjacent_nodes(edges: List[list]) -> List[list]:
"""各nodeと隣接したnodeのリストを作る"""
nodes = set(sum(edges, []))
adjacent_nodes = []
for node in nodes:
adjacent_node = []
for edge in edges:
if node in edge:
e = [e for e in edge if e != node][0]
adjacent_node.append(e)
adjacent_nodes.append(adjacent_node)
return adjacent_nodes
def dfs(edges: List[list]):
"""深さ優先探索（depth-first search）"""
adjacent_nodes = get_adjacent_nodes(edges)
n_edge: int = len(set(sum(edges,[])))
# その頂点を検知済みかどうかを表す配列
searched: List[bool] = [False] * n_edge
# 検知したがまだ訪問済みでない頂点の集合 (保留中の頂点の集合)
todo: List[int] = []
# root nodeをtodoに入れる
searched[0] = True
todo.append(0)
while len(todo) > 0:
target_node: int = todo.pop()
print(f"searching a node '{target_node}'")
for adj_node in adjacent_nodes[target_node]:
if not searched[adj_node]:
print(f"{adj_node} is found and enqueued to todo")
todo.append(adj_node)
searched[adj_node] = True
# 隣接リスト表現 (adjacency-list representation)したグラフ
edges: List[list] = [
[0, 1], # 0 - 1 の辺
[0, 2],
[1, 3]
]
dfs(edges)
searching a node '0'
1 is found and enqueued to todo
2 is found and enqueued to todo
searching a node '2'
searching a node '1'
3 is found and enqueued to todo
searching a node '3'