如何将有向无权图转换为以指定顶点为根的树？

你要的这个从指定顶点出发生成的树本质是单源可达树，仅保留从源点出发可到达的节点，以及沿遍历方向的父子关联边，不会包含环和反向不可达的边，具体实现逻辑如下：

算法选择 #

• 优先选BFS（广度优先搜索）生成树：因为是无权图，BFS生成的树自带最短路径属性，输出的路径都是从源点到对应节点的最短路径，适配大部分通用场景
• 可选DFS（深度优先搜索）生成树：如果你需要优先遍历深度更深的分支、或者要获取所有可能的简单路径（不含环的路径）可以用该方案，注意要加访问标记避免环导致的死循环

通用实现步骤 #

1. 存储结构预处理：优先把图整理为邻接表形式，遍历效率远高于邻接矩阵，结构可以存为dict[顶点, 所有邻接出边顶点列表]
2. 初始化变量：
   • 用集合存储已访问的节点，避免重复遍历
   • 用字典存储父子边映射，格式为子节点: 父节点，后续用来还原路径
   • 用队列（BFS场景）或者栈（DFS场景）存储待遍历的节点，初始时把指定的源顶点放入容器，同时标记为已访问
3. 遍历逻辑：
   • 每次从队列/栈取出一个当前节点
   • 遍历它所有出边指向的邻接节点
   • 如果邻接节点未被访问过，就标记为已访问，记录它的父节点为当前节点，再把这个邻接节点加入待遍历容器
4. 路径还原：拿到父子边映射后，要获取到某节点的路径就从该节点倒序遍历父节点直到源点，再反转列表即可得到从源点出发的正向路径
5. 特殊场景适配：如果需要获取所有可能的简单路径而不是仅最短路径，遍历的时候不要设置全局已访问标记，改为给每条路径单独记录当前走过的节点集合，遇到重复节点就终止当前分支的遍历即可

Python示例代码（BFS生成可达树+路径查询） #

# 示例有向无权图邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# 生成BFS可达树
def bfs_generate_tree(graph, source):
    visited = set([source])
    parent_map = {source: None}
    queue = [source]
    while queue:
        current = queue.pop(0)
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent_map[neighbor] = current
                queue.append(neighbor)
    return parent_map, visited

# 从父子映射中还原路径
def get_path(parent_map, source, target):
    if target not in parent_map:
        return None # 源点不可达该节点
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = parent_map[current]
    return path[::-1] # 反转得到从源点出发的正向路径

# 测试用例
parent_map, reachable_nodes = bfs_generate_tree(graph, 'A')
print(get_path(parent_map, 'A', 'F')) # 输出 ['A', 'C', 'F']，为源点到F的最短路径

注意事项 #

• 有向图中如果存在从源点出发可到达的环，全局已访问标记会自动截断环的遍历，不会出现死循环
• 从源点不可达的节点不会被纳入生成树中，也查询不到对应路径

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