图（Graph）遍历：深度优先搜索（DFS）

# /*
# 图（Graph）遍历：深度优先搜索（DFS）
# --------------------------------------------------------
# 定义：
# 深度优先搜索（Depth-First Search）沿着图的一条路径尽可能深入，
# 到达终点或无未访问节点时回溯，再探索其他路径。
#
# 特点：
# - 可用于连通性判断、拓扑排序、路径搜索等
# - 可以用递归或栈实现
# */

# 图的邻接表表示
class Graph:
    def __init__(self):
        self.adj_list = {}

    def add_vertex(self, v):
        if v not in self.adj_list:
            self.adj_list[v] = []

    def add_edge(self, u, v):
        if u not in self.adj_list:
            self.add_vertex(u)
        if v not in self.adj_list:
            self.add_vertex(v)
        self.adj_list[u].append(v)
        # 无向图可添加 self.adj_list[v].append(u)

    def display(self):
        for vertex, neighbors in self.adj_list.items():
            print(f"{vertex} -> {neighbors}")

# --------------------------------------------------------
# DFS 遍历（递归实现）
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()

    visited.add(start)
    print(start, end=" ")

    for neighbor in graph.adj_list.get(start, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

    return visited

# --------------------------------------------------------
# 示例操作
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")
g.add_edge("D", "E")

print("图的邻接表：")
g.display()

print("\n深度优先搜索 DFS 结果：", end="")
dfs(g, "A")
print()

# --------------------------------------------------------
# 要点总结：
# 1) DFS 沿一条路径尽可能深入，再回溯；
# 2) 可用递归或栈实现；
# 3) 适合搜索连通性、路径、拓扑排序等问题；
# 4) visited 集合用于防止重复访问；
# 5) 时间复杂度 O(V + E)，空间复杂度取决于递归深度或栈。
# */

# 图的邻接表：
# A -> ['B', 'C']
# B -> ['D']
# C -> ['D']
# D -> ['E']
# E -> []

# 深度优先搜索 DFS 结果：A B D E C