[C] 그래프와 DFS, BFS 구현

그래프(Graph)에 대해 알아보자.

그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료구조이다. 가장 쉬운 예로는 지하철 노선도가 있겠다.

 

 

서울시 지하철 노선도이다. 역과 역 사이는 철로로 연결되어 있고, 노선도에 거리는 나와있지 않지만 대충 길이를 보고 종착지로의 최단 경로도 파악할 수 있다. 연결 상태를 파악할 수 있는 자료구조이기 때문에 다음과 같은 필드에 응용할 수 있다:

 

• 전기회로의 연결 상태
• 운영 체제에서 프로세스와 자원들의 연관 관계
• 미로
• 과목 간의 연관관계(선수과목 파악)

 

 

 

간선들에 수치가 부여되어 있으므로 그래프 중에서도 가중치 그래프이다.

 

그래프는 정점과 간선들의 유한 집합이라고 할 수 있다. 해당 그래프의 이름을 G1이라고 한다면, 

V(G1) = { a, b, c, d, e, f }
E(G1) = { (a, b), (a, c), (a, f), (b, c), (b, d), (c, f), (d, e), (e, f) }

 

참고로 방향 그래프에서 차수를 따질 때는 진입 차수와 진출 차수로 나누는데, 진입 차수는 외부에서 오는 간선의 개수, 진출 차수는 외부로 향하는 간선의 개수이다.

 

 

그래프의 구현

(1) 인접행렬 - 배열

무방향 그래프에서 이용한다. 간선이 있으면 1, 그렇지 않으면 0으로 표현하는 방식이다. 인접행렬이 대칭이라는 점에 유의하자.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAX_VTXS 10
 
typedef char VtxData;
 
int adj[MAX_VTXS][MAX_VTXS]; //인접행렬
int vsize; //전체 정점의 개수
VtxData vdata[MAX_VTXS]; //정점에 저장할 데이터 배열
 
void init() {
    int i, j;
    vsize = 0;
    for (i = 0; i < MAX_VTXS; i++)
        for (j = 0; j < MAX_VTXS; j++)
            adj[i][j] = 0;
}
int is_full() {
    if (vsize > MAX_VTXS) return 1;
    else 0;
}
void insert_vertex(char name) {
    if (is_full() == 1) {
        printf("Error: 정점 개수 초과\n");
    }
    else vdata[vsize++] = name;
}
void insert_edge(int u, int v, int value) {
    adj[u][v] = value;
}
void insert_edge2(int u, int v, int value) {
    adj[u][v] = adj[v][u] = value;
}
void print_all() {
    for (int i = 0; i < vsize; i++) {
        for (int j = 0; j < vsize; j++) {
            printf("%2d ", adj[i][j]);
        }
        printf("\n");
    }
}
 
int main(void) {
    init();
    for (int i = 0; i < 4; i++)
        insert_vertex('A' + i);
    insert_edge2(0, 1, 1);
    insert_edge2(0, 3, 1);
    insert_edge2(1, 2, 1);
    insert_edge2(0, 3, 1);
    insert_edge2(2, 3, 1);
    insert_edge2(0, 1, 1);
    insert_edge2(0, 1, 1);
    printf("그래프(인접행렬)\n");
    print_all();
}
 

 

 

(2)인접 리스트 - 연결리스트

배열이 아니라 연결리스트를 이용함. 각 정점들이 연결리스트를 가진다. 결과창은 배열과 똑같다. 배열을 쓰면 공간 낭비가 심해서 연결리스트를 자꾸 쓰는 듯.

 

 

 

그래프의 탐색

vertex는 우위가 없다. 저번 포스트의 우선순위 큐처럼 가중치가 없고 값만 배정되어 있기 때문이다. 그래서 '어디서부터 시작해서 어떻게 탐색할 것인가'가 고민거리가 되는데, 어디서부터 시작할지는 사용자가 지정해줘야 한다. how에는 두가지 종류가 있다.

 

