[C언어] DFS(Depth First Search)

이번 포스팅은 인접 행렬과 visted을 통한 DFS Algorithm을 구현해본다. 

Keywords

- Vertex = Edge : 정점, 꼭 (0,1,2,3,4,5,6,7)를 의미한다.
- 인접 행렬 : 그래프 이론에서, 인접행렬 (Adjacency Matrix)은 그래프에서 어느 꼭짓점(Vertex)들이 어느 변으로 연결되어 있는지를 나타내는 정사각형 행렬이다. 
- Visited : 어느 꼭짓점을(Vertex)방문 했는가에 대한 여부, flag같은 개념

이것만 기억하자!
 - 방문된적이 없는 인접한 곳 중에서 가장 작은곳으로 이동한다.
- 인접한 vertex가 모두 방문된적이 있는 vertex면 이전 vertex로 다시 되돌아간다.

시나리오
Start Vertex는 0
1. 0에 인접한 vertex 1, 2중 둘다 방문한적이 없으니(visited flag = 0) 우선 1을 방문한다. 그리고나서 vertex 1의 visited flag를 1로 바꿔준다. 
2. 1에서 인접한 vertex 3, 4 중 둘다 방문한적이 없으니 우선 3을방문한다. 마찬가지로 vertex 3의 visited flag를 1로 바꿔준다.
3. 3에 인접한 vertex중 방문한적이 없는 vertex는 7이므로 7로 이동하고 vertex 7의 visited flag를 1로 바꿔준다.
4. 7에 인접한 vertex 3,4,5,6중에서 3은 방문한적이 있으므로 제외하고 우선 4를 방문한 후 vertex 4의 visited flag를 1로 바꿔준다.
5. 4에인접한 vertex 1,7 중에서 둘다 방문한적이 있으니 이전 vertex인 7로 되돌아간다.
6. 7에서 인접한 vertex중 방문한적이 없는 5, 6중에서 우선 5를 방문한 후 vertex 5의 visited flag를 1로 바꿔준다.
7. 5에 인접한 vertex 2,7중에서 방문한적 없는 vertex는 2밖에 없으니 2를 방문한 후 vertex 2의 visited flag를 1로 바꿔준다.
8. 2에 인접한 vertex중 방문한적이 없는 6을 방문한 후 vertex 6의 visited flag를 1로 바꿔준다.
0->1-> 3-> 7-> 4-> 5->2->6

1. Make Graph

4 typedef struct Graph{ 5 int numOfVertex; 6 int **matrix; 7 int *visited; 8 9 }Graph; 10 11 Graph* makeGraph(int numOfVertex){ 12 int i=0; 13 Graph *graph = (Graph*)malloc(sizeof(Graph)*numOfVertex); 14 graph->matrix = (int**)malloc(sizeof(int*)*numOfVertex); 15 graph->visited = (int*)malloc(sizeof(int)*numOfVertex); 16 graph->numOfVertex = numOfVertex; 17 for(i=0; i<numOfVertex; i++){ 18 graph->matrix[i] = (int*)malloc(sizeof(int)*numOfVertex); 19 memset(graph->matrix[i], 0, sizeof(int)*numOfVertex); 20 graph->visited[i] = 0; 21 } 22 return graph; 23 }

line 13 : Vertex의 개수만큼 Graph 구조체변수를 동적할당 해준다.
line 14, line18 : Vertex * Vertex 의 행렬을 만들기 위해 2차 배열을 동적할당을 해준다. 
line 15 : Vertex의 개수만큼 visited 배열을 동적할당 해준다.
line 16 : Vertex의 개수를 초기화 한다.
line 19 : Vertex의 개수만큼 행렬을 0의 값으로 초기화 한다.
line 20 : visited flag값을 0(false)로 초기화 한다.

2. Add Edge

무방향성 Edge를 생성한다. 무방향성 Edge이기 때문에 2차배열의 가로 인덱스와 세로 인덱스를 바꾸어 각각 1로 set해준다.

25 void addEdge(Graph* graph, int start, int end){ 26 graph->matrix[start][end] = 1; 27 graph->matrix[end][start] = 1; 28 }

Edge	0	1	2	3	4	5	6	7
0	[0][0] 0	[0][1] 1	[0][2] 1	[0][3] 0	[0][4] 0	[0][5] 0	[0][6] 0	[0][7] 0
1	[1][0] 1	[1][1] 0	[1][2] 0	[1][3] 1	[1][4] 1	[1][5] 0	[1][6] 0	[1][7] 0
2	[2][0] 1	[2][1] 0	[2][2] 0	[2][3] 0	[2][4] 0	[2][5] 1	[2][6] 1	[2][7] 0
3	[3][0] 0	[3][1] 1	[3][2] 0	[3][3] 0	[3][4] 0	[3][5] 0	[3][6] 0	[3][7] 1
4	[4][0] 0	[4][1] 1	[4][2] 0	[4][3] 0	[4][4] 0	[4][5] 0	[4][6] 0	[4][7] 1
5	[5][0] 0	[5][1] 0	[5][2] 1	[5][3] 0	[5][4] 0	[5][5] 0	[5][6] 0	[5][7] 1
6	[6][0] 0	[6][1] 0	[6][2] 1	[6][3] 0	[6][4] 0	[6][5] 1	[6][6] 0	[6][7] 1
7	[7][0] 0	[7][1] 0	[7][2] 0	[7][3] 1	[7][4] 1	[7][5] 1	[7][6] 1	[7][7] 0

