Что плохого в моем BFS кратчайшему пути реализации в Java

Question

import java.io.*; 
import java.util.*; 

class Graph 
{ 
    private int V; // No. of vertices 
    private LinkedList<Integer> adj[]; //Adjacency Lists 
    private LinkedList<Integer> path[]; 


    Graph(int v) 
    { 
     V = v; 
     adj = new LinkedList[v]; 
     for (int i=0; i<v; ++i) 
      adj[i] = new LinkedList(); 
     path = new LinkedList[v]; 
     for(int i=0;i<v;++i) 
      adj[i]=new LinkedList(); 
    } 


    void addEdge(int v,int w) 
    { 
     adj[v].add(w); 
    } 

    // prints BFS traversal from a given source s 
    void BFS(int s,int d) 
    { 
     boolean visited[] = new boolean[V]; 
     LinkedList<Integer> queue = new LinkedList<Integer>(); 


     visited[s]=true; 
     queue.add(s); 
     path[s].addLast(s); 
     while (queue.size() != 0) 
     { 

      s = queue.poll(); 
      //System.out.print(s+" "); 


      Iterator<Integer> i = adj[s].listIterator(); 
      while (i.hasNext()) 
      { 
       int n = i.next(); 
       if (!visited[n]) 
       { 
        visited[n] = true; 
        queue.add(n); 
        path[n]=path[s]; 
        path[n].addLast(n); 
       } 
      } 
     } 

     System.out.print("Following is the path from source to destination\n"); 
     while(path[d].size()!=0) 
     { 
      int xyz=path[d].getFirst(); 
      path[d].poll(); 
      System.out.print(xyz+" "); 
     } 
    } 

    // Driver method to 
    public static void main(String args[]) 
    { 
     Graph g = new Graph(4); 

     g.addEdge(0, 1); 
     g.addEdge(0, 2); 
     g.addEdge(1, 2); 
     g.addEdge(2, 0); 
     g.addEdge(2, 3); 
     g.addEdge(3, 3); 

     System.out.println("Following is the desired path\n"); 

     g.BFS(2,3); 
    } 
} 

мне нужно, чтобы получить кратчайший путь между узлами 2 и 3.

Answer 1

Вы пытаетесь добавить элемент в связанный список, который является нулевым. Вам нужно инициализировать связанный список по индексу s, прежде чем вы сможете добавить к нему.

path[s] = new LinkedList(); 
path[s].addLast(s); 

Кроме того, ваш код не удается, потому что вы не клонировать путь массива при задании значения пути [п]:

path[n]=path[s]; 

Вы должны изменить это:

path[n]= (LinkedList) path[s].clone(); 

Таким образом, список для n не сохранит ссылку на список s. В настоящее время ссылка сохраняется, так что всякий раз, когда вы добавляете что-то в список для n, эта вещь также будет добавлена ​​к s.

Answer 2

Поскольку нет информации о том, что именно не ведет себя так, как ожидалось, немного сложно сказать, что такое ошибка. Но я вижу две проблемы с кодом:

Во-первых, вы не инициализируете элементы path. Вместо этого в конструкторе вы дважды инициализируете элементы adj. Таким образом, вы должны заменить одну из линий, которые говорят

for(int i=0; i<v; ++i) 
    adj[i] = new LinkedList(); 

с

for(int i=0; i<v; ++i) 
    path[i] = new LinkedList(); 

или вы можете просто удалить две строки, как вы сейчас видите:

Вторая проблема заключается в том, что вам установите различные элементы path в качестве ссылки на другой LinkedList и отредактируйте его:

path[n] = path[s]; 
path[n].addLast(n); 

В результате каждый элемент path использует тот же LinkedList с теми же элементами. Вместо этого вы должны создать новый LinkedList, содержащий те же элементы:

path[n] = new LinkedList(path[s]); 
path[n].addLast(n); 

EDIT: Как сказал Soggiorno в своем ответе, вы должны по крайней мере инициализировать path[s] в начале BFS -метода перед добавлением элемента к нему:

path[s] = new LinkedList(); 
path[s].addLast(s); 

Если вы выполняете инициализацию для всех элементов path, это не обязательно, конечно.