티스토리 뷰
주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
DFS가 한 사람에게 연락을 취하는 방식이라면, BFS는 자신에게 연결된 모든 사람에게 연락을 취하는 방식입니다. 다음과 같은 그래프에서,
지율에게 비상 메시지가 도착했고, 지율로부터 시작해서 모두에게 비상 메시지를 전달해야 합니다. 이번에는 DFS와는 달리, 지율이 연락할 수 있는 모든 사람들에게 연락합니다.
그리고 동수와 민석도 각각 자신이 연락할 수 있는 모든 사람들에게 연락합니다. 다만 순서를 임의로 정했습니다. 동수와 민석이가 동시에 연락을 하지 않게 하기 위해 동수가 먼저 연락 가능한 모든 사람들에게 연락하고 이어서 민석이가 연락하기로 합니다. 이 순서는 달라져도 상관없습니다. 동수는 지민에게 연락합니다.
그리고 이어서 민석이가 연락을 할 차례입니다. 그런데 민석이와 연결되어 있는 지민은 이미 동수에게서 연락을 받았으므로 민석은 지민이에게는 연락하지 않고, 수정과 정희에게 연락합니다.
그리고 수정과 정희 중에 수정이 먼저 연락을 취하고 정희가 그 다음 순서로 할 것을 전했습니다. 민석의 차례가 끝이 났고, 동수가 연락했던 지민이 연락을 취할 차례입니다. 그런데 지민은 연락할 사람이 없으므로 건너뜁니다. 그리고 수정의 차례가 됐습니다. 수정 역시도 연락할 사람이 없으므로 건너뜁니다. 다음으로 정희의 차례가 되고 정희는 명석에게 연락합니다.
그리고 다음 순서로 명석의 차례가 되고 명석이 연락할 상대가 없으므로 비로소 연락 전달 과정은 끝이 납니다. 이러한 방법을 너비 우선 탐색, BFS라고 합니다.
이제 깊이 우선 탐색 방법인 DFS를 구현해 볼 차례입니다. DFS의 구현을 위해서는 '스택'과 '배열'이 필요합니다. 우선 배열은 각 정점에 방문한 적이 있는지 없는지를 기록하기 위해 사용합니다. 스택은 한 정점에서 다음 정점으로 이동할 때, 다음 정점으로 이동하기 위해 떠난 정점을 저장하는 데에 사용합니다. 어떤 식으로 사용되는지 예를 들겠습니다.
위의 그래프가 있을 때, 지율부터 시작해서 DFS 방법으로 모든 정점을 방문하고자 합니다. 그리고 다음은 배열과 스택입니다.
지율을 제외한 배열의 각 정점에 해당하는 칸에는 0이 저장되어 있습니다. 이 0 값은 아직 해당 정점에는 방문한 적이 없음을 의미합니다. 정점에 방문하게 되면 해당 데이터는 1로 바뀝니다. 현재 지율로부터 모든 정점의 방문을 시작할 것이기 때문에 시작 정점인 지율은 방문했다고 표시합니다.
이어서 지율이 민석에게 연락합니다.
지율을 떠나 민석을 방문했으므로 스택에 지율을 저장하고, 배열의 민석에 해당하는 요소의 데이터를 1로 바꾸어 방문했음을 기록합니다. 이어서 민석 → 수정 → 정희 → 명석 순서로 방문하면 다음과 같이 됩니다.
명석과 연결된 정점은 모두 이미 방문한 적이 있는 정점입니다. 따라서 명석은 자신에게 연락해 온 정희에게 다시 연락해서 자신은 더 연락할 정점이 없으니 혹시 정희와 연결된 정점 중에 방문하지 않은 곳이 있으면 연락하라고 전해야 합니다. 이는 스택을 이용하면 가능합니다. 스택에는 연락이 전달되면서 떠나온 정점들을 저장해 두고 있기 때문에 현재 스택에는 정희가 가장 위에 저장되어 있습니다. 따라서 스택에서 데이터를 하나 빼고, 해당 정점에 다시 방문합니다.
정희도 역시 더 이상 연락할 정점이 없으므로 스택의 가장 위에 저장되어 있는 수정에게 다시 방문하고, 똑같은 방법으로 다시 민석에게 방문합니다.
민석은 지민에게 연락하고, 지민은 동수에게 연락합니다.
이로써 모든 정점을 방문했지만 아직 끝난 것은 아닙니다. 스택에 값이 아직 남아 있으므로 스택에 저장되어 있는 모든 값들을 하나씩 빼면서 해당 정점을 따라 되돌아와야 합니다. 그렇게 되면 현재 동수에서 지민, 민석, 지율의 순서로 하여 처음 시작 정점이었던 지율에게 다시 돌아오게 됩니다. 이로써 DFS가 완전히 종료됩니다.
이제 이를 코드로 구현해 보겠습니다. 우리는 앞서 구현했던 ALGraph.h 파일과 ALGraph.c 파일을 확장하여 ALGraphDFS.h 와 ALGraphDFS.c 파일을 만들 겁니다. 그리고 확장하는 과정에서 다음의 함수를 추가합니다.
void DFShowGraphVertex(ALGraph* pg, int startV); //그래프의 정점 정보 출력위 함수의 두 번째 인자를 통해서 시작 정점을 정합니다. 그러면 시작 정점을 시작으로 하여 모든 정점을 거치면서 정점의 이름을 출력합니다. 배열과 스택도 활용하기 때문에 필요한 파일들은 다음과 같습니다.
- ALGraphDFS.h
- ALGraphDFS.c
- LLBStack.h
- LLBStack.c
- LinkedList.h
- LinkedList.c
- Main.c
이 중에서 ALGraphDFS.h 파일을 먼저 소개합니다.
//ALGraphDFS.h
//수정 날짜 : 2021.03.28
//작성자 : KOEY
#ifndef AL_GRAPH_DFS_H
#define AL_GRAPH_DFS_H
#include "LinkedList.h"
//정점의 이름을 상수화
enum { A, B, C, D, E, F, G, H, I, J, K };
typedef struct Ual
{
int numV;
int numE;
List* adjList;
int* visitInfo; //추가된 변수, 각 정점의 방문 정보를 저장하는 배열의 주소
}ALGraph;
void GraphInit(ALGraph* pg, int nv);
void GraphDestroy(ALGraph* pg);
void AddEdge(ALGraph* pg, int fromV, int toV);
void ShowGraphEdgeInfo(ALGraph* pg);
void DFShowGraphVertex(ALGraph* pg, int startV); // 추가된 함수DFS 기반, 정점의 정보 출력
#endif다음은 ALGraphDFS.c 파일입니다. 구조체에 새로운 변수가 추가됨에 따라 초기화 함수와 그래프 삭제 함수에도 변경사항이 생겼습니다.
//ALGraphDFS.c
//수정날짜 : 2021.03.27
//작성자 : KOEY
#include "ALGraphDFS.h"
#include "LLBStack.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
void GraphInit(ALGraph* pg, int nv)
{
pg->adjList = (List*)malloc(sizeof(List) * nv); //List 구조체 변수를 저장할 배열 생성
if (pg->adjList == NULL)
{
printf("메모리 공간이 부족합니다.\n");
exit(1);
}
int i;
for (i = 0; i < nv; i++)
{
ListInit(&(pg->adjList[i])); //배열의 각각의 List 구조체 변수를 초기화
}
pg->numE = 0;
pg->numV = nv;
pg->visitInfo = (int*)malloc(sizeof(int) * pg->numV); //추가된 코드
if (pg->visitInfo == NULL)
{
printf("메모리 공간이 부족합니다. \n");
exit(1);
}
memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}
void GraphDestroy(ALGraph* pg)
{
if (pg->adjList == NULL)
{
return;
}
int i;
for (i = 0; i < pg->numV; i++)
{
Data data;
while (LFirst(&(pg->adjList[i]), &data)) //리스트에 노드가 존재한다면
{
LRemove(&(pg->adjList[i])); //해당 노드 삭제
}
}
free(pg->adjList); //List 구조체 변수들을 저장하던 배열 삭제
pg->numE = 0;
pg->numV = 0;
if (pg->visitInfo != NULL) //추가된 코드
{
free(pg->visitInfo);
}
}
void AddEdge(ALGraph* pg, int fromV, int toV)
{
LInsert(&(pg->adjList[fromV]), toV + 'A');
LInsert(&(pg->adjList[toV]), fromV + 'A'); //무방향 그래프이므로 대칭되게 저장
pg->numE++;
}
void ShowGraphEdgeInfo(ALGraph* pg)
{
int i;
for (i = 0; i < pg->numV; i++) //모든 배열 요소에 대해
{
printf("%c와 연결된 정점 : ", i + 'A');
Data data;
if (LFirst(&(pg->adjList[i]), &data))
{
printf("%c ", data);
while (LNext(&(pg->adjList[i]), &data))
{
printf("%c ", data);
}
}
else
{
printf("없음");
}
printf("\n");
}
}
int VisitVertex(ALGraph* pg, int visitV)
{
if (pg->visitInfo[visitV] == 0) //visitV에 처음 방문한 경우 참
{
pg->visitInfo[visitV] = 1; //방문함의 의미로 1을 저장
printf("%c ", visitV + 'A'); //방문한 정점의 이름 출력
return TRUE; //방문 성공
}
return FALSE; //방문 실패
}
void DFShowGraphVertex(ALGraph* pg, int startV)
{
Stack stack;
int visitV = startV; //시작 정점을 방문 정점으로
int nextV; //다음 방문할 정점을 저장할 변수
StackInit(&stack);
VisitVertex(pg, visitV); //시작 정점 방문
//SPush(&stack, visitV);
while (LFirst(&(pg->adjList[visitV]), &nextV)) //방문한 정점과 연결된 정점이 있다면, 해당 정점을 다음 방문할 정점으로 저장
{
nextV = nextV - 'A';
int visitFlag = FALSE; //우선 방문 정보를 거짓으로 초기화
if (VisitVertex(pg, nextV)) //다음 방문할 정점에 성공적으로 방문 했다면, 즉, 처음 방문하는 것이라면
{
SPush(&stack, visitV); //스택에 떠나온 정점을 저장
visitV = nextV; //nextV를 방문 정점으로 변경
visitFlag = TRUE; //성공적으로 방문이 이루어짐
}
else //다음 방문할 정점에 이미 방문한 적이 있다면
{
while (LNext(&(pg->adjList[visitV]), &nextV)) //visitV에 연결된 다른 정점을 다음 방문할 정점으로 저장
{
nextV = nextV - 'A';
if (VisitVertex(pg, nextV))
{
SPush(&stack, visitV);
visitV = nextV;
visitFlag = TRUE;
break;
}
}
}
if (!visitFlag) //visitV에 연결된 다른 모든 정점에 방문할 수 없었다면
{
if (StackIsEmpty(&stack)) //스택이 비어 있다면
{
break; //반복문 종료
}
else //스택에 데이터가 남아 있다면, 즉, 돌아가야할 정점이 있다면
{
visitV = SPop(&stack); //돌아가야할 정점을 visitV로 저장
}
}
}
memset(pg->visitInfo, 0, sizeof(int) * pg->numV); //다음 차례 함수 호출을 위해 visitInfo를 0으로 초기화
}위 파일에서,
int VisitVertex(ALGraph* pg, int visitV)
{
if (pg->visitInfo[visitV] == 0) //visitV에 처음 방문한 경우 참
{
pg->visitInfo[visitV] = 1; //방문함의 의미로 1을 저장
printf("%c ", visitV + 'A'); //방문한 정점의 이름 출력
return TRUE; //방문 성공
}
return FALSE; //방문 실패
}위 함수는 헤더 파일에는 선언되어 있지 않습니다. 이 함수는 DFShowGraphVertex 함수에서 호출하게 될 함수입니다. 방문할 정점을 두 번째 인자로 전달받아 해당 정점에 방문하고, 방문 기록을 남깁니다. 만약 이전에 방문한 적이 있다면 false를 반환합니다.
void DFShowGraphVertex(ALGraph* pg, int startV)
{
Stack stack;
int visitV = startV; //시작 정점을 방문 정점으로
int nextV; //다음 방문할 정점을 저장할 변수
StackInit(&stack);
VisitVertex(pg, visitV); //시작 정점 방문
//SPush(&stack, visitV);
while (LFirst(&(pg->adjList[visitV]), &nextV)) //방문한 정점과 연결된 정점이 있다면, 해당 정점을 다음 방문할 정점으로 저장
{
nextV = nextV - 'A';
int visitFlag = FALSE; //우선 방문 정보를 거짓으로 초기화
if (VisitVertex(pg, nextV)) //다음 방문할 정점에 성공적으로 방문 했다면, 즉, 처음 방문하는 것이라면
{
SPush(&stack, visitV); //스택에 떠나온 정점을 저장
visitV = nextV; //nextV를 방문 정점으로 변경
visitFlag = TRUE; //성공적으로 방문이 이루어짐
}
else //다음 방문할 정점에 이미 방문한 적이 있다면
{
while (LNext(&(pg->adjList[visitV]), &nextV)) //visitV에 연결된 다른 정점을 다음 방문할 정점으로 저장
{
nextV = nextV - 'A';
if (VisitVertex(pg, nextV))
{
SPush(&stack, visitV);
visitV = nextV;
visitFlag = TRUE;
break;
}
}
}
if (!visitFlag) //visitV에 연결된 다른 모든 정점에 방문할 수 없었다면
{
if (StackIsEmpty(&stack)) //스택이 비어 있다면
{
break; //반복문 종료
}
else //스택에 데이터가 남아 있다면, 즉, 돌아가야할 정점이 있다면
{
visitV = SPop(&stack); //돌아가야할 정점을 visitV로 저장
}
}
}
memset(pg->visitInfo, 0, sizeof(int) * pg->numV); //다음 차례 함수 호출을 위해 visitInfo를 0으로 초기화
}위 함수의 정의는 직접 따라 작성해 보면서 어떻게 작동하게 될지 잘 살펴보길 권합니다. 앞서 그림으로 설명했던 알고리즘을 그대로 구현한 코드입니다.
이제 나머지 모든 파일들과 main.c 파일을 보이고, 실행결과를 확인하겠습니다.
//LinkedList.h 헤더 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct Node
{
Data data;
struct Node* next;
} Node;
typedef struct LinkedList
{
Node* head;
Node* cur;
Node* before;
int numOfData;
}LinkedList;
typedef LinkedList List;
void ListInit(List* plist);
void LInsert(List* plist, Data data);
int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
Data LRemove(List* plist);
int LCount(List* plist);
#endif//LinckedList.c 소스 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#include "LinkedList.h"
#include <stdlib.h>
#include <stdio.h>
void ListInit(List* plist)
{
plist->head = NULL;
plist->numOfData = 0;
}
void LInsert(List* plist, Data data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다.");
exit(1);
}
newNode->data = data;
if (plist->head == NULL)
{
newNode->next = NULL;
}
else
{
newNode->next = plist->head;
}
plist->head = newNode;
plist->numOfData++;
}
int LFirst(List* plist, Data* pdata)
{
plist->cur = plist->head;
plist->before = NULL;
if (plist->cur == NULL)
{
return FALSE;
}
*pdata = plist->cur->data;
return TRUE;
}
int LNext(List* plist, Data* pdata)
{
plist->before = plist->cur;
plist->cur = plist->cur->next;
if (plist->cur == NULL)
{
return FALSE;
}
*pdata = plist->cur->data;
return TRUE;
}
Data LRemove(List* plist)
{
Node* delNode = plist->cur;
Data delData = delNode->data;
plist->cur = plist->before;
if (delNode == plist->head)
{
plist->head = delNode->next;
}
else
{
plist->before->next = delNode->next;
}
free(delNode);
plist->numOfData--;
return delData;
}
int LCount(List* plist)
{
return plist->numOfData;
}
//LLBStack.h
//수정날짜 : 2021.03.28
//작성자 : KOEY
#ifndef LINKED_LIST_BASE_STACK_H
#define LINKED_LIST_BASE_STACK_H
#define TRUE 1
#define FALSE 0
typedef int SData;
typedef struct SNode
{
SData data;
struct SNode* next;
}SNode;
typedef struct LLBStack
{
SNode* head;
}LLBStack;
typedef LLBStack Stack;
void StackInit(Stack* pstack);
int StackIsEmpty(Stack* pstack);
void SPush(Stack* pstack, SData data);
SData SPop(Stack* pstack);
SData SPeek(Stack* pstack);
void DeleteStack(Stack* pstack);
#endif//LLBStack.c
//수정날짜 : 2021.03.28
//작성자 : KOEY
#include "LLBStack.h"
#include <stdlib.h>
#include <stdio.h>
void StackInit(Stack* pstack)
{
pstack->head = NULL;
}
int StackIsEmpty(Stack* pstack)
{
if (pstack->head == NULL)
{
return TRUE;
}
return FALSE;
}
void SPush(Stack* pstack, SData data)
{
SNode* newNode = (SNode*)malloc(sizeof(SNode));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다. \n");
exit(1);
}
newNode->data = data;
if (pstack->head == NULL)
{
newNode->next = NULL;
}
else
{
newNode->next = pstack->head;
}
pstack->head = newNode;
}
SData SPop(Stack* pstack)
{
SNode* delNode = pstack->head;
SData delData = delNode->data;
pstack->head = delNode->next;
free(delNode);
return delData;
}
SData SPeek(Stack* pstack)
{
return pstack->head->data;
}
void DeleteStack(Stack* pstack)
{
while (!StackIsEmpty(pstack))
{
SPop(pstack);
}
}//main.c
//수정날짜 : 2021.03.27
//작성자 : KOEY
#include <stdio.h>
#include "ALGraphDFS.h"
int main(void)
{
ALGraph graph; //그래프의 생성
GraphInit(&graph, 7); //그래프의 초기화
AddEdge(&graph, A, B);
AddEdge(&graph, A, D);
AddEdge(&graph, B, C);
AddEdge(&graph, D, C);
AddEdge(&graph, D, E);
AddEdge(&graph, E, F);
AddEdge(&graph, E, G);
ShowGraphEdgeInfo(&graph); //그래프의 간선 정보 출력
DFShowGraphVertex(&graph, A);
printf("\n");
DFShowGraphVertex(&graph, C);
printf("\n");
DFShowGraphVertex(&graph, E);
printf("\n");
DFShowGraphVertex(&graph, G);
printf("\n");
GraphDestroy(&graph); //그래프의 리소스 소멸
return 0;
}
/*
실행결과
A와 연결된 정점 : D B
B와 연결된 정점 : C A
C와 연결된 정점 : D B
D와 연결된 정점 : E C A
E와 연결된 정점 : G F D
F와 연결된 정점 : E
G와 연결된 정점 : E
A D E G F C B
C D E G F A B
E G F D C B A
G E F D C B A
*/위 실행결과를 보면 어디서 시작을 하든 모든 정점에 방문함을 알 수 있습니다.
'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글
| Chapter 14. 최소 비용 신장 트리 (0) | 2021.03.29 |
|---|---|
| Chapter 14. 그래프의 탐색 (3) (0) | 2021.03.29 |
| 연습문제 14. 01 DFS의 탐색 과정 (0) | 2021.03.27 |
| Chapter 14. 그래프의 탐색 (0) | 2021.03.27 |
| Chapter 14. 인접 리스트 기반의 그래프 구현 (0) | 2021.03.27 |