DFS(深さ優先探索)とBFS(幅優先探索)比較！グラフ探索アルゴリズムの基礎と使い分け

def dfs_recursive(graph, node, visited=None):
    """
    再帰を使ったDFSの実装
    
    Parameters:
    graph: 隣接リストで表現されたグラフ
    node: 現在のノード
    visited: 訪問済みノードの集合
    """
    if visited is None:
        visited = set()
    
    # 現在のノードを訪問済みにマーク
    visited.add(node)
    print(f"訪問: {node}")
    
    # 隣接ノードを探索
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited

# グラフの定義（隣接リスト形式）
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# DFSの実行
print("=== DFS（再帰版）の実行結果 ===")
dfs_recursive(graph, 'A')

def dfs_stack(graph, start):
    """
    スタックを使ったDFSの実装
    
    Parameters:
    graph: 隣接リストで表現されたグラフ
    start: スタート地点のノード
    """
    visited = set()
    stack = [start]  # スタックの初期化
    
    while stack:
        # スタックから取り出す（後入れ先出し）
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            print(f"訪問: {node}")
            
            # 隣接ノードをスタックに追加
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return visited

# DFSの実行
print("\n=== DFS（スタック版）の実行結果 ===")
dfs_stack(graph, 'A')

from collections import deque

def bfs(graph, start):
    """
    キューを使ったBFSの実装
    
    Parameters:
    graph: 隣接リストで表現されたグラフ
    start: スタート地点のノード
    """
    visited = set()
    queue = deque([start])  # キューの初期化
    visited.add(start)
    
    while queue:
        # キューから取り出す（先入れ先出し）
        node = queue.popleft()
        print(f"訪問: {node}")
        
        # 隣接ノードをキューに追加
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited

# 同じグラフでBFSを実行
print("=== BFS の実行結果 ===")
bfs(graph, 'A')

def bfs_shortest_path(graph, start, goal):
    """
    最短経路を見つけるBFS
    
    Parameters:
    graph: 隣接リストで表現されたグラフ
    start: スタート地点
    goal: ゴール地点
    
    Returns:
    最短経路のリスト（見つからなければNone）
    """
    visited = set()
    queue = deque([[start]])  # 経路のリストをキューに保存
    
    if start == goal:
        return [start]
    
    visited.add(start)
    
    while queue:
        # 現在の経路を取り出す
        path = queue.popleft()
        node = path[-1]  # 経路の最後のノード
        
        # 隣接ノードを探索
        for neighbor in graph[node]:
            if neighbor not in visited:
                new_path = path + [neighbor]
                
                # ゴールに到達したら経路を返す
                if neighbor == goal:
                    return new_path
                
                visited.add(neighbor)
                queue.append(new_path)
    
    return None  # 経路が見つからない

# 最短経路の探索
print("\n=== 最短経路探索の実行結果 ===")
path = bfs_shortest_path(graph, 'A', 'F')
if path:
    print(f"AからFへの最短経路: {' -> '.join(path)}")
    print(f"距離: {len(path) - 1}")

def find_all_paths_dfs(graph, start, goal, path=[]):
    """
    DFSを使って全ての経路を見つける
    """
    path = path + [start]
    
    if start == goal:
        return [path]
    
    paths = []
    for neighbor in graph[start]:
        if neighbor not in path:  # 循環を避ける
            new_paths = find_all_paths_dfs(graph, neighbor, goal, path)
            paths.extend(new_paths)
    
    return paths

# 全経路の探索
print("\n=== 全経路の探索（DFS）===")
all_paths = find_all_paths_dfs(graph, 'A', 'F')
for i, path in enumerate(all_paths, 1):
    print(f"経路{i}: {' -> '.join(path)}")

def bfs_shortest_distance(graph, start, goal):
    """
    BFSで最短距離を計算
    """
    visited = {start: 0}  # ノード: 距離
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        
        if node == goal:
            return visited[goal]
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited[neighbor] = visited[node] + 1
                queue.append(neighbor)
    
    return -1  # 到達不可能

# 最短距離の計算
print("\n=== 最短距離の計算（BFS）===")
distance = bfs_shortest_distance(graph, 'A', 'F')
print(f"AからFまでの最短距離: {distance}")

from collections import deque

def solve_maze_bfs(maze, start, goal):
    """
    BFSで迷路を解く（最短経路を見つける）
    
    maze: 2次元リスト（0=通路、1=壁）
    start: (row, col) のタプル
    goal: (row, col) のタプル
    """
    rows, cols = len(maze), len(maze[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右、下、左、上
    
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        (row, col), path = queue.popleft()
        
        if (row, col) == goal:
            return path
        
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # 範囲内かつ通路かつ未訪問
            if (0 <= new_row < rows and 
                0 <= new_col < cols and 
                maze[new_row][new_col] == 0 and 
                (new_row, new_col) not in visited):
                
                visited.add((new_row, new_col))
                queue.append(((new_row, new_col), path + [(new_row, new_col)]))
    
    return None

# 迷路の例（0=通路、1=壁）
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

start = (0, 0)
goal = (4, 4)

print("\n=== 迷路の最短経路探索 ===")
path = solve_maze_bfs(maze, start, goal)
if path:
    print(f"最短経路（長さ{len(path)}）:")
    for pos in path:
        print(f"  {pos}")