实现深度优先图遍历

Question

我对深度优先遍历的信息存在矛盾，希望能得到一些帮助，了解如何构建程序。给定一个特定的图形，我想打印出顶点的序列。用户将输入要从哪个节点开始遍历。我正在查看不同的示例，但我不理解深度优先遍历的顺序如何工作。我有以下伪代码可供使用：

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;
}

- Raging Java

---

+1 为添加作业标签加分！ - squawknull

Answer 1

这两个片段的关键在于以下思路：

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的子级应用完全相同的功能，以此类推。这就是为什么它被称为深度优先搜索，因为您的搜索将首先搜索路径中最低可能的一组子级，然后返回检查其余的子级。

- Carlos Daniel Gadea Omelchenko