DFS

DFS (Depth-First Search)

: 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
: 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘
: 스택 자료 구조를 이용

그래프의 기본 구조

- 노드 (Node)
- 간선 (Edge)
- 정점 (Vertex)

그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다.
또한 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다.

 

그래프의 표현 방식 2가지

- 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

인접 행렬(Adjacenct Matrix)

: 각 노드가 연결된 형태를 기록하는 방식
- 연결되어있지 않은 노드끼리는 무한의 비용이라고 작성
  - 실제 코드에서는 논리적으로 정답이 될 수 없는 큰 값 중에서 999999999, 987654321 등의 값으로 초기화하는 경우가 많다.
  

예제 코드 - java)

public class DFSBase {
    static final int INF = 999999999;
    public static void main(String[] args) {
        int[][] graph = {
                {0, 7, 5},
                {7, 0, INF},
                {5, INF, 0}
        };
        
    }
}

인접 리스트(Adjacency List)

: 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
- '연결 리스트'라는 자료구조를 이용해 구현

 

예제 코드 - java)

import java.util.ArrayList;

public class DFSBase2 {
    public static void main(String[] args) {
        int n = 3; // 노드의 개수
        int m = 3; // 간선의 개수

        // 인접 리스트
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        // 인접 리스트로 구성한 그래프에 ArrayList를 넣어주면서 초기화
        for(int i=0 ; i<=n ; i++){
            graph.add(new ArrayList<>());
        }

        // 노드 0에 연결된 노드 정보 저장
        graph.get(0).add(7);
        graph.get(0).add(5);

        // 노드 1에 연결된 노드 정보 저장
        graph.get(1).add(7);

        // 노드 2에 연결된 노드 정보 저장
        graph.get(2).add(5);

    }
}

/** 참고한 코드 출처
https://wonit.tistory.com/238
 **/

 

두 방식의 차이

- 메모리
  - 인접 행력 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.
  - 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용
  
- 속도
  - 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.
  연결된 데이터를 하나씩 확인해야 하기 때문이다.
 

DFS의 구체적인 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

TIP : '방문 처리'는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다.
방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.

 

 

예시) 더보기 클릭

다음과 같은 그래프를 생각해보자.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

탐색을 수행함에 있어 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다.

 

 

DFS 인접 리스트 예제 코드 - java)

package exam05_dfs_bfs;

import java.util.ArrayList;
import java.util.Iterator;

public class DFS_Exam {
    public static void dfs(ArrayList<Integer>[] graph, int v, boolean[] visited) {
        // 현재 노드를 방문 처리
        visited[v] = true;
        System.out.print(v + " ");

        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for(int e : graph[v]){

            if (!visited[e])
                dfs(graph, e, visited);
        }

    }

    public static void main(String[] args) {
        // 인접 리스트
        ArrayList<Integer>[] graph = new ArrayList[9];
        // 인접 리스트로 구성한 그래프에 ArrayList를 넣어주면서 초기화
        for(int i=0; i<graph.length; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        boolean[] visited = new boolean[9];
        
        // 그래프 
        graph[1].add(2);
        graph[1].add(3);
        graph[1].add(8);

        graph[2].add(1);
        graph[2].add(7);

        graph[3].add(1);
        graph[3].add(4);
        graph[3].add(5);

        graph[4].add(3);
        graph[4].add(5);

        graph[5].add(3);
        graph[5].add(4);

        graph[6].add(7);

        graph[7].add(2);
        graph[7].add(6);
        graph[7].add(8);

        graph[8].add(1);
        graph[8].add(7);

        dfs(graph, 1, visited);


    }
}

 

DFS 인접 행렬 예제 코드 - java)

package exam05_dfs_bfs;


public class DFS_Exam_matrix {
    public static void dfs(int[][] graph, int v, boolean[] visited){
        // 현재 노드를 방문 처리
        visited[v] = true;
        System.out.print(v + " ");

        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        // 리스트와 다르게 배열은 크기가 선언되어있으므로 0번 인덱스부터 끝까지 탐색
        for(int i= 1; i<graph.length ; i++){
            // 현재 v와 i 번호가 연결되어있고, i 노드를 아직 방문하지 않았다면 재귀적으로 방문
            if(graph[v][i] == 1 && !visited[i]){
                dfs(graph, i, visited);
            }
        }
    }

    public static void main(String[] args) {
        // 인접 행렬
        int[][] graph = new int[9][9];
        boolean[] visited = new boolean[9];

        // 그래프
        graph[1][2] = 1;
        graph[1][3] = 1;
        graph[1][8] = 1;

        graph[2][1] = 1;
        graph[2][7] = 1;

        graph[3][1] = 1;
        graph[3][4] = 1;
        graph[3][5] = 1;

        graph[4][3] = 1;
        graph[4][5] = 1;

        graph[5][3] = 1;
        graph[5][4] = 1;

        graph[6][7] = 1;

        graph[7][2] = 1;
        graph[7][6] = 1;
        graph[7][8] = 1;

        graph[8][1] = 1;
        graph[8][7] = 1;

        dfs(graph, 1, visited);


    }
}