我正在寻找一个非二叉树的非递归深度优先搜索算法。任何帮助都非常感激。
当前回答
你可以使用堆栈。我用邻接矩阵实现了图:
void DFS(int current){
for(int i=1; i<N; i++) visit_table[i]=false;
myStack.push(current);
cout << current << " ";
while(!myStack.empty()){
current = myStack.top();
for(int i=0; i<N; i++){
if(AdjMatrix[current][i] == 1){
if(visit_table[i] == false){
myStack.push(i);
visit_table[i] = true;
cout << i << " ";
}
break;
}
else if(!myStack.empty())
myStack.pop();
}
}
}
其他回答
伪代码基于@biziclop的答案:
只使用基本结构:变量、数组、if、while和for 函数getNode(id)和getChildren(id) 假设已知节点数N
注意:我从1开始使用数组索引,而不是0。
广度优先
S = Array(N)
S[1] = 1; // root id
cur = 1;
last = 1
while cur <= last
id = S[cur]
node = getNode(id)
children = getChildren(id)
n = length(children)
for i = 1..n
S[ last+i ] = children[i]
end
last = last+n
cur = cur+1
visit(node)
end
深度优先
S = Array(N)
S[1] = 1; // root id
cur = 1;
while cur > 0
id = S[cur]
node = getNode(id)
children = getChildren(id)
n = length(children)
for i = 1..n
// assuming children are given left-to-right
S[ cur+i-1 ] = children[ n-i+1 ]
// otherwise
// S[ cur+i-1 ] = children[i]
end
cur = cur+n-1
visit(node)
end
你可以使用一个堆栈来保存尚未访问的节点:
stack.push(root)
while !stack.isEmpty() do
node = stack.pop()
for each node.childNodes do
stack.push(stack)
endfor
// …
endwhile
虽然“使用堆栈”可能是人为的面试问题的答案,但实际上,它只是显式地做递归程序在幕后所做的事情。
递归使用程序内置堆栈。当你调用一个函数时,它将函数的参数推入堆栈,当函数返回时,它通过弹出程序堆栈来执行。
这是一个java程序的链接,显示DFS同时遵循递归和非递归方法,还计算发现和完成时间,但没有边对齐。
public void DFSIterative() {
Reset();
Stack<Vertex> s = new Stack<>();
for (Vertex v : vertices.values()) {
if (!v.visited) {
v.d = ++time;
v.visited = true;
s.push(v);
while (!s.isEmpty()) {
Vertex u = s.peek();
s.pop();
boolean bFinished = true;
for (Vertex w : u.adj) {
if (!w.visited) {
w.visited = true;
w.d = ++time;
w.p = u;
s.push(w);
bFinished = false;
break;
}
}
if (bFinished) {
u.f = ++time;
if (u.p != null)
s.push(u.p);
}
}
}
}
}
这里是完整的源代码。
使用Stack,以下是要遵循的步骤:
如果可能,访问一个相邻的未访问顶点,标记它, 然后把它推到堆栈上。 如果您不能遵循第1步,那么,如果可能的话,弹出一个顶点 堆栈。 如果你不能遵循第1步或第2步,你就完了。
下面是执行上述步骤的Java程序:
public void searchDepthFirst() {
// begin at vertex 0
vertexList[0].wasVisited = true;
displayVertex(0);
stack.push(0);
while (!stack.isEmpty()) {
int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
// if no such vertex
if (adjacentVertex == -1) {
stack.pop();
} else {
vertexList[adjacentVertex].wasVisited = true;
// Do something
stack.push(adjacentVertex);
}
}
// stack is empty, so we're done, reset flags
for (int j = 0; j < nVerts; j++)
vertexList[j].wasVisited = false;
}