1. 깊이 우선 탐색(DFS)

시작 정점을 v라고 했을 때, v에서 한 방향으로 계속 가다가 더 이상 갈 수 있는 정점이 없게 되면 다시 가장 가까운 갈림길로 돌아와서, 다른 방향으로 다시 탐색을 진행하는 방법이다. 일단 v부터 시작하면 v는 '방문되었다'로 인식한다. 그리고 v에서 인접한 정점들 중에서 아직 방문하지 않은 정점을 선택하는 것이다. 스택을 이용해서 구현한다.

 

탐색 순서: A - B - D - C - E - G - H - F

 

  <소스 코드 & 결과 창>

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 10
 
typedef char VtxData;
 
int adj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vsize;
VtxData vdata[MAX_VERTEX_NUM];
 
int visited[MAX_VERTEX_NUM]; //이미 방문한 노드는 방문 안하게 하기 위한 배열
 
void init() {
    vsize = 0;
    for (int i = 0; i < MAX_VERTEX_NUM; i++)
        for (int j = 0; j < MAX_VERTEX_NUM; j++)
            adj[i][j] = 0;
}
int is_full() {
    if (vsize > MAX_VERTEX_NUM) return 1;
    else return 0;
}
void insert_vertex(char name) {
    if (is_full() == 1) {
        printf("Error: 정점 개수 초과\n");
    }
    else
        vdata[vsize++] = name;
}
void insert_edge(int u, int v, int value) { //무방향 그래프
    adj[u][v] = value;
    adj[v][u] = value;
}
void DFS_search(int n) {
    visited[n] = 1; //현재 노드 n 방문 표시
    printf("정점 %c ->", vdata[n]); //방문한 정점 순차 출력
    for (int i = 0; i < vsize; i++) //인접 정점 탐색
        if ((adj[n][i] != 0) && (visited[i] == 0))
            DFS_search(i);
}
void print_all() {
    for (int i = 0; i < vsize; i++) {
        for (int j = 0; j < vsize; j++) {
            printf("%2d ", adj[i][j]);
        }
        printf("\n");
    }
}
 
int main(void) {
 
    init();
    for (int i = 0; i < 4; i++)
        insert_vertex('A' + i);
    insert_edge(0, 1, 1);
    insert_edge(0, 3, 1);
    insert_edge(1, 2, 1);
    insert_edge(0, 3, 1);
    insert_edge(2, 3, 1);
    insert_edge(0, 1, 1);
    insert_edge(0, 1, 1);
 
    printf("인접행렬 그래프\n");
    print_all();
    printf("\n깊이 우선 탐색(DFS) with 인접행렬(배열)\n");
    DFS_search(0);
    
    printf("\n");
    return 0;
}
 
 

 

 

2. 너비 우선 탐색(BFS)

시작 정점 v에서부터 가장 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. v로부터 하나씩 가는게 아니라 여러개를 한꺼번에 갈 수 있음. 큐를 통해 구현한다.

 

 

  <소스 코드>

너무 길어져서(...) 구조체&변수 정의와 BFS 탐색용 함수만 짜보았다. enqueue와 dequeue가 있는 걸 봐선 그냥 둘 다 연결리스트로 구현이 되어 있어야 할듯....

 

typedef struct GraphNode {
    int id;
    struct GraphNode* link;
}GNode;
typedef char VtxData;
 
int vsize;
VtxData vdata[MAX_VERTEX_NUM];
GNode* adj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 
int visited[MAX_VERTEX_NUM];
 
void BFS_search(int n) {
    GNode* w;
    init();
    visited[n] = 1;
    printf("정점 %c ->", vdata[n]); 
    enqueue(n);
    while (is_empty() == 1) {
        n = dequeue();
 
        for (w = adj[n]; w != NULL; w = w->link) {
            if (visited[w->id] == 0) {
                visited[w->id] = 1;
                printf("%c ", vdata[w->id]);
                enqueue(w->id);
            }
        }
    }
}