поиск всех возможных путей между двумя узлами с использованием DFS

Question

Я пытаюсь найти все возможные пути в моем графике. Когда я запускаю программу, я получаю сообщение об ошибке ArrayIndexOutOfBoundsException. Где мне нужно исправить мой код, чтобы устранить эту ошибку

private int v;  
 void printAllPaths(String s, String d) {
     int start=airportsHashMap.get(s).intValue();
        int end=airportsHashMap.get(d).intValue();

        //int DaRoute;
        printPaths(start,end);
 }
 public void printPaths(int s, int d)  
 { 

     boolean[] isVisited = new boolean[v]; 
     ArrayList<Integer> pathList = new ArrayList<>(); 

     //add source to path[] 
     pathList.add(s); 

     //Call recursive utility 
     printAllPathsUtil(s, d, isVisited, pathList); 
 } 

 // A recursive function to print 
 // all paths from 'u' to 'd'. 
 // isVisited[] keeps track of 
 // vertices in current path. 
 // localPathList<> stores actual 
 // vertices in the current path 
 private void printAllPathsUtil(Integer u, Integer d, 
                                 boolean[] isVisited, 
                         List<Integer> localPathList) { 

     // Mark the current node 
     isVisited[u] = true; 

     if (u.equals(d))  
     { 
         System.out.println(localPathList); 
         // if match found then no need to traverse more till depth 
         isVisited[u]= false; 
         return ; 
     } 

     // Recur for all the vertices 
     // adjacent to current vertex 
     for (Integer i :adjListArray[u])  
     { 
         if (!isVisited[i]) 
         { 
             // store current node  
             // in path[] 
             localPathList.add(i); 
             printAllPathsUtil(i, d, isVisited, localPathList); 

             // remove current node 
             // in path[] 
             localPathList.remove(i); 
         } 
     } 

     // Mark the current node 
     isVisited[u] = false; 
 } 

Я ожидал, что результат будет выглядеть так:

Все пути между EWR и PHL

EWR IAD ILG PHL EWR IAD PHL EWR PHL

Все пути между EWR и ILG

EWR IAD ILG EWR IAD PHL ILG EWR PHL ILG EWR PHL IAD ILG

Answer 1

Я думаю, что Исключением является то, что вы неправильно используете удалить . Вы должны передать индекс вместо «объекта».

 for (Integer i :adjListArray[u])  
 { 
     if (!isVisited[i]) 
     { 
         // store current node  
         // in path[] 
         localPathList.add(i);                 <=== i the 'object'
         printAllPathsUtil(i, d, isVisited, localPathList); 

         // remove current node 
         // in path[] 
         localPathList.remove(i);              <=== i should be 'index' not object
     } 
 } 

Ваш холодный шолуд вот так:

 for (Integer i :adjListArray[u])  
 { 
     if (!isVisited[i]) 
     { 
         // store current node  
         // in path[] 
         localPathList.add(i);
         printAllPathsUtil(i, d, isVisited, localPathList); 

         // remove current node 
         // in path[] 
         localPathList.remove(localPathList.size()-1);
     } 
 }