[자료구조] 그래프 탐색 (DFS, BFS)

[ 그래프의 탐색 ]

- 그래프의 탐색

└ 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하여 탐색하는 것

많은 문제들이 단순 그래프의 노드(정점)를 탐색하느 것으로 해결 가능함

- 탐색 방법

└ 깊이 우선 탐색 ( DFS : Depth First Search )

너비 우선 탐색 ( BFS : Breath First Search )

(좌) DFS : 0-1-3-4-2-5-6 (우) BFS : 0-1-2-3-4-5-6

[ 깊이 우선 탐색 (DFS) ]

- 깊이 우선 탐색 (DFS)

└ 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 탐색 방법이다.

주로 스택을 사용하여 구현, 단순 탐색 속도 자체는 너비 우선 탐색 (BFS)에 비해 느림.

탐색이 아닌 순회를 할 경우 자주 사용한다

① 갈림길이 나타날 때마다 '다른 길'의 정보만 기록하며 지나온 길을 지운다

② 더 이상 갈 수 없게 되면 직전의 갈림길까지 돌아가며 현재 루트는 아니라는 표식을 남긴다.

③ 갈림길을 순차적으로 탐색하며 반복한다.

④ 탐색에 성공할 경우 종료한다.

- 깊이 우선 탐색 (DFS) 장/단점

└ 장점 : 현 경로상의 노드만을 기억하므로 저장 공간의 수요가 비교적 적음

탐색 목표의 노드가 깊은 단계에 있을 경우 빠르게 탐색 가능

단점 : 해가 없는 경로에 깊이 빠질 가능성이 있음. (이럴 경우 미리 지정한 임의 깊이까지만 탐색 후 실패할 경우 다음 경로 탐색하는 방법 사용)

얻어진 해가 최단 경로가 된다는 보장이 없음 (DFS 방식은 해에 다다르는 경우 탐색을 종료하므로 최적이 아닐 가능성 있음)

- DFS 알고리즘 복잡도 [ V : 노드 수 / E : 간선 수 ]

└ 시간 복잡도 : O(V + E)

공간 복잡도 : O(V)

- DFS 알고리즘

└ DFS의 구현은 그래프 각 정점의 방문 여부를 확인하는 것으로 분류한다.

① 스택의 최상단에 그래프의 정점 중 하나를 배치한다

② 스택의 top에 있는 정점을 가져와 방문 목록에 추가한다.

③ 해당 정점의 인접 노드 목록을 생성, 방문 목록에 없는 것을 스택의 상단에 추가한다.

④ 스택이 비어 있을 떄까지 ②와 ③ 반복.

정점 0에서 시작하는 경우. 인접 노드인 1, 2, 3을 스택에 추가. 0은 방문한 것으로 표시

0-1-2-4 순서대로 방문 후 인접 노드가 없을 경우. 직전 노드인 0으로 돌아간 후 인접 노드인 3을 방문

[ 깊이 우선 탐색 (DFS) 알고리즘 구현 ]

// C code
// 인접행렬로 표현된 무향 그래프의 DFS 구현
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50

int visited[MAX_VERTICES]; // 방문 여부를 확인하기 위한 배열

typedef struct GraphType {
    int n;	// 정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

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

// 정점 삽입 연산
void insert_vertex(GraphType* g, int v) {
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}

// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end) {
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}

// 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_mat(GraphType* g, int v) {
    int w;
    visited[v] = TRUE;            // 정점 v의 방문 체크
    printf("정점 %d -> ", v);     // 방문한 정점 출력
    for (w = 0; w < g->n; w++)    // 인접 노드 탐색
        if (g->adj_mat[v][w] && !visited[w])
            dfs_mat(g, w);        //정점 w에서 DFS 새로 시작
}

int main(void){
    GraphType* g = (GraphType*)malloc(sizeof(GraphType));;
    init(g);

    for (int i = 0; i < 5; i++)
        insert_vertex(g, i);

    insert_edge(g, 0, 1);
    insert_edge(g, 0, 2);
    insert_edge(g, 0, 3);
    insert_edge(g, 1, 2);
    insert_edge(g, 2, 4);

    printf("<깊이 우선 탐색 (DFS)>\n");
    dfs_mat(g, 0);
    printf("\n");
    free(g);

    return 0;
}

[ 너비 우선 탐색 (BFS) ]

- 너비 우선 탐색 (BFS)

└ 시작 정점으로부터 인접한 노드를 먼저 탐색, 멀리 떨어져 있는 노드를 나중에 방문하는 탐색방법.

주로 큐를 사용하여 구현.

① 루트 노드에서 시작

