[C] 깊이 우선 탐색(DFS; Depth First Search) 개념 및 정리

개념

트리의 순회와 같이 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을

그래프의 탐색(search) 알고리즘이라고 한다

 

깊이 우선 탐색(DFS; depth-first search)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다

 

출처 : https://freestrokes.tistory.com/88

 

1. 현재 정점과 인접한 간선들을 하나씩 검사하다가,
2. 아직 방문하지 않은 정점으로 향하는 간선이 있다면 따라가고,
3. 더이상 갈 곳이 없다면 포기하고 마지막에 온 간선을 따라 뒤로 돌아간다

3번의 과정에서 우리는 재귀 호출을 이용하여 간단하게 구현할 수 있다

 

---

코드

인접 행렬 사용

#include<stdio.h>

#define MAX 1001
int adj[MAX][MAX]; //인접행렬 만들때 사용 
int visited[MAX]; //방문했는지 check  

void init(int N) {
    for(int i=1; i<=N; i++) {
        visited[i] = 0; //방문한곳 0으로 초기화 !
    }
}

// 모든 컴포넌트 방문
// void DFSAll(int N);

void DFS(int here, int N) { //정점과 정점개수
    int there;
    
    visited[here] = 1; //방문 check
    printf("%d ", here); //정점 출력
    
    for(int i = 1; i <= N; i++) {
        if(adj[here][i]) {
            there = i;
            if(!visited[there]) {
                DFS(there, N); //발견하자마자 바로 함수로 다시 들어가
            }
        }
    }
}

int main() {
    int N,M,v; // 정점개수, 간선개수, 시작정점
    int x,y; // 좌표
    
    scanf("%d %d %d", &N, &M, &v);
    for(int i=1; i<=M; i++) { //M(간선개수) 만큼
        scanf("%d %d", &x,&y);
        adj[x][y]=1;
        adj[y][x]=1; //인접행렬 만들기
    }
        
    //DFS 호출
    DFS(v, N);
    
    return 0;
}

 

그래프가 하나의 컴포넌트로 이루어져 있다는 보장이 없기 떄문에,

우리는 dfsAll()로 그래프 전체의 구조를 파악할 수 있다

 

---

시간 복잡도

인접 리스트를 이용했을 때,

모든 정점을 한 번씩, 간선을 1번 (무향 그래프일 경우 2번) 확인하므로

O(|V| + |E|) 가 된다

(|V|는 정점 수, |E|는 간선 수)

 

인접 행렬을 사용한다면 dfs() 내부에서 다른 모든 정점들을 순회하며 간선을 확인하므로

O(|V|^2) 가 된다

 

---

장점 및 단점

장점

 

• 구현이 너비 우선 탐색(BFS) 보다 간단하다
• 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적음

단점

 

• 모든 정점, 간선을 탐색하므로 검색 속도는 너비 우선 탐색(BFS) 보다 느림
• 해가 없는 경우에 빠질 가능성이 있음
  (이러한 경우 사전에 임의의 깊이를 지정한 후 탐색하도록 하고, 목표 노드를 발견하지 못할 경우 다음 경로를 탐색하도록 함 : 점점 깊어지는 탐색(IDS; Iteratively Deepening Search))
• 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로, 구한 해가 최단 경로가 된다는 보장이 없음
  (목표에 이르는 경로가 다수인 경우 구한 해가 최적이 아닐 수 있음)

참조 : freestrokes.tistory.com/88 / 알고리즘 문제 해결 전략

 

---

더 나아가기 키워드

• 위상 정렬(DAG; directed acycle graph) : visited[] 역순 출력
• 오일러 서킷 : 모든 간선을 한 번씩 지나 시작점으로
  - 무향 그래프 : 모든 정점이 짝수점이고 하나의 컴포넌트로 이루어져 있다
  - 방향 그래프 : 나가는 간선의 수 == 들어오는 간선의 수
• 오일러 트레일 : 시작점과 끝점을 임의로 이어 오일러 서킷 찾기
• DFS 스패닝 트리(Spanning Tree) : discovered[] 발견 순서로 간선 파악 / finished[] dfs(i) 종료 여부
  - 트리 간선 (tree edge) : 스패닝 트리의 모든 간선
  - 순방향 간선(forward edge) : 트리 간선이 아닌, 선조-자손 간선
  - 역방향 간선(back edge) : 자손-선조 간선 (무향엔 순방향 == 역방향)
  - 교차 간선(cross edge) : 나머지 간선 (무향엔 없다)
• 절단점(cut vertex) 찾기 : 삭제하면 컴포넌트가 쪼개지는 정점
  :임의의 정점 u의 자손들이 모두 역방향 간선으로 u의 선조로 올라간다면,
    u는 절단점이 아니다 (discovered[] 이용)
• 다리 찾기 : 삭제하면 컴포넌트가 쪼개지는 간선
  : 다리는 항상 트리 간선이다
  : 다리 (u, v) : 역방향 간선 중 부모 간선 제외,
    v와 그 자손들에게서 닿을 수 있는 정점의 최소 발견 순서가 u 후라면 다리
• 강결합 컴포넌트(SCC; strongly connected components)
  : 방향 그래프에서 두 정점 u와 v에 대해 양 방향으로 가는 경로가 모두 있을 때,
    “SCC에 속해 있다”
  : 교차 간선을 따라가 만난 정점의 SCC 묶임 여부를 확인한다
    (절단점 판단 알고리즘과 비슷함)
  : scc() 함수 - DFS에서 방문한 정점들의 번호를 담는 스택