[자료구조] 그래프(Graph) - 깊이우선탐색(DFS) & 너비우선탐색(BFS)

그래프의 탐색이란?

• 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것
• 특정한 정점에서 다른 정점으로 갈 수 있는지 없는지를 탐색을 통하여 알 수 있다.
  - e.g. 특정 도시에서 다른 도시로 갈 수 있는지 없는지

깊이 우선 탐색(DFS: depth first search)

• 깊이부터 우선적으로 탐색하는 기법
• 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 정점이 없게 되면 왔던 정점 중 가장 가까운 정점으로 돌아가서 다른 정점으로 다시 탐색을 진행하는 방식

깊이 우선 탐색(DFS) 동작 과정

1. 정점 0부터 시작한다고 가정했을 때 정점 0과 간선으로 연결되어 있는 정점 1,2,3 중 가장 가까운 1번 정점으로 탐색
2. 정점 1은 정점 0과 정점 2에 연결되어 있지만 정점 0은 이미 방문을 했기 때문에 정점 2로 탐색

1. 정점 2에서는 정점 0,1,3과 간선으로 연결되어 있지만 정점 0과 정점 1은 이미 방문을 했기 때문에 정점 3으로 탐색
2. 정점 3에서는 정점 4 밖에 방문하지 않은 곳이 없으니 정점 4로 탐색

1. 정점 4가 시작 정점이 되었을 때는 모든 정점을 이미 방문 했기 때문에 가장 최근에 거쳐왔던 정점 3으로 다시 되돌아감
2. 정점 3에서도 마찬가지로 방문할 정점이 없기에 최근에 거쳐온 정점 2로 되돌아감

1. 정점 2와 정점 1에서도 마찬가지로 순환호출로 인하여 되돌아감

1. 마지막 정점 0에서 더 이상 방문할 정점이 없기에 탐색을 종료함

깊이 우선 탐색(DFS) 구현방식

1. 순환 호출을 이용하여 구현
2. 스택을 이용하여 구현

아래는 순환 호출을 이용한 DFS 함수 코드이다.

#define SIZE 100
#define TRUE 1
#define FALSE 0
typedef struct GraphType {
    int n; // 정점의 개수
    int adj_mat[SIZE][SIZE];
} GraphType;

int visited[SIZE];

void init(GraphType* g){ // 그래프 초기화
    int r,c;
    g->n = 0;
    for(r = 0; r < SIZE; r++)
        for(c = 0; c < SIZE; c++)
            g->adj_mat[r][c] = 0
}

void insert_vertex(GraphType* g, int v){ // 정점 삽입 연산
    if(((g->n) + 1) > SIZE){
        return;
    }
    g->n++;
}

void insert_edge(GraphType* g, int start, int end){ // 간선 삽입 연산
    if (start >= g->n || end >= g->n){
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}


void dfs_mat(GraphType* g, int v){ // DFS
    visited[v] = TRUE;
    
    printf("정점 %d -> ",v);
    for (int w = 0; w < (g->n); w++)
        if (g->adj_mat[v][w] && !visited[w])
            dfs_mat(g, w);
}

너비 우선 탐색(BFS: breath first search)

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 큐(Queue) 자료구조를 사용하여 구현

너비 우선 탐색(BFS) 동작 과정

1. A 정점부터 너비 우선 탐색을 시작하면 먼저 큐에 정점 A를 삽입
2. 그 다음 큐 맨 앞에 있는 정점을 꺼낸 뒤 그 정점과 연결되어 있는 정점들을 차례대로 큐에 삽입

1. 다시 큐 맨 앞에 있는 C 정점을 꺼내서 C 정점과 연결되어 있는 B,D,F 정점을 큐에 삽입
2. 마찬가지로 반복하여 큐 맨 앞에 있는 E 정점을 꺼내서 확인하는데 연결되어 있는 F 정점은 이미 큐에 있기 때문에 삽입하지 않고 E 정점만 큐에서 삭제
3. 남은 B, D, F 정점도 동일한 메커니즘으로 탐색

아래는 Queue를 이용한 BFS 함수 코드이다.

typedef struct QueueType
{
    int queue[100];
    int front, rear;
}QueueType;


void bfs_mat(GraphType* g, int v){
    int w;
    QueueType q;

    queue_init(&q);
    visited[v] = TRUE;
    printf("%d 방문 -> ",v);
    enqueue(&q, v);

    while(!is_empty(&q)){
        v = dequeue(&q);
        for (w = 0; w < g->n; w++)
            if (g->adj_mat[v][w] && !visited[w]){
                visited[w] = TRUE;
                printf("%d 방문 -> ",w);
                enqueue(&q, w);
            }
    }
}

DFS vs BFS

• 다음과 같이 상황에 따라 DFS와 BFS를 알맞게 사용하는 것이 유리하다.