使用 BFS 查找节点是否可达
Find if a node is reachable using BFS
我正在使用 BFS 检查节点是否可达并打印路由。
谁能解释为什么在这种情况下 BFS 比 DFS 更受欢迎?
使用以下代码:
LinkedList<String> queue = new LinkedList<String>();
HashSet<String> visitedNodes = new LinkedHashSet<String> ();
queue.add(source);
visitedNodes.add(source);
while (!queue.isEmpty()) {
String focusNode = queue.poll();
Set<Node> nodeSet = inputMap.getAllOutgoingNodes(focusNode);
if (null != nodeSet) {
for (Node s: nodeSet) {
if (!visitedNodes.contains(s.edge1)) {
visitedNodes.add(s.edge1);
queue.add(s.edge1);
if (destination.equals(s.edge1)) {
for (String sn: visitedNodes) {
System.out.print(sn);
break;
}
}
}
}
}
如果问题是检查节点是否可达,那么我认为 DFS 是首选(通常只是为了代码长度),如果你还必须找到一条路由,那么使用 DFS 找到的路由可能非常好很长(而且对于人类来说很难检查),因此 BFS 是首选。
但总之没有统一的规则,全看个人喜好了。
我正在使用 BFS 检查节点是否可达并打印路由。 谁能解释为什么在这种情况下 BFS 比 DFS 更受欢迎? 使用以下代码:
LinkedList<String> queue = new LinkedList<String>();
HashSet<String> visitedNodes = new LinkedHashSet<String> ();
queue.add(source);
visitedNodes.add(source);
while (!queue.isEmpty()) {
String focusNode = queue.poll();
Set<Node> nodeSet = inputMap.getAllOutgoingNodes(focusNode);
if (null != nodeSet) {
for (Node s: nodeSet) {
if (!visitedNodes.contains(s.edge1)) {
visitedNodes.add(s.edge1);
queue.add(s.edge1);
if (destination.equals(s.edge1)) {
for (String sn: visitedNodes) {
System.out.print(sn);
break;
}
}
}
}
}
如果问题是检查节点是否可达,那么我认为 DFS 是首选(通常只是为了代码长度),如果你还必须找到一条路由,那么使用 DFS 找到的路由可能非常好很长(而且对于人类来说很难检查),因此 BFS 是首选。
但总之没有统一的规则,全看个人喜好了。