java - 使用 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);
     } 
 }