Was in meiner BFS kürzesten Weg Implementierung in 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); 
    } 
} 

falsch Ich brauche den kürzesten Weg zwischen den Knoten 2 und 3

Answer 1

Sie versuchen zu bekommen, ein Element zu einer verknüpften Liste hinzuzufügen, der null ist. Sie müssen die verknüpfte Liste in Index s initialisieren, bevor Sie sie hinzufügen können.

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

Zusätzlich Code versagt, weil Sie den Pfad Array nicht klonen, wenn der Wert der Pfadeinstellung [n]:

path[n]=path[s]; 

Sie müssen dies ändern:

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

Auf diese Weise behält die Liste für n keinen Verweis auf die Liste von s. Derzeit wird die Referenz beibehalten, so dass jedes Mal, wenn Sie etwas zur Liste für n hinzufügen, diese Sache auch zu s hinzugefügt wird.

Answer 2

Da es keine Information gibt, was genau sich nicht wie erwartet verhält, ist es ein bisschen schwierig zu sagen, was der Fehler ist. Aber ich sehe zwei Probleme mit dem Code:

Zuerst initialisieren Sie nicht die Elemente der path. Stattdessen initialisieren Sie im Konstruktor die Elemente von adj zweimal. Also, sollten Sie eine der Leitungen ersetzen, die sagen

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

mit

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

oder Sie können nur die beiden Zeilen löschen, wie Sie jetzt sehen:

Das zweite Problem, dass Sie ist eingestellt, die verschiedenen Elemente der path als Verweis auf eine andere VerketteteListe und bearbeiten es:

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

Dies hat zur Folge, dass jedes Element von path dieselbe LinkedList mit denselben Elementen verwendet. Stattdessen sollten Sie einen neuen LinkedList enthält die gleichen Elemente erstellen:

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

EDIT: Wie Soggiorno in seiner Antwort sagte, müssen Sie mindestens path[s] am Anfang des BFS -Methode initialisiert wird, bevor ein Element, um es fügt hinzu:

Wenn Sie die Initialisierung für alle Elemente von path tun, ist dies natürlich nicht erforderlich.