lessons/互动程序/01-欧拉路径/00-从散步到欧拉回路.py

#!/usr/bin/env python3
"""课前零食：用很小的图观察欧拉路径和 Hierholzer 栈。"""

from __future__ import annotations

from collections import defaultdict, deque


DEFAULT_EDGES = [
    ("A", "B"), ("B", "C"), ("C", "A"),
    ("A", "D"), ("D", "E"), ("E", "A"),
]


def ask(prompt: str, default: str = "") -> str:
    try:
        value = input(prompt).strip()
    except EOFError:
        value = ""
    return value or default


def parse_edges(raw: str) -> list[tuple[str, str]]:
    edges: list[tuple[str, str]] = []
    for token in raw.replace("，", ",").split(","):
        token = token.strip()
        if not token:
            continue
        if "-" not in token:
            raise ValueError(f"{token!r} 缺少连字符，例如 A-B")
        left, right = (part.strip() for part in token.split("-", 1))
        if not left or not right:
            raise ValueError(f"{token!r} 的端点不能为空")
        edges.append((left, right))
    if not edges:
        raise ValueError("至少输入一条边")
    return edges


def build_graph(edges: list[tuple[str, str]]) -> dict[str, list[tuple[str, int]]]:
    graph: dict[str, list[tuple[str, int]]] = defaultdict(list)
    for edge_id, (u, v) in enumerate(edges):
        graph[u].append((v, edge_id))
        graph[v].append((u, edge_id))
    return graph


def nonzero_connected(graph: dict[str, list[tuple[str, int]]]) -> bool:
    active = [vertex for vertex, neighbors in graph.items() if neighbors]
    if not active:
        return True
    seen = {active[0]}
    queue: deque[str] = deque([active[0]])
    while queue:
        u = queue.popleft()
        for v, _ in graph[u]:
            if v not in seen:
                seen.add(v)
                queue.append(v)
    return all(vertex in seen for vertex in active)


def hierholzer_trace(
    graph: dict[str, list[tuple[str, int]]], start: str, edge_count: int
) -> list[str]:
    used = [False] * edge_count
    pointer = {vertex: 0 for vertex in graph}
    stack = [start]
    reversed_answer: list[str] = []
    print("\n--- 栈的动作日志 ---")
    while stack:
        u = stack[-1]
        while (
            pointer[u] < len(graph[u])
            and used[graph[u][pointer[u]][1]]
        ):
            pointer[u] += 1
        if pointer[u] == len(graph[u]):
            finished = stack.pop()
            reversed_answer.append(finished)
            print(f"{finished} 没有未用边：弹栈，倒序答案为 {reversed_answer}")
            continue
        v, edge_id = graph[u][pointer[u]]
        used[edge_id] = True
        stack.append(v)
        print(f"走边 #{edge_id}: {u}-{v}，栈变成 {' -> '.join(stack)}")
    answer = list(reversed(reversed_answer))
    return answer


def main() -> None:
    print("欧拉小散步：输入边时用 A-B,B-C 这种格式。")
    raw = ask("直接回车用双三角形；或输入自己的边： ")
    try:
        edges = DEFAULT_EDGES if not raw else parse_edges(raw)
    except ValueError as error:
        print(f"输入不太像一张图：{error}。这次先用预设图。")
        edges = DEFAULT_EDGES

    graph = build_graph(edges)
    degree = {vertex: len(neighbors) for vertex, neighbors in graph.items()}
    odd = [vertex for vertex, value in degree.items() if value % 2 == 1]
    print("\n边：", ", ".join(f"{u}-{v}" for u, v in edges))
    print("度数：", ", ".join(f"{v}:{degree[v]}" for v in sorted(degree)))
    print("奇度点：", odd or "没有")

    connected = nonzero_connected(graph)
    possible = connected and len(odd) in (0, 2)
    print("非孤立点连通：", "是" if connected else "否")
    if not possible:
        print("\n这张图没有欧拉路径：先别让栈背锅，条件已经不成立。")
        return

    start = odd[0] if odd else min(graph)
    print(f"\n条件成立，从 {start} 开始。注意：收集答案的顺序会反过来。")
    answer = hierholzer_trace(graph, start, len(edges))
    print("\n最终欧拉路线：", " -> ".join(answer))
    print(
        f"长度检查：{len(answer)} 个顶点，应该是边数 + 1 = {len(edges) + 1}。"
    )


if __name__ == "__main__":
    main()