DFS(Depth - Fist Search) : 코드로 구현

앞서 DFS에 대한 개념 및 예시를 알아보았다.

 

코드로 작성해보자!

 

1. UndirectedGraph를 matrix로 구현하기

---

DFS를 코드로 구현하기 앞서, 그래프를 matrix로 등록하는 코드를 작성하자.

 

그래프는 이전에 사용한 그래프와 동일한 그래프를 사용할 예정.

 

public class UndirectedGraph {

    //현재 노드가 몇개?
    int nubmer;
    int from;
    int to;
    //matrix
    private int[][] nodeMatrix;
    //가중치
    private int weight;

    public UndirectedGraph(int nubmer){
        this.nubmer = nubmer;
        nodeMatrix = new int[nubmer][nubmer];
      //UndirectedGraph의 인스턴스가 생성 될 때, nodeMatrix 초기화
    }

    public void addEdge(int from, int to, int weight){
        nodeMatrix[from][to] = weight;
        //undirectedMatrix니 양항향 동일
        nodeMatrix[to][from] = weight;
    }

    public int[][] getMatrix(){
        return nodeMatrix;
    }
}

 

2. DFS 기능 구현하기

---

public class DepthFirstSearch {

    Stack<Integer> stack;
    boolean[] visited;
    Stack<Integer> visitOrder;
    //노드 수
    private int number;

    //matrix
    int[][] matrix;

    int count = 0;

    public DepthFirstSearch(int number){
        this.number = number;
        visited = new boolean[number];
        stack = new Stack<>();
        visitOrder = new Stack<>();

    }

//search 시작할 노드 입력받음.
    public void dfsTraversal(int startNode){

        stack.push(startNode);
        System.out.println("stack : " + stack.toString());

        while(true){

            int currentNode = stack.pop(); //노드 방문
            System.out.println("이번 방문 노드 : " + currentNode);
            System.out.println("stack : " + stack.toString());
            count++;
            visited[currentNode] = true;

            //matrix상에서 현재 노드와 연결된 노드 찾고, 
            //stack에 그 노드가 있는지
            //이미 방문했는지 여부 확인!
            for(int j=0;j < number; j++){
                //from current node to 어디? 찾기
                if((matrix[currentNode][j] >0)
                  && (stack.search(j) == -1) 
                  && visited[j] == false){
                    //인접노드 추가
                    stack.push(j);

                }

            }
            System.out.println(currentNode+" 인접노드 push");
            System.out.println("stack : " + stack.toString());
            System.out.println("-------------------------");
            if(count == number) {
                System.out.println("serach 종료");
            break;
            }
        }

      System.out.println("방문 순서 : " + visitOrder.toString());

    }

}

 

3. main에서 실행하기

---

public class DFSPractice {

    public static void main(String[] args) {

        int number = 8;
        DepthFirstSearch DFS = new DepthFirstSearch(number);
        UndirectedGraph graph = new UndirectedGraph(number);


        graph.addEdge(0, 1, 1);
        graph.addEdge(0, 2, 1);
        graph.addEdge(1 ,3, 1);
        graph.addEdge(1 ,4, 1);
        graph.addEdge(2 ,5, 1);
        graph.addEdge(2 ,6, 1);
        graph.addEdge(4 ,5, 1);
        graph.addEdge(3 ,7, 1);

        //DFS에서 사용할 matrix는 UndirectedGraph에서 생성한 그래프를 입력받는다.
        DFS.matrix = graph.getMatrix();
 
        //어디서 부터 시작할 지 주입받는다.
        DFS.dfsTraversal(0);


    }
}

 

4. 실행 결과

---

1) 0부터 시작한 경우

stack : [0]
이번 방문 노드 : 0
stack : []
0 인접노드 push
stack : [1, 2]
-------------------------
이번 방문 노드 : 2
stack : [1]
2 인접노드 push
stack : [1, 5, 6]
-------------------------
이번 방문 노드 : 6
stack : [1, 5]
6 인접노드 push
stack : [1, 5]
-------------------------
이번 방문 노드 : 5
stack : [1]
5 인접노드 push
stack : [1, 4]
-------------------------
이번 방문 노드 : 4
stack : [1]
4 인접노드 push
stack : [1]
-------------------------
이번 방문 노드 : 1
stack : []
1 인접노드 push
stack : [3]
-------------------------
이번 방문 노드 : 3
stack : []
3 인접노드 push
stack : [7]
-------------------------
이번 방문 노드 : 7
stack : []
7 인접노드 push
stack : []
-------------------------
serach 종료
방문 순서 : [0, 2, 6, 5, 4, 1, 3, 7]

 

2) 4부터 시작한 경우

stack : [4]
이번 방문 노드 : 4
stack : []
4 인접노드 push
stack : [1, 5]
-------------------------
이번 방문 노드 : 5
stack : [1]
5 인접노드 push
stack : [1, 2]
-------------------------
이번 방문 노드 : 2
stack : [1]
2 인접노드 push
stack : [1, 0, 6]
-------------------------
이번 방문 노드 : 6
stack : [1, 0]
6 인접노드 push
stack : [1, 0]
-------------------------
이번 방문 노드 : 0
stack : [1]
0 인접노드 push
stack : [1]
-------------------------
이번 방문 노드 : 1
stack : []
1 인접노드 push
stack : [3]
-------------------------
이번 방문 노드 : 3
stack : []
3 인접노드 push
stack : [7]
-------------------------
이번 방문 노드 : 7
stack : []
7 인접노드 push
stack : []
-------------------------
serach 종료
방문 순서 : [4, 5, 2, 6, 0, 1, 3, 7]