v*n
1 楼
Anyone gives an iterative graph dfs algorithm. My implementation in Java is
as follows. It works but look a little wired to me.
public void dfsIterative(Vertex v) {
v.isVisited = true;
Stack s = new Stack();
System.out.print(v.label + " ");
for (Vertex u: v.adj()) {
s.push(u);
}
while (!s.empty()) {
Vertex u = s.pop();
for (Vertex w : u.adj()) {
if (!w.isVisited) {
w.isVisited = true;
s.push(w);
System.out.print(w.label + " ");
}
}
}
System.out.println();
}
as follows. It works but look a little wired to me.
public void dfsIterative(Vertex v) {
v.isVisited = true;
Stack
System.out.print(v.label + " ");
for (Vertex u: v.adj()) {
s.push(u);
}
while (!s.empty()) {
Vertex u = s.pop();
for (Vertex w : u.adj()) {
if (!w.isVisited) {
w.isVisited = true;
s.push(w);
System.out.print(w.label + " ");
}
}
}
System.out.println();
}
