深さまずグラフのJavaで検索

Question

私は、JavaでDFS越えを実装する際に問題が少しあります。私の問題は、Graph.javaの 'dfs'メソッドがコード化されていると思います。それは特定の入力を与える必要な出力を返していません。私のコードは、その入力と希望する出力とともに下にあります。誰かが私のコードでこの問題を解決するのを助けることができますか？ありがとう。あなたはほとんどそれを持っていた

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

あなたは、単にあなたに沿って、親の更新など、到達可能なものをマーキング、DFSを呼んでいます。完了したら、すべての頂点を通過して到達可能なもの（ソース自体を除く）を印刷してください。ここ

そして、私は取得しています出力されます：

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

を私はまた、あなたのコードをリファクタリングして、コマンドラインではなくGraphコンストラクタのメインに読み込み、移動することをお勧めいたします。グラフを作成するには、数値を読み、g.addEdgeに電話してください。