② 루트 노드의 인접 노드들의 목록을 큐에 저장

③ 인접 노드 목록의 노드들을 차례로 방문

④ ③번 과정의 인접 노드 방문시 해당 인접 노드의 인접 노드(방문하지 않은) 목록을 큐에 저장

⑤ 해당 과정을 반복, 모든 노드 방문시 탐색 종료

- 너비 우선 탐색 (BFS) 장/단점

└ 장점 : 여러 갈래 중 무한한 길이를 가지는 경로가 존재하며 탐색 목표가 다른 경로에 존재할 경우

DFS의 경우 탐색 불가능하지만 BFS의 경우 모든 경로를 동시에 탐색하기 때문에 탐색 가능

노드의 수가 적거나 깊이가 얕을수록 탐색에 유리(최선의 상황에서 최선의 탐색 가능)

단순 검색 속도는 깊이 우선 탐색(DFS) 보다 빠름

너비를 우선적으로 탐색하기에 탐색 정점으로의 경로가 여러개 일지라도 최단 경로를 보장 가능

최단 경로가 존재할 경우 어느 한 경로가 무한히 깊어지더라도 최단 경로 탐색 가능

단점 : 재귀호출을 이용하는 DFS와 달리 큐에 다음 탐색 노드들을 저장하므로 저장 공간을 상대적으로 많이 사용

노드의 수가 많거나 깊이가 깊을수록 탐색에 불리함

- BFS 알고리즘 복잡도 [ V : 노드 수 / E : 간선 수 ]

└ 시간 복잡도 : O(V + E)

공간 복잡도 : O(V)

- BFS 알고리즘

└ BFS의 구현 또한 그래프 각 정점의 방문 여부를 통해 분류

① 시작 정점의 인접 노드들을 큐에 저장

② 큐에 저장된 노드 FRONT에 위치한 노드를 방문, 해당 노드의 방문하지 않은 인접 노드가 존재할 경우 큐의 후단에 해당 노드 삽입

③ 큐가 전부 비거나 방문 목록이 전부 찰 때 까지 ②번 반복.

루트 노드 0과 인접한 노드 1, 2, 3을 큐에 삽입 후 큐의 FRONT 노드부터 순차 탐색

2번 노드 방문시 인접 노드 목록 중 방문하지 않은 4번 노드 존재. 해당 노드를 큐의 후단에 삽입 후 탐색 재개

[ 너비 우선 탐색 (BFS) 알고리즘 구현 ]

// C code
// 인접행렬로 표현된 무향 그래프의 BFS 구현
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct { // 큐 타입
    element  queue[MAX_QUEUE_SIZE];
    int  front, rear;
} QueueType;

// 오류 검증 함수
void error(char* message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// 큐 초기화 함수
void queue_init(QueueType* q) {
    q->front = q->rear = 0;
}

// 공백 상태 검증 함수
int is_empty(QueueType* q) {
    return (q->front == q->rear);
}
// 포화 상태 검증 함수
int is_full(QueueType* q) {
    return ((q->rear + 1) %
        MAX_QUEUE_SIZE == q->front);
}
// 큐 삽입 함수
void enqueue(QueueType* q, element item) {
    if (is_full(q))
        error("큐가 포화상태입니다");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}
// 큐 삭제 함수
element dequeue(QueueType* q) {
    if (is_empty(q))
        error("큐가 공백상태입니다");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

#define MAX_VERTICES 50
typedef struct GraphType {
    int n;	// 정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

int visited[MAX_VERTICES];

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

// 정점 삽입 연산
void insert_vertex(GraphType* g, int v) {
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}

// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end) {
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}

// 인접 행렬로 표현된 그래프에 대한 너비 우선 탐색
void bfs_mat(GraphType* g, int v) {
    int w;
    QueueType q;
    queue_init(&q);       // 큐 초기화 
    visited[v] = TRUE;    // 정점 v 방문 표시 
    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);      // 방문한 정점을 큐에 저장
            }
    }
}

int main(void)
{
    GraphType* g;
    int i;
    g = (GraphType*)malloc(sizeof(GraphType));
    graph_init(g);
    for (i = 0; i < 5; i++)
        insert_vertex(g, i);

    insert_edge(g, 0, 1);
    insert_edge(g, 0, 2);
    insert_edge(g, 0, 3);
    insert_edge(g, 1, 2);
    insert_edge(g, 2, 4);

    printf("《 너비 우선 탐색 (BFS) 》\n");
    bfs_mat(g, 0);
    printf("\n");
    free(g);
    return 0;
}

저작자표시 비영리 변경금지 (새창열림)

티스토리툴바