깊이 그래프 우선 검색

Question

자바에서 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으로 전화하십시오.