Java로 구현하는 DFS 알고리즘

안녕하세요, 이번 포스팅에서는 DFS 알고리즘에 대해서 알아보겠습니다.

 

그래프 탐색 알고리즘 중 가장 유명한 알고리즘은 아무래도 DFS와 BFS가 아닐까 생각됩니다.

DFS는 스택을 활용해서 저장된 그래프의 모든 정점을 1번 방문하는 방법 중 하나인데,

갈 수 있는 만큼 최대한 많이 가고 갈 수 없을 경우 이전 정점으로 돌아가서 다시 탐색을 하는 알고리즘입니다.

 

 

그래프의 탐색

그래프는 자료구조에서 배우는 정점과 간선으로 이루어진 그래프를 의미합니다. 그래프 탐색은 하나의 정점으로부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미합니다.

예를 들면 특정 도시에서 다른 도시로 갈 수 있는지, 전자 회로에서 특정 단자와 단자가 서로 연결 되어 있는지에

대한 것입니다.

 

깊이 우선 탐색(DFS)

DFS는 말그대로 깊게 탐색하는 것을 의미하는데요. BFS가 넓게, 큐를 이용해서 탐색하는 것과 달리

DFS는 스택을 이용해서 뎁스를 한번에 깊게 들어가는 경향이 있습니다.

 

DFS를 구현하는 방법에는 인접행렬, 인접리스트, 간선리스트 3가지가 있습니다.

여기선 인접행렬과 인접리스트를 활용해보겠습니다.

 

먼저 다음의 그래프로 DFS를 구현해볼게요

1번 정점부터 순차적으로 탐색했을 때 어떻게 동작하는지 알아봅시다.

 

1번 정점 : 2번, 3번 정점을 모두 방문하지 않은 상태2번 정점 방문

 

2번 정점 : 1번, 4번, 5번과 연결된 상태이고 1번은 방문한 상태4번 정점 방문

 

4번 정점 : 2번, 8번 정점과 연결된 상태이고 2번 정점은 방문한 상태8번 정점 방문

 

8번 정점 : 4번, 5번, 6번, 7번 정점과 연결된 상태이고 4번은 방문한 상태5번 정점 방문

 

5번 정점 : 2번, 8번 정점과 연결된 상태이고 모두 방문한 상태8번으로 다시 돌아갑니다

 

8번 정점 : 4번, 5번, 6번, 7번 정점과 연결된 상태이고 4, 5번은 방문한 상태6번 정점 방문

 

6번 정점 : 3번, 8번 정점과 연결된 상태이고 8번 정점은 방문한 상태3번 정점 방문

 

3번 정점 : 1번, 6번, 7번 정점과 연결된 상태이고 1번, 6번은 방문한 상태7번 정점 방문

 

7번 정점 : 3번, 8번 정점과 연결된 상태이고 모두 방문한 상태8번 정점으로 다시 돌아감

 

8번 정점 : 4번, 5번, 6번, 7번과 연결된 상태이고 모두 방문한 상태이므로탐색을 종료함

 

인접행렬로 구현한 DFS

import java.util.Scanner;

//그래프(인접행렬)클래스
class DfsGraph {
    private int nV; // 정점의 개수
    private int[][] dfsGraph; // 그래프
    private boolean[] visitArr; // 정점 방문 여부 확인 배열

    //그래프 초기화
    public DfsGraph(int nV) {
        this.nV = nV;

            /*
            put(int x, int y)에서 입력되는 정점의 값은 0 이상의 정수이나
            배열의 index는 0부터 시작이므로
            정점을 담는 인접행렬의 행과 열 size는 1을 더하여 초기화해줌
             */
        this.dfsGraph = new int[this.nV+1][this.nV+1];

        this.visitArr = new boolean[this.nV+1];
    }

    //그래프 return
    public int[][] getGraph(){
        return this.dfsGraph;
    }

    //그래프 추가(양방향)
    public void put(int x, int y){
        this.dfsGraph[x][y] = this.dfsGraph[y][x] = 1;
    }

    //그래프 추가(단방향)
    public void putSingle(int x, int y){
        this.dfsGraph[x][y] = 1;
    }

    //그래프 출력(인접행렬)
    public void printGraphToAdjArr() {
        for(int i=1; i<this.dfsGraph.length; i++){
            for (int j=1; j<this.dfsGraph[i].length; j++){
                System.out.print(" " + this.dfsGraph[i][j]);
            }
            System.out.println();
        }
    }

    //정점 방문 여부 확인 배열 초기화
    public void clearVisitArr() {
        for (int i=1; i<this.visitArr.length; i++) {
            this.visitArr[i] = false;
        }
    }

    //그래프 탐색(재귀호출)
    public void dfs(int vIdx){
        this.visitArr[vIdx] = true;
        System.out.println(vIdx + "");

        for (int i = 1; i<=this.nV; i++){
            if (dfsGraph[vIdx][i] == 1 && visitArr[i] == false) {
                dfs(i);
            }
        }
    }
}

public class dfsAlgorithm {
    public static void main(String[] args){
        int nV = 0;
        int nE = 0;

        Scanner scanner = new Scanner(System.in);
        nV = scanner.nextInt();
        nE = scanner.nextInt();

        DfsGraph dfsGraph = new DfsGraph(nV);

        /*
        양방향으로 그래프 추
         */
        dfsGraph.put(1, 2);
        dfsGraph.put(1, 3);
        dfsGraph.put(2, 4);
        dfsGraph.put(2, 5);
        dfsGraph.put(3, 6);
        dfsGraph.put(3, 7);
        dfsGraph.put(4, 8);
        dfsGraph.put(5, 8);
        dfsGraph.put(6, 8);
        dfsGraph.put(7, 8);

        scanner.close();

        dfsGraph.printGraphToAdjArr();

        System.out.println();
        System.out.print("정점 1부터 탐색:");
        dfsGraph.dfs(1);

        System.out.println();
        System.out.print("정점 3부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(3);
    }
}

 

실행결과

 

인접 리스트로 구현한 DFS

 

 

 

 

 

 

참조

https://freestrokes.tistory.com/88