3. DFS

43 void DFS(Graph* graph, int vertex){ 44 int i=0; 45 46 graph->visited[vertex] = 1; 47 printf("vertex %d is visited\n" , vertex); 48 49 for(i=0; i<graph->numOfVertex; i++){ 50 if(graph->matrix[vertex][i] == 1 && graph->visited[i] == 0 ){ 51 DFS(graph, i); 52 } 53 } 54 }

line 46 : 방문된 Vertex의 visited 값을 true로 바꿔준다.
line 50 : 매개변수 Vertex에 인접해있는 Vertex가 1이고 visited flag가 0이면 (방문된적 없음) DFS 재귀한다.

4. Print Graph

그래프를 행렬 형태로 출력해주는 함수.

30 void printGraph(Graph *graph) 31 { 32 int i, j; 33 34 for (i = 0; i < graph->numOfVertex; i++) { 35 printf("start %d ->", i); 36 for (j = 0; j < graph->numOfVertex; j++) { 37 printf("%d ", graph->matrix[i][j]); 38 } 39 printf("\n"); 40 } 41 }

5. Main

57 int main(void) 58 { 59 60 Graph *graph; 61 graph = makeGraph(8); 62 63 addEdge(graph, 0, 1); 64 addEdge(graph, 0, 2); 65 addEdge(graph, 1, 3); 66 addEdge(graph, 1, 4); 67 addEdge(graph, 3, 7); 68 addEdge(graph, 4, 7); 69 addEdge(graph, 2, 5); 70 addEdge(graph, 2, 6); 71 addEdge(graph, 6, 7); 72 addEdge(graph, 5, 7); 73 74 printGraph(graph); 75 76 DFS(graph, 0); 77 78 return 0; 79 }

line 60 : Graph를 초기화 해준다.
line 63 - line 72 : Edge를 생성한다.
line 74 : 행렬 출력
line 76 : DFS를 수행한다.

결과 화면

전체 소스

#include <stdio.h> 2 #include <stdlib.h> 3 #include <memory.h> 4 typedef struct Graph{ 5 int numOfVertex; 6 int **matrix; 7 int *visited; 8 9 }Graph; 10 11 Graph* makeGraph(int numOfVertex){ 12 int i=0; 13 Graph *graph = (Graph*)malloc(sizeof(Graph)*numOfVertex); 14 graph->matrix = (int**)malloc(sizeof(int*)*numOfVertex); 15 graph->visited = (int*)malloc(sizeof(int)*numOfVertex); 16 17 graph->numOfVertex = numOfVertex; 18 for(i=0; i<numOfVertex; i++){ 19 graph->matrix[i] = (int*)malloc(sizeof(int)*numOfVertex); 20 memset(graph->matrix[i], 0, sizeof(int)*numOfVertex); 21 graph->visited[i] = 0; 22 } 23 return graph; 24 } 25 26 void addEdge(Graph* graph, int start, int end){ 27 graph->matrix[start][end] = 1; 28 graph->matrix[end][start] = 1; 29 } 30 void printGraph(Graph *graph) 31 { 32 int i, j; 33 34 for (i = 0; i < graph->numOfVertex; i++) { 35 printf("start %d ->", i); 36 for (j = 0; j < graph->numOfVertex; j++) { 37 printf("%d ", graph->matrix[i][j]); 38 } 39 printf("\n"); 40 } 41 } 42 43 void DFS(Graph* graph, int vertex){ 44 int i=0; 45 graph->visited[vertex] = 1; 46 printf("vertex %d is visitied\n" , vertex); 47 48 for(i=0; i<graph->numOfVertex; i++){ 49 if(graph->matrix[vertex][i] == 1 && graph->visited[i] == 0 ){ 50 DFS(graph, i); 51 } 52 } 53 54 } 55 56 int main(void) 57 { 58 59 Graph *graph; 60 graph = makeGraph(8); 61 62 addEdge(graph, 0, 1); 63 addEdge(graph, 0, 2); 64 addEdge(graph, 1, 3); 65 addEdge(graph, 1, 4); 66 addEdge(graph, 3, 7); 67 addEdge(graph, 4, 7); 68 addEdge(graph, 2, 5); 69 addEdge(graph, 2, 6); 70 addEdge(graph, 6, 7); 71 addEdge(graph, 5, 7); 72 73 printGraph(graph); 74 75 DFS(graph, 0); 76 77 return 0; 78 }

참고 문헌 : https://www.programiz.com/dsa/graph-dfs