java

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

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

  1. public boolean isPath(int vorigin, int vdestiny)
  2. {
  3. boolean result = false;//devuelve si el camino existe
  4. boolean[] visited = new boolean[nodes.size()];//Booleano para marcar nodos como visitados
  5. Queue<Integer> cola = new ArrayDeque<>();//Cola en la que se van guardando los nodos
  6. cola.add(vorigin);
  7. visited[vorigin] = true;
  8. while(!cola.isEmpty()){
  9. int vertice = cola.poll();//Se saca el primer nodo de la cola, y se guarda en vertice
  10. visited[vertice]=true;//vertice se marca como visitado
  11. if(vertice == vdestiny){
  12. result = true;
  13. break;
  14. }
  15. ArrayList<NodeAdj> vecinos = nodes.get(vertice).adjList;
  16. for (NodeAdj vecino : vecinos) {
  17. if(!visited[vecino.data]){//Se verifica que el nodo con este dato no este visitado
  18. cola.add(vecino.data);
  19. }
  20. }
  21. }
  22. return result;
  23. }

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

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

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

  1. public void addAdjacency(int data_node1, int data_node2, int cost)
  2. {
  3. //
  4. Node node1;
  5. node1 = searchNode(data_node1);
  6. if(node1 != null)
  7. {
  8. node1.addAdjacency(data_node2, cost);
  9. }
  10. }

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

暂无答案!

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

相关问题