java - 实现深度优先的图遍历

关于深度优先遍历的信息有冲突，可以在理解如何构建程序方面提供一些帮助。给定一个特定的图，我想打印一系列顶点。用户将输入一个特定的节点以开始遍历。我正在查看不同的示例，但我不了解深度优先遍历的顺序是如何工作的。我有以下伪代码可以使用:

public DFS() {
    DFS(v)
    {   num(v) = i ++;
       for all vertices u adjacent to v
       { if num(u) is 0
            attach edge(uv) to edges;
            DFS(u);
        }
    }



depthFirstSearch()
{     for all vertices v
        num(v) = 0;
  edges = null; //vector of all edges
  i=1;
  while there is a vertex v such that num(v) is 0
         DFS(v);
  output edges;
}

最佳答案

这两个片段的关键是以下想法:

check if item found at (v)
if item not found,
   for all vertices u adjacent to v
     depth_first_search(u)

而不是立即检查所有节点(v)个子节点(u的列表)的结束条件，而是仅在当前节点v上进行检查。如果不满足结束条件，则应用相同的深度优先搜索功能从v的第一个孩子u1开始。由于u1也可能有孩子，因此在处理v的其余孩子之前，将完全相同的功能应用于u1的孩子，依此类推。这就是为什么将其称为深度优先搜索的原因，因为您的搜索将首先搜索路径中可能的最低子集，然后再返回以检查剩余的子项。

关于java - 实现深度优先的图遍历，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5761575/