# 深さ優先探索

def depth_first_search(graph, start_node):
    # 訪問済みの頂点を記録するセット（画像内の「マーク」に相当）
    visited = {start_node}
    # 全域木を構成する辺のリスト
    spanning_tree_edges = []
    # 探索用のスタック（現在の頂点 hat_v を管理）
    stack = [start_node]

    print(f"探索開始: {start_node}")

    while stack:
        current_node = stack[-1]  # 現在の頂点 hat_v
        found_neighbor = False

        # 隣接する頂点 u を順に確認
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                # 未マークの頂点を見つけた場合（前進）
                visited.add(neighbor)
                spanning_tree_edges.append((current_node, neighbor))
                stack.append(neighbor)
                print(f"  前進: {current_node} -> {neighbor}")
                found_neighbor = True
                break

        if not found_neighbor:
            # 前進できる頂点がない場合（後退）
            popped_node = stack.pop()
            if stack:
                print(f"  後退: {popped_node} から {stack[-1]} へ戻る")
            else:
                print(f"  終了: {popped_node} から戻る場所がありません")

    return spanning_tree_edges

    # 画像の図 6.2 に基づいたグラフの定義
graph_6_2 = {
    0: [1, 2],
    1: [0, 3, 5],
    2: [0, 3, 4],
    3: [1, 2, 5],
    4: [2, 6],
    5: [1, 3, 7],
    6: [4],
    7: [5]
}

# 実行
tree = depth_first_search(graph_6_2, 0)
print(f"\n得られた全域木の辺: {tree}")