如何获取有向图DFS森林中的树根？是否需修改DFS算法？

不需要修改DFS的核心遍历逻辑，只需在全图DFS的主流程中记录每次启动DFS的初始顶点即可，具体逻辑如下：

• 标准全图DFS的执行逻辑是：遍历图中所有顶点，对每个未被访问过的顶点，启动一次DFS遍历。
• 每次启动DFS的这个未访问顶点，就是DFS森林中一棵新树的树根。
• 实现时只需要维护一个记录访问状态的数组，以及一个存储树根的列表：在主循环里，发现未访问顶点时，先将其加入树根列表，再调用DFS处理该顶点。

伪代码示例 #

# 初始化状态
visited = [False] * 顶点总数
roots = []

# 全图遍历主流程
for u in 所有顶点:
    if not visited[u]:
        roots.append(u)
        dfs(u)

# 标准DFS核心函数
def dfs(u):
    visited[u] = True
    for v in u的邻接顶点:
        if not visited[v]:
            dfs(v)

这个方案完全基于标准DFS算法，仅在主流程中增加了树根记录的步骤，无需修改DFS的核心遍历逻辑。

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