I saw an implementation of breadth-first-search that's slightly different from what I've learned. What's the benefit of using three states "Unvisited, Visited, Visiting" for bfs? Or is it just a matter of taste?
Problem: find out whether there's a route between two nodes in a graph.
public enum State {
Unvisited, Visited, Visiting;
}
public static boolean search(Graph g,Node start,Node end) {
LinkedList<Node> q = new LinkedList<Node>();
for (Node u : g.getNodes()) {
u.state = State.Unvisited;
}
start.state = State.Visiting;
q.add(start);
Node u;
while(!q.isEmpty()) {
u = q.removeFirst();
if (u != null) {
for (Node v : u.getAdjacent()) {
if (v.state == State.Unvisited) {
if (v == end) {
return true;
} else {
v.state = State.Visiting;
q.add(v);
}
}
}
u.state = State.Visited;
}
}
return false;
}
Source: Gayle McDowell's Cracking the Coding Interview
question from:
https://stackoverflow.com/questions/65886613/comparing-two-breadth-first-search-implementations 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…