拓扑排序与DFS的区别仅在于,
- 在拓扑排序的情况下,处理(添加到输出)当前元素的stack)在递归调用后完成,而
- 在DFS的情况下,当前元素被处理(即打印或添加到输出队列)之前的递归调用?
public void depthfirstsearchrecursive()
{
for(int i = 0;i<vertices.size();i++)
{
if(vertices.get(i).isVisited == false)
{
vertices.get(i).isVisited = true;
System.out.println(vertices.get(i).name + " ");
depthfirstsearchrecursiveUtil(vertices.get(i));
}
}
}
public void depthfirstsearchrecursiveUtil(Vertex v)
{
for(int i = 0;i<v.neighbors.size();i++)
{
if(v.neighbors.get(i).isVisited == false)
{
v.neighbors.get(i).isVisited = true;
System.out.println(v.neighbors.get(i).name + " ");
depthfirstsearchrecursiveUtil(v.neighbors.get(i));
}
}
}
如您所见,我先打印元素,然后进行递归调用。
这是我的拓扑排序实现
/* topological sort recursive */
public void topologicalsortrecursive()
{
Stack<Vertex> output = new Stack<Vertex>();
for(int i = 0;i<vertices.size();i++)
{
if(vertices.get(i).isVisited == false)
{
vertices.get(i).isVisited = true;
topologicalsortrecursiveDriver(vertices.get(i), output);
// System.out.println(vertices.get(i).name + " ");
output.push(vertices.get(i));
}
}
}
public void topologicalsortrecursiveDriver(Vertex v, Stack<Vertex> output)
{
for(int i = 0;i<v.neighbors.size();i++)
{
if(v.neighbors.get(i).isVisited == false)
{
v.neighbors.get(i).isVisited = true;
topologicalsortrecursiveDriver(v.neighbors.get(i), output);
// System.out.println(v.neighbors.get(i).name + " ");
output.push(v.neighbors.get(i));
}
}
}
这里,处理(压入堆栈,在递归调用之后完成)
是真的吗?
- DFS类似于PreOrder遍历,在这里我们处理元素,然后到它的子节点,而
- 拓扑排序就像一个反向后序遍历,我们去哪里先到子元素,然后处理当前元素,通过推入(这就是为什么我说反转 postder)
不完全是。DFS是通用形式。您可以使用它来实现预排序和/或后排序的求值。
拓扑排序需要后求值DFS。
考虑以下代码:
void DFS(Vertex v) {
if (v.hasVisited)
return;
v.hasVisited = true;
doBeforeDepth(v)
for (Vertex u : v.neighbours)
DFS(u);
doAfterDepth(v);
}
void DFS()
{
for (Vertex v : vertices)
DFS(v);
}
您可以使用这个DFS代码来执行拓扑排序。