[C언어] graph 탐색 BFS 인접 행렬

이전에 작성한 linked list 소스를 이해가 쉽게 인접 행렬로 구현함

인접 행렬

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define MAX_VERTICES 20   int adj_matrix[MAX_VERTICES+1][MAX_VERTICES+1]; int visited[MAX_VERTICES+1];   void graph_init() {     int vi,vo;     for (vi = 0; vi<MAX_VERTICES; vi++){         for (vo = 0; vo<MAX_VERTICES; vo++){             adj_matrix[vi][vo] = 0;         }         visited[vi] = 0;     } }   void insert_edge(int u, int v) {     // 간선 정보 u->v     adj_matrix[u][v]=1; }   // 간단 queue typedef int element; int  front, rear; element  queue[MAX_VERTICES+2];   void init() {     front = rear = 0; }   int is_empty() {     return (front == rear); }   void enqueue(element item) {     rear++;     queue[rear] = item; }   element dequeue() {     front++;     return queue[front]; }   // BFS 이해가 쉽게 인접 행렬로 구현 void bfs_list(int v) {     int w;     init();     visited[v] = TRUE;     printf("%d ", v);      enqueue(v);     while (!is_empty()) {         v = dequeue();         for (w = 0; w < MAX_VERTICES; w++ ){             if (adj_matrix[v][w]==1 && !visited[w]) {                 visited[w] = TRUE;                 printf("%d ", w);                 enqueue(w);             }         }     } }   main() {     int i;       graph_init();       insert_edge(1, 9);     insert_edge(1, 5);     insert_edge(1, 2);     insert_edge(2, 3);     insert_edge(3, 4);     insert_edge(5, 8);     insert_edge(5, 6);     insert_edge(6, 7);     insert_edge(9, 10);     bfs_list(1); } Colored by Color Scripter

cs

bfs_list(1)에서 1은 출발 정점

결과

1

1 2 5 9 3 6 8 10 4 7

cs

인접 행렬 리스트로 구현함

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define MAX_VERTICES 20 #define MAX_ALIST    20   typedef struct{     int in;     int out; }adj_info;   adj_info adj_alist[MAX_ALIST+1]; int edge_count = 0;   int visited[MAX_VERTICES+1];   void graph_init() {     int i;     for (i = 0; i<MAX_ALIST; i++){         adj_alist[i].in = 0;         adj_alist[i].out = 0;     }     edge_count=0; }   void insert_edge(int u, int v) {     // 간선 정보 u->v     adj_alist[edge_count].in = u;     adj_alist[edge_count].out = v;     edge_count++; }   // 간단 queue typedef int element; int  front, rear; element  queue[MAX_VERTICES+2];   void init() {     front = rear = 0; }   int is_empty() {     return (front == rear); }   void enqueue(element item) {     rear++;     queue[rear] = item; }   element dequeue() {     front++;     return queue[front]; }   // BFS 이해가 쉽게 인접 행렬로 구현 void bfs_list(int v) {     int w;     init();     visited[v] = TRUE;     printf("%d ", v);      enqueue(v);     while (!is_empty()) {         v = dequeue();         for (w = 0; w < edge_count; w++ ){             if (adj_alist[w].in==v && !visited[adj_alist[w].out]) {                 visited[adj_alist[w].out] = TRUE;                 printf("%d ", adj_alist[w].out);                 enqueue(adj_alist[w].out);             }         }     } }   main() {     int i;       graph_init();       insert_edge(1, 9);     insert_edge(1, 5);     insert_edge(1, 2);     insert_edge(2, 3);     insert_edge(3, 4);     insert_edge(5, 8);     insert_edge(5, 6);     insert_edge(6, 7);     insert_edge(9, 10);     bfs_list(1); } Colored by Color Scripter

cs

결과

1

1 9 5 2 10 8 6 3 7 4

cs

기존 대비 BFS 내부의 연결된 간선 선택하는 부분이 변경되었습니다.

출력 결과는 이전과 다르지만 오른쪽 왼쪽 가운데 순서는 관계없고 level 단위로 처리만 되면 BFS이며 이것도 BFS 결과입니다.