实现深度优先图遍历

我有关于深度优先遍历的冲突信息，并且可以在理解如何构建程序时使用一些帮助。给定一个图，我想打印一个顶点序列。用户将输入一个特定的节点来开始遍历。我正在看不同的例子，我不明白深度优先遍历的顺序是如何工作的。我有以下的伪代码一起工作：实现深度优先图遍历

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

来源

2011-04-23 Raging Java

+1添加作业标签！ – squawknull 2011-04-23 01:52:32

的关键，这两个片段的有以下几种思路：

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的孩子将会应用完全相同的功能，等等。这就是为什么它被称为深度优先搜索的原因，因为在返回检查剩余的孩子之前，您的搜索将首先搜索路径中尽可能少的一组儿童。

来源

2011-04-23 01:53:12

实现深度优先图遍历

回答

相关问题