在无向图中查找路径 BFS - Java

Question

我正在编写一个程序来处理具有未加权边的无向图，因为我是一名学习者，所以遇到了一些问题。

我必须创建一个方法（与主方法相同 class）来接收图形、初始顶点和结束顶点。然后我必须找到是否有从 vertex1 到 vertex2 的路径并将中间顶点存储在队列中然后打印它（它不一定是最短的，ofc 如果可能的话更好但不是真的需要它）。

假设我有：

Graph

我想从

获得唯一的一条路径

我已经实现了一个 bfs 方法，如下所示，用于我也有的其他方法，但我不知道如何开始使用我需要的这个方法。我的 bfs 方法：

    public static Queue<DecoratedInmate> bfs (Graph gr, Vertex<DecoratedInmate> v){
    Queue<Vertex<DecoratedInmate>> vertices = new LinkedList<Vertex<DecoratedInmate>>();   //temporal queue
    Queue<DecoratedInmate> traversal = new LinkedList<DecoratedInmate>();   //traversal queue
    Vertex<DecoratedInmate> u;  //vertex taken from queue
    Vertex<DecoratedInmate> z;  //opposite vertex of u
    Edge e; //edge between vertices
    Iterator<Edge<DecoratedInmate>> it; //to store incident edges
    v.getElement().setVisited(true);    //set received vertex to visited
    vertices.offer(v); //add origin vertex to queue
    while (!vertices.isEmpty()) {  //if queue isn't empty
        u = vertices.remove(); //take vertex from queue
        traversal.offer(u.getElement());    //add element to list
        it = gr.incidentEdges(u);   //get incident edges of u
        while (it.hasNext()) {  //check if there are incident edges
            e = it.next();      //assign the edge
            z = gr.opposite(u, e);  //assign opposite vertex of u
            if (!z.getElement().getVisited()) { //check if the opposite is not visited
                z.getElement().setVisited(true);    //set to visited
                vertices.offer(z); //add to queue
            }
        }
    }
    return traversal;
}

提前致谢

Answer 1

我对你的问题的理解是你试图找到从一个节点到另一个节点的路径，而不一定是如何访问它们。所以这是一个实现。当运行 bfs时，存储每个顶点父节点即

    public static void Bfs(Vertex source) {
    vertex = GraphifyGUI.getNode();
    reset();
    q = new LinkedList<>(); // FIFO
    source.wasVisited = true; // marked as visited
    q.add(source); // put into queue
    source.parent = source; // set parent
    conn = new ArrayList<>();
    while (!q.isEmpty()) { // source
        Vertex current = q.poll(); // remove first 
        conn.add(current.getId());
        Iterator<Vertex> currentList = current.vList().iterator();
        while (currentList.hasNext()) {
            Vertex next = currentList.next();
            if (next.wasVisited == false) {
                next.wasVisited = true;
                q.add(next);
                next.parent = current;
                GG.printlnConsole(next.getName() + " has type of " + next.getType());
            }
        }
    }
    GG.printlnConsole("Order is " + conn);
}

然后获取最短路径的方法如下所示

   public void shortestPath(int v, int e) {
    if (e == v) {
        GG.printlnConsole(v + "-->" + v);
        return;
    }
    for (int i = e; i >= 0; i = vertex.get(i).getParent().getId()) {
        if (i == v) {
            break;
        }
        if (vertex.get(i).getParent().getId() != -1) {
            set.put(vertex.get(i).getParent().getId(), i);
        }
    }
}

上面shortestPath的解释

if this source is the same as destination then that is shortest path
for(i = destination; i >= 0; i = parent of i){
    if(i == source) we are done;
    if(parent of i is a node) add as path;

Answer 2

谢谢 Fafore 我已经解决了。我所做的是将所有相邻节点设置为结束顶点并将它们存储在堆栈中，而它们与起始顶点不同。然后我做了一段时间直到堆栈为空并开始检查哪个与起始顶点相邻然后哪个在它们之间相邻（因为堆栈的第一个与结束顶点相邻）然后将相邻的添加到一个队列。它不需要是最短路径，但谢谢=)

在无向图中查找路径 BFS - Java

Find path in an undirected graph BFS - Java

java

graph

path

vertices