BFS(广度优先搜索)-在Java中不计算最短路径

Question

我在Java中使用BFS算法计算最短路径时遇到了一个问题。

当我试图定义从节点0到节点7的路径时，我得到了这个结果。(0 -> 2 -> 3 -> 4 -> 5)

如何解决这个问题?

这是我的节点类

public class Node {
private final int value;
private final Set<Node> siblingNodes;
public Node(int value) {
this.value = value;
siblingNodes = new HashSet<Node>();
}
public Set<Node> getSiblingNodes() {
return siblingNodes;
}
public boolean equals(Node compareTo) {
return (compareTo.getValue() == value);
}
public int getValue() {
return value;
}
public void addSiblingNode(Node node) {
siblingNodes.add(node); 
}
}

下面是代码片段:

public static void main(String[] args) {
/**
*
*        1             -> 5
* 0 ->           -> 4
*        2 -> 3        -> 6    -> 7
*
*/
Node node0 = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
node0.addSiblingNode(node1);
node0.addSiblingNode(node2);    
Node node3 = new Node(3);
node2.addSiblingNode(node3);
Node node4 = new Node(4);
node3.addSiblingNode(node4);
Node node5 = new Node(5);
Node node6 = new Node(6);
node4.addSiblingNode(node5);
node4.addSiblingNode(node6);

Node node7 = new Node(7);
node6.addSiblingNode(node7);
List<Node> shortestPath = getDirections(node0, node7);
for(Node node : shortestPath) {
System.out.println(node.getValue());
}
}
public static List<Node> getDirections(Node sourceNode, Node destinationNode) {
// Initialization.
Map<Node, Node> nextNodeMap = new HashMap<Node, Node>();
Node currentNode = sourceNode;
Node previousNode = sourceNode;
// Queue
Queue<Node> queue = new LinkedList<Node>();
queue.add(currentNode);
/*
* The set of visited nodes doesn't have to be a Map, and, since order
* is not important, an ordered collection is not needed. HashSet is 
* fast for add and lookup, if configured properly.
*/
Set<Node> visitedNodes = new HashSet<Node>();
visitedNodes.add(currentNode);
//Search.
while (!queue.isEmpty()) {
currentNode = queue.remove();
if (currentNode.equals(destinationNode)) {
// Handle case where the node leading to the destinatino node
// itself pointed to multiple nodes. In this case,
// nextNodeMap is incorrect and we need to rely on the previously
// seen node.
// Also need to check for edge-case of start node == end node.
if (!previousNode.equals(currentNode)) {
nextNodeMap.put(previousNode, currentNode);
}
break;
} else {
for (Node nextNode : currentNode.getSiblingNodes()) {
if (!visitedNodes.contains(nextNode)) {
queue.add(nextNode);
visitedNodes.add(nextNode);
// Look up of next node instead of previous.
nextNodeMap.put(currentNode, nextNode);
previousNode = currentNode;
}
}
}
}
// If all nodes are explored and the destination node hasn't been found.
if (!currentNode.equals(destinationNode)) {
throw new RuntimeException("No feasible path.");
}
// Reconstruct path. No need to reverse.
List<Node> directions = new LinkedList<Node>();
for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) {
directions.add(node);
}
return directions;
}
}

Answer 1

使用Map来构建节点之间的路径是个好主意。但可能的是，您正在重写值，因为不能有多个具有相同键的条目(4 -> 6已被4 -> 5覆盖，并且您收到了不正确的结果)。

为了解决这个问题，我们可以反向映射，即键表示兄弟节点(键是唯一的)，而值表示父节点(值可以重复)。当找到destination节点(或访问了所有节点)时，路径将以反向顺序重建，即从destination到source

(我们需要反转列表)。 也注意访问节点的HashSet是多余的，因为这些信息已经反映在Map中。

BFS的实现可能是这样的:

public static List<Node> getDirections(Node source, Node destination) {
Map<Node, Node> paths = new HashMap<>(); // Map of paths also allows to track the visited nodes
Queue<Node> queue = new ArrayDeque<>();  // is more performant than LinkedList
queue.add(source);
paths.put(source, null); // the starting point of the path

boolean isFound = false;

while (!isFound && !queue.isEmpty()) {
Node current = queue.remove();

for (Node sibling : current.getSiblingNodes()) {
if (paths.containsKey(sibling)) continue;
// update the Map of paths
paths.put(sibling, current);
// the target node was found
if (sibling.equals(destination)) {
isFound = true; // we need to terminate the search, no need to explore all nodes if the path is found
break;
}
queue.add(sibling); // adding the sibling to the queue
}
}
return getPath(source, destination, paths);
}

生成路径的辅助方法:

public static List<Node> getPath(Node start, Node end, Map<Node, Node> paths) {
List<Node> path = new ArrayList<>();
Node current = end;
path.add(current);
while (current != start && current != null) { // if there's no path from start to end current eventually will become null
path.add(paths.get(current));
current = paths.get(current);
}
Collections.reverse(path);
return current != null ? path : Collections.emptyList();
}

注意Node类中的equals()实现实际上并不覆盖java.lang.Object.equals()，因为签名不匹配。此外，hashCode()的实现缺失，这违背了equals()的契约。因此，在基于散列的集合中，将使用equals和hashCode的默认实现。它没有在原始代码中造成麻烦，只是因为OP实际上使用了相同的对象。

下面是一个正确实现的例子:

public class Node {
private final int value;
private final Set<Node> siblingNodes = new HashSet<>();

// constructor, getters, addSiblingNode(), etc.

@Override
public boolean equals(Object o) {
return o instanceof Node other && value == other.value;
}

@Override
public int hashCode() {
return Objects.hash(value);
}
}

main()

public static void main(String[] args) {
// sample data from the question

List<Node> shortestPath = getDirections(node0, node7);

String path = shortestPath.stream()
.map(Node::getValue)
.map(String::valueOf)
.collect(Collectors.joining(" -> "));
System.out.println(path);
}

输出:

0 -> 2 -> 3 -> 4 -> 6 -> 7

Answer 2

您的getDirections()实现似乎是正确的。但是Node类有一个问题。应该将以下两个方法添加到Node中。这些是在Map或Set中存储Node对象所需要的。

@Override
public int hashCode() {
return value;
}
@Override
public boolean equals(Object obj) {
return obj instanceof Node n
&& n.value == value;
}

输出:

0
2
3
4
6
7