Tiefe erste Suche auf Graph Java

Question

Ich habe ein kleines Problem mit der Implementierung von DFS Traversal in Java. Mein Problem ist meiner Meinung nach die 'dfs'-Methode in Graph.java, die ich codiert habe. Es liefert nicht die erforderliche Ausgabe und gibt ihm eine bestimmte Eingabe. Mein Code ist unten mit seinem Eingang und der gewünschten Ausgabe. Könnte jemand mir helfen, dieses Problem in meinem Code zu lösen. Vielen Dank.

Graph.java

public class Graph { 
ArrayList<Vertex> Vertices=new ArrayList<Vertex>(); 
Stack<Integer> stack=new Stack<Integer>(); 
public Graph(){ 
    Scanner in=new Scanner(System.in); 
    String sz=in.nextLine(); 
    int size=Integer.parseInt(sz); 
    for(int i=0; i<size; i++) addVertex(); 
    String s=in.nextLine(); 
    while(!s.equals("-1")){ 
     String[] arr=s.split(","); 
     int v1=Integer.parseInt(arr[0]); 
     int v2=Integer.parseInt(arr[1]); 
     addEdge(v1,v2); 
     s=in.nextLine(); 
    } 

    //Vertex v=Vertices.get(2); 
    //System.out.println(dfs(v)); 
} 

public static void main(String[] args){ 
    new Graph(); 
} 
public void addVertex(){ 
    Vertex v=new Vertex(Vertices.size()); 
    Vertices.add(v); 
} 
public Vertex getVertex(int n){ 
    return Vertices.get(n); 
} 
public void addEdge(int n, int m){ 
    Vertex v1=Vertices.get(n); 
    Vertex v2=Vertices.get(m); 
    v1.addAdjacency(v2); 
    v2.addAdjacency(v1); 
} 
public void dfs(Vertex obj){ 
    obj.marked=true; 
    int k=0; 
    for(Vertex v:obj.Vertices){ 
     Vertex d=v; 
     if(!d.marked){ 
      d.parent=obj; 
      k=d.parent.vertexNumber; 
      stack.push(k); 
      dfs(d); 
     } 
    } 
} 
} 

Vertex.java

public class Vertex { 
int vertexNumber; 
Vertex parent = null; 
boolean marked = false; 
LinkedList<Vertex> Vertices = new LinkedList<Vertex>(); 

public Vertex(int num) { 
    vertexNumber = num; 
} 

public void addAdjacency(Vertex object) { 
    Vertices.add(object); 
} 

public boolean isAdjacent(Vertex object) { 
    if (Vertices.contains(object)) 
     return true; 
    else 
     return false; 
} 

public int getDegree() { 
    return Vertices.size(); 
} 

}

Answer 1

Sie es fast hatte. Sie brauchen den Stapel in Ihrem dfs nicht. Vereinfachen Sie es wie folgt aus:

public void dfs(Vertex obj) { 
    obj.marked = true; 
    for (Vertex v : obj.Vertices) { 
     if (!v.marked) { 
      v.parent = obj; 
      dfs(v); 
     } 
    } 
} 

Sie die Ergebnisse in der Haupt drucken:

public static void main(String[] args) { 
    Graph g = new Graph(); 
    Vertex source = g.Vertices.get(0); 
    g.dfs(source); 

    for(Vertex v:g.Vertices){ 
     if (v!= source && v.marked){ 
      System.out.println(v.vertexNumber+":"+v.parent.vertexNumber); 
     } 
    } 
} 

Sie sind einfach dfs Aufruf, Kennzeichnung etwas zu erreichen, wie Sie entlang und die Eltern zu aktualisieren. Sobald Sie fertig sind, gehen Sie einfach durch alle Scheitelpunkte und drucken Sie diejenigen, die erreichbar waren (mit Ausnahme der Quelle selbst).

Und hier ist der Ausgang Ich erhalte:

1:0 
2:1 
3:8 
4:5 
5:6 
6:2 
7:10 
8:7 
9:5 
10:5 

Ich empfehle Ihnen auch Ihren Code und bewegen die Befehlszeile liest auf Ihre Haupt statt Graph Konstruktor Refactoring. Lies einfach die Zahlen und rufe g.addEdge an, um dein Diagramm zu erstellen.