Depth First Recherche sur le graphe java

Question

J'ai un peu de mal à implémenter la traversée DFS en java. Mon problème, je pense, est la méthode 'dfs' dans Graph.java que j'ai codé. Il ne renvoie pas la sortie requise en lui donnant une entrée spécifique. Mon code est ci-dessous avec son entrée et la sortie désirée. Quelqu'un pourrait m'aider à résoudre ce problème dans mon code. Merci.

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

Tu as presque eu. Vous n'avez pas besoin de la pile dans vos dfs. Simplifier comme ceci:

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

imprimer uniquement les résultats dans votre principale:

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); 
     } 
    } 
} 

Vous appelez simplement DSF, tout marquage accessible comme vous le long et la mise à jour du parent. Une fois que vous avez terminé, passez tous les sommets et imprimez ceux qui étaient accessibles (sauf la source elle-même).

Et voici la sortie que je reçois:

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

Je recommande aussi que vous factoriser votre code et déplacer la ligne de commande lit à votre principal au lieu du constructeur Graph. Il suffit de lire les numéros et appelez g.addEdge afin de construire votre graphique.