gpt4 book ai didi

java - 双向图搜索的实现

转载 作者:搜寻专家 更新时间:2023-10-31 08:18:55 26 4
gpt4 key购买 nike

我正在尝试实现 bi-directional graph search .据我了解,我应该以某种方式合并两个广度优先搜索,一个从起始(或根)节点开始,另一个从目标(或结束)节点开始。当两个广度优先搜索在同一顶点“相遇”时,双向搜索终止。

您能否为我提供一个代码示例(如果可能,使用 Java)或双向图搜索代码链接?

最佳答案

假设你有像这样的 Node(在文件 Node.java 中):

import java.util.HashSet;
import java.util.Set;

public class Node<T> {
private final T data; // The data that you want to store in this node.
private final Set<Node> adjacentNodes = new HashSet<>();

// Constructor
public Node(T data) {
this.data = data;
}

// Getters

/*
* Returns the data stored in this node.
* */
public T getData() {
return data;
}

/*
* Returns a set of the adjacent nodes of this node.
* */
public Set<Node> getAdjacentNodes() {
return adjacentNodes;
}

// Setters

/*
* Attempts to add node to the set of adjacent nodes of this node. If it was not previously added, it is added, and
* true is returned. If it was previously added, it returns false.
* */
public boolean addAdjacent(Node node) {
return adjacentNodes.add(node);
}
}

然后双向搜索算法(在文件 BidirectionalSearch.java 中定义)看起来像这样:

import java.util.HashSet;
import java.util.Queue;
import java.util.Set;
import java.util.LinkedList;


public class BidirectionalSearch {

/*
* Returns true if a path exists between Node a and b, false otherwise.
* */
public static boolean pathExists(Node a, Node b) {
// LinkedList implements the Queue interface, FIFO queue operations (e.g., add and poll).

// Queue to hold the paths from Node a.
Queue<Node> queueA = new LinkedList<>();

// Queue to hold the paths from Node a.
Queue<Node> queueB = new LinkedList<>();

// A set of visited nodes starting from Node a.
Set<Node> visitedA = new HashSet<>();

// A set of visited nodes starting from Node b.
Set<Node> visitedB = new HashSet<>();

visitedA.add(a);
visitedB.add(b);

queueA.add(a);
queueB.add(b);

// Both queues need to be empty to exit the while loop.
while (!queueA.isEmpty() || !queueB.isEmpty()) {
if (pathExistsHelper(queueA, visitedA, visitedB)) {
return true;
}
if (pathExistsHelper(queueB, visitedB, visitedA)) {
return true;
}
}

return false;
}

private static boolean pathExistsHelper(Queue<Node> queue,
Set<Node> visitedFromThisSide,
Set<Node> visitedFromThatSide) {
if (!queue.isEmpty()) {
Node next = queue.remove();

Set<Node> adjacentNodes = next.getAdjacentNodes();

for (Node adjacent : adjacentNodes) {

// If the visited nodes, starting from the other direction,
// contain the "adjacent" node of "next", then we can terminate the search
if (visitedFromThatSide.contains(adjacent)) {
return true;
} else if (visitedFromThisSide.add(adjacent)) {
queue.add(adjacent);
}
}
}
return false;
}

public static void main(String[] args) {
// Test here the implementation above.
}
}

关于java - 双向图搜索的实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38674659/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com