깊이 우선 검색 알고리즘 작동

Question

깊이 우선 검색이 제대로 작동하지 않습니다. 솔직히 이것이 현재 구현 방법인지 확실하지 않습니다. 나는 그래프를 구현하는 것에 익숙하지 않고 그것을 프로로하고 싶다. 어디서 잘못 가고 있는데 어떻게 dfs() 함수에서 요소를 인쇄하면 dfs가 어떻게되어야하는지 알 수 없습니다.

자식 요소에 대한 getter & 설정 메소드가 권장됩니까? 현재 스택 필요가 없습니다

package graphs; 

    public enum State { 

     Unvisited,Visiting,Visited; 

    } 

    package graphs; 

    public class Node { 

     public Node[] adjacent; 
     public int adjacentCount; 
     private String vertex; 
     public graphs.State state; 

     public Node(String vertex) 
     { 
      this.vertex = vertex; 
     } 
     public Node(String vertex, int adjacentlen) 
     { 
      this.vertex = vertex; 
      adjacentCount = 0; 
      adjacent = new Node[adjacentlen]; 
     } 

     public void addAdjacent(Node adj) 
     { 
      if(adjacentCount < 30) 
      { 
       this.adjacent[adjacentCount] = adj; 
       adjacentCount++; 
      } 
     } 

     public Node[] getAdjacent() 
     { 
      return adjacent; 

     } 

     public String getVertex() 
     { 
      return vertex; 
     } 

    } 

    public class Graph { 

     public int count; // num of vertices 
     private Node vertices[]; 

     public Graph() 
     { 
      vertices = new Node[8]; 
      count = 0; 
     } 

     public void addNode(Node n) 
     { 
      if(count < 10) 
      { 
       vertices[count] = n; 
       count++; 
      } 
      else 
      { 
       System.out.println("graph full"); 
      } 
     } 

     public Node[] getNode() 
     { 
      return vertices; 
     } 
    } 


    package graphs; 

    import java.util.Stack; 
    import graphs.State; 
    public class Dfs { 

     /** 
     * @param args 
     */ 

     static boolean visited[]; 

     public void dfs(Node root) 
     {  
      if(root == null) return; 

      Stack<Node> s = new Stack<Node>(); 
      s.push(root); 
      root.state = State.Visited; 

      System.out.println("root:"+root.getVertex() + "\t"); 
      while(!s.isEmpty()) 
      { 
       Node u = s.pop(); 
       for(Node n: u.getAdjacent()) 
       { 

        if(n.state != State.Visited) 
        { 
         dfs(n); 
        } 
       } 
      } 
     } 

     public static Graph createNewGraph() 
     { 
      Graph g = new Graph();   
      Node[] temp = new Node[8]; 

      temp[0] = new Node("A", 3); 
    temp[1] = new Node("B", 3); 
    temp[2] = new Node("C", 1); 
    temp[3] = new Node("D", 1); 
    temp[4] = new Node("E", 1); 
    temp[5] = new Node("F", 1); 

    temp[0].addAdjacent(temp[1]); 
    temp[0].addAdjacent(temp[2]); 
    temp[0].addAdjacent(temp[3]); 

    temp[1].addAdjacent(temp[0]); 
    temp[1].addAdjacent(temp[4]); 
    temp[1].addAdjacent(temp[5]); 

    temp[2].addAdjacent(temp[0]); 
    temp[3].addAdjacent(temp[0]); 
    temp[4].addAdjacent(temp[1]); 
    temp[5].addAdjacent(temp[1]); 

      for (int i = 0; i < 7; i++) 
      { 
       g.addNode(temp[i]); 
      } 
      return g; 
     } 

     public static void main(String[] args) { 


      Graph g = createNewGraph(); 
      Dfs s = new Dfs(); 
      //Node[] n = g.getNode(); 

      s.dfs(g.getNode()[0]); 

     } 

    } 

Answer 1

:

여기 내 코드입니다. 만 재귀 :

public void dfs(Node node) { 
    if (node == null) { 
     return; 
    } 

    System.out.println("Node: " + node.getVertex()); 
    node.state = State.Visited; 

    for (Node n : node.getAdjacent()) { 
     if (n.state != State.Visited) { 
      dfs(n); 
     } 
    } 
} 

UPDATE

경로의 존재를 확인하려면 :

public boolean isPath(Graph graph, Node start, Node target) { 
    for (Node node : graph.getNode()) { 
     if (node != null) { 
      node.state = State.Unvisited; 
     } 
    } 

    dfs(start); 

    return target.state == State.Visited; 
}