Python如何对边为元组列表的图实现递归DFS遍历

你需要先把输入的边列表转换为便于遍历的邻接表结构，再通过递归逻辑实现深度优先搜索，过程中需要记录已访问节点避免环结构导致的无限递归，同时覆盖图中所有不连通分量保证遍历到全部节点。

实现步骤 #

• 第一步：解析边列表，构建邻接表。邻接表用字典存储，键为节点，值为该节点直接连通的相邻节点列表，同时收集全量节点用于后续全图遍历。
• 第二步：实现递归DFS核心逻辑：访问当前节点时标记为已访问、加入遍历结果，再依次递归遍历当前节点所有未访问的邻接节点。
• 第三步：遍历所有未访问的节点作为DFS起点，避免遗漏不连通分量里的节点。

完整可运行代码 #

def build_adjacency_list(edges):
    adj = {}
    all_nodes = set()
    for u, v in edges:
        all_nodes.add(u)
        all_nodes.add(v)
        # 按有向边构建：u -> v，如果是无向图，额外添加adj[v].append(u)即可
        if u not in adj:
            adj[u] = []
        adj[u].append(v)
    return adj, all_nodes

def dfs_recursive(current, adj, visited, result):
    # 标记当前节点为已访问，加入结果列表
    visited.add(current)
    result.append(current)
    # 遍历所有邻接节点，未访问则递归深入
    for neighbor in adj.get(current, []):
        if neighbor not in visited:
            dfs_recursive(neighbor, adj, visited, result)

def dfs_traverse_all_nodes(edges):
    adj, all_nodes = build_adjacency_list(edges)
    visited = set()
    traverse_result = []
    # 遍历所有节点，从未访问的节点启动DFS，覆盖全部分量
    for node in all_nodes:
        if node not in visited:
            dfs_recursive(node, adj, visited, traverse_result)
    return traverse_result

# 测试示例
edges = [('human', 'mammal'), ('mammal', 'vertebrate'), ('mouse', 'mammal'), ('vertebrate', 'animal')]
print(dfs_traverse_all_nodes(edges))

补充说明 #

以上测试用例的典型DFS输出为['human', 'mammal', 'vertebrate', 'animal', 'mouse']，邻接节点的遍历顺序和边列表的输入顺序一致，如果需要调整遍历优先级，可以在构建邻接表后对每个节点的邻接列表做自定义排序。

注意：如果图存在环结构，visited集合会拦截重复访问的节点，不会出现无限递归的问题。如果只需要从指定起点开始遍历，直接调用dfs_recursive(指定起点, adj, set(), [])即可拿到对应起点出发的DFS遍历结果。

内容的提问来源于stack exchange，提问作者sujaypatil