DFS(깊이 우선 탐색)

1.인접 행렬에서의 DFS

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50

typedef struct GraphType{
    int n;
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

int visited[MAX_VERTICES]; // 방문 정점

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,"vertex overflow");
        return;
    }
    g->n++;
}

void insert_edge(GraphType *g, int start, int end){
    if(start >= g->n || end >= g->n){
        fprintf(stderr, "edge error");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}

// void print_adj_mat(GraphType *g){
//     for(int i=0; i<g->n; i++){
//         for(int j=0; j<g->n; j++){
//             printf("%2d", g->adj_mat[i][j]);
//         }
//         printf("\n");
//     }
// }

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

int main(){
    GraphType *g;
    g = (GraphType*)malloc(sizeof(GraphType));
    init(g);
    for(int i=0; i<4; 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, 3);
    
    printf("dfs\n");
    dfs_mat(g,0);
    printf("\n");
    free(g);
    return 0;
}

현재 그래프의 상태는 다음과 같다

인접행렬(adj_mat[][])로 나타낼 경우 다음과 같다.
--0 1 2 3
0 0 1 1 1
1 1 0 1 1
2 1 1 0 1
3 1 0 1 0

DFS 탐색 함수 부분을 보자

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

dfs_mat(g, 0) 호출 시 일어나는 과정을 한 단계씩 분석해보자

dfs_mat(g, 0) 즉, 0의 위치에서 dfs 탐색을 시도하였다.
1. visited[0] = TRUE
2. printf("vertex 0 ->")
3. g->adj_mat[0][0] && !visited[0] 의 결과는 0 && 1 이므로 거짓이 된다
4. g->adj_mat[0][1] && !visited[1] 의 결과는 1 && 1 이므로 참이 되어 재귀 호출을 하게 된다.

dfs_mat(g, 1)
5. visited[1] = TRUE
6. printf("vertex 1 ->")
7. g->adj_mat[1][0] && !visited[0] 의 결과는 1 && 0 이므로 거짓이 된다
8. g->adj_mat[1][1] && !visited[1] 의 결과는 0 && 0 이므로 거짓이 된다
9. g->Adj_mat[1][2] && !visited[2] 의 결과는 1 && 1 이므로 참이 되어 재귀 호출을 하게 된다.

dfs_mat(g, 2)
10. visited[2] = TRUE
11. printf("vertex 2 ->")
12. g->adj_mat[2][0] && !visited[0] 의 결과는 1 && 0 이므로 거짓이 된다
13. g->adj_mat[2][1] && !visited[1] 의 결과는 1 && 0 이므로 거짓이 된다
14. g->adj_mat[2][2] && !visited[2] 의 결과는 0 && 0 이므로 거짓이 된다
15. g->adj_mat[2][3] && !visited[3] 의 결과는 1 && 1 이므로 참이 되어 재귀 호출을 하게 된다.

dfs_mat(g, 3)
16. visited[3] = TRUE
17. printf("vertex 3 ->")
18. g->adj_mat[3][0] && !visited[0] 의 결과는 1 && 0 이므로 거짓이 된다
19. g->adj_mat[3][1] && !visited[1] 의 결과는 0 && 0 이므로 거짓이 된다
20. g->adj_mat[3][2] && !visited[2] 의 결과는 1 && 0 이므로 거짓이 된다
21. g->adj_mat[3][3] && !visited[3] 의 결과는 0 && 0 이므로 거짓이 된다

 

결과 출력 값은 다음과 같다

2.인접 리스트에서의 DFS

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50

typedef struct GraphNode{
    int vertex;
    struct GraphNode *link;
} GraphNode;

typedef struct GraphType{
    int n;
    GraphNode *adj_list[MAX_VERTICES];
} GraphType;

int visited[MAX_VERTICES];

void init(GraphType *g){
    int v;
    g->n = 0;
    for(v=0; v<MAX_VERTICES; v++){
        g->adj_list[v] = NULL;
    }
}

void insert_vertex(GraphType *g, int v){
    if(((g->n)+1) > MAX_VERTICES){
        fprintf(stderr, "vertex overflow");
        return;
    }
    g->n++;
}

void insert_edge(GraphType *g, int u, int v){
    GraphNode *node;
    if(u>=g->n || v>=g->n){
        fprintf(stderr, "edge error");
        return;
    }
    node = (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

void dfs_list(GraphType *g, int v){
    GraphNode *node;
    visited[v] = TRUE;
    printf("vertex %d ->", v);
    for(node = g->adj_list[v]; node; node = node->link){
        if(!visited[node->vertex]){
            dfs_list(g, node->vertex);
        }
    }
}

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

    for(int i=0; i<4; i++){
        insert_vertex(g, i);
    }

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

    printf("dfs\n");
    dfs_list(g, 0);
    free(g);
    return 0;
}