我正在寻找一个非二叉树的非递归深度优先搜索算法。任何帮助都非常感激。
当前回答
如果你有指向父节点的指针,你可以在没有额外内存的情况下完成。
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
其他回答
如果你有指向父节点的指针,你可以在没有额外内存的情况下完成。
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
完整的示例工作代码,没有堆栈:
import java.util.*;
class Graph {
private List<List<Integer>> adj;
Graph(int numOfVertices) {
this.adj = new ArrayList<>();
for (int i = 0; i < numOfVertices; ++i)
adj.add(i, new ArrayList<>());
}
void addEdge(int v, int w) {
adj.get(v).add(w); // Add w to v's list.
}
void DFS(int v) {
int nodesToVisitIndex = 0;
List<Integer> nodesToVisit = new ArrayList<>();
nodesToVisit.add(v);
while (nodesToVisitIndex < nodesToVisit.size()) {
Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
for (Integer s : adj.get(nextChild)) {
if (!nodesToVisit.contains(s)) {
nodesToVisit.add(nodesToVisitIndex, s);// add the node to the HEAD of the unvisited nodes list.
}
}
System.out.println(nextChild);
}
}
void BFS(int v) {
int nodesToVisitIndex = 0;
List<Integer> nodesToVisit = new ArrayList<>();
nodesToVisit.add(v);
while (nodesToVisitIndex < nodesToVisit.size()) {
Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
for (Integer s : adj.get(nextChild)) {
if (!nodesToVisit.contains(s)) {
nodesToVisit.add(s);// add the node to the END of the unvisited node list.
}
}
System.out.println(nextChild);
}
}
public static void main(String args[]) {
Graph g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.addEdge(3, 1);
g.addEdge(3, 4);
System.out.println("Breadth First Traversal- starting from vertex 2:");
g.BFS(2);
System.out.println("Depth First Traversal- starting from vertex 2:");
g.DFS(2);
}}
输出: 宽度优先遍历-从顶点2开始: 2 0 3. 1 4 深度优先遍历-从顶点2开始: 2 3. 4 1 0
伪代码基于@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
这是一个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);
}
}
}
}
}
这里是完整的源代码。
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中的所有节点。