java - 在java中制作深度优先搜索算法

Question

我有以下有向图实现

 Nodes nod[]
 List<Arcs> arc[]

因此，第 n 个位置的节点在位置 n 处具有列表的所有弧。当然，节点是相应组织的，因此我可以使用 Binary Search。基于此实现。我希望创建一个 DFS 算法。伪代码我很熟悉，适应java应该不是问题。

但我的问题如下。在 DFS 中，我们需要从“顶部”节点开始搜索。想想看，我没有这个“顶级”节点。此外，我不知道如何获得它。所以我问，考虑到我的实现，我如何获得这个顶级节点？

谢谢您的帮助。

Answer 1

扩展我的评论：

假设弧是定向的（即，仅从父节点到子节点），您可以在所有节点中搜索没有传入弧的节点：

// parent_count is an integer array of the same size as nod[]

for i = 1..n
    for each arc in arc[i] (arc going from i to j)
        increment parent_count[j]
    end
end

for k = 1..n
    if parent_count[k] == 0
        return k
end

Answer 2

DFS/BFS 是非常常见的遍历图的通用算法，两者都没有顶部节点的特殊含义，您可以从任何节点启动 DFS。例如，DFS 用于拓扑排序算法，它指出我们必须从没有传入边的节点开始。

您能否突出显示您要解决的问题？这应该有助于我们找到必须用作 DFS 根的节点。