我正在寻找一个非二叉树的非递归深度优先搜索算法。任何帮助都非常感激。
当前回答
使用堆栈来跟踪节点
Stack<Node> s;
s.prepend(tree.head);
while(!s.empty) {
Node n = s.poll_front // gets first node
// do something with q?
for each child of n: s.prepend(child)
}
其他回答
使用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;
}
Java中的DFS迭代:
//DFS: Iterative
private Boolean DFSIterative(Node root, int target) {
if (root == null)
return false;
Stack<Node> _stack = new Stack<Node>();
_stack.push(root);
while (_stack.size() > 0) {
Node temp = _stack.peek();
if (temp.data == target)
return true;
if (temp.left != null)
_stack.push(temp.left);
else if (temp.right != null)
_stack.push(temp.right);
else
_stack.pop();
}
return false;
}
如果你有指向父节点的指针,你可以在没有额外内存的情况下完成。
def dfs(root):
node = root
while True:
visit(node)
if node.first_child:
node = node.first_child # walk down
else:
while not node.next_sibling:
if node is root:
return
node = node.parent # walk up ...
node = node.next_sibling # ... and right
注意,如果子节点存储为数组而不是通过兄弟指针,那么下一个兄弟节点可以通过以下方式找到:
def next_sibling(node):
try:
i = node.parent.child_nodes.index(node)
return node.parent.child_nodes[i+1]
except (IndexError, AttributeError):
return None
PreOrderTraversal is same as DFS in binary tree. You can do the same recursion
taking care of Stack as below.
public void IterativePreOrder(Tree root)
{
if (root == null)
return;
Stack s<Tree> = new Stack<Tree>();
s.Push(root);
while (s.Count != 0)
{
Tree b = s.Pop();
Console.Write(b.Data + " ");
if (b.Right != null)
s.Push(b.Right);
if (b.Left != null)
s.Push(b.Left);
}
}
一般的逻辑是,将一个节点(从根开始)推入Stack, Pop()它和Print()值。然后,如果它有子节点(左和右),将它们推入堆栈-先推右,这样你就会先访问左子节点(在访问节点本身之后)。当stack为空()时,您将访问Pre-Order中的所有节点。
你可以使用堆栈。我用邻接矩阵实现了图:
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();
}
}
}