java

jslywgbw  于 2021-07-06  发布在  Java
关注(0)|答案(0)|浏览(238)

我有一个bfs方法,它在邻接列表中查找两个节点之间的路径。但是,我注意到如果我索引无序的节点,那么它将找不到路径。
这是我的密码:

public boolean isPath(int vorigin, int vdestiny)
{
    boolean result = false;//devuelve si el camino existe
    boolean[] visited = new boolean[nodes.size()];//Booleano para marcar nodos como visitados
    Queue<Integer> cola = new ArrayDeque<>();//Cola en la que se van guardando los nodos 
    cola.add(vorigin);
    visited[vorigin] = true;
    while(!cola.isEmpty()){
        int vertice = cola.poll();//Se saca el primer nodo de la cola, y se guarda en vertice
        visited[vertice]=true;//vertice se marca como visitado
        if(vertice == vdestiny){
            result = true;
            break;
        }
        ArrayList<NodeAdj> vecinos = nodes.get(vertice).adjList;
        for (NodeAdj vecino : vecinos) {
            if(!visited[vecino.data]){//Se verifica que el nodo con este dato no este visitado
                cola.add(vecino.data);
            }
        }
    }
    return result;
}

以下是节点及其邻接的索引:

public static void main(String[] args) {
    Graph_AdjList myGraph = new Graph_AdjList();
    myGraph.addNode(0);
    myGraph.addNode(1);
    myGraph.addNode(3);
    myGraph.addNode(2);
    myGraph.addAdjacency(0, 1, 2);
    myGraph.addAdjacency(1, 3, 4);
    myGraph.addAdjacency(3, 2, 5);
    if(myGraph.isPath(0,2)==true){
        System.out.println("There is a path");
    }else{
        System.out.println("There is no path");
    }
}

为了以防万一,这里有一个函数可以为节点添加连接:

public void addAdjacency(int data_node1, int data_node2, int cost)
{
    //
    Node node1;
    node1 = searchNode(data_node1);
    if(node1 != null)
    {
        node1.addAdjacency(data_node2, cost);
    }
}

我可能是一个很简单的东西,我一直忽视,但任何给予的帮助将不胜感激。提前谢谢!

暂无答案!

目前还没有任何答案,快来回答吧!

相关问题