Поиск по графу java

Question

У меня возникла проблема с реализацией обхода DFS в java. Моя проблема, я думаю, это метод «dfs» в кодировке Graph.java I. Он не возвращает требуемый вывод, давая ему определенный вход. Мой код ниже вместе со своим входом и желаемым выходом. Может ли кто-нибудь помочь мне решить эту проблему в моем коде. Благодарю.

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

Вы почти имели его. Вам не нужен стек в ваших dfs. Упростить это так:

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

Просто распечатайте результаты в главном:

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

Вы просто позвонив в глубину, маркировка ничего достижимого как вам вместе и обновление родителя. Как только вы закончите, просто пройдете все вершины и напечатайте те, которые были доступны (кроме самого источника).

А вот выход я получаю:

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

Я также рекомендую вам реорганизовать свой код и переместить из командной строки читает ваш главный вместо Graph конструктора. Просто прочитайте номера и позвоните g.addEdge, чтобы построить свой график.