<그래프의 탐색>
[그래프의 탐색에 들어가기에 앞서]
연결 리스트나 배열과 같은 선형 자료구조에서는 탐색해야 할 방향이 정해져있다.
그래서 탐색과 조회를 진행하는 것이 어렵지 않았다.
트리와 같은 비선형 자료구조는 노드의 연결 방향이 일정하지 않기 때문에 탐색을 진행하는 것이 비교적 어렵다.
그렇지만 이진 탐색 트리는 노드가 연결되는 규칙이 있었기 때문에 비교적 간단한 편이었다.
말 그대로 '탐색'을 고려해서 만들어진 트리이기 때문이다.
그런데 그래프에서의 탐색은 어떻게 해야할까?
지금까지 학습했던 자료구조들 중에서 탐색 과정이 꽤 복잡한 편이다.
적어도 연결 리스트나 배열같은 선형 자료구조도 그렇고, 이진 탐색 트리도 그랬듯 '틀'이 있었다.
정형화된 구조가 있었기 때문에 탐색을 어떻게 할 것인가를 정의할 수 있었지만 그래프는 그렇지 않다.
그래프는 정점이나 간선의 갯수가 모두 다르고, 정형화된 틀이 없기 때문이다.
그래서 그래프에서 탐색은 특정 데이터를 찾는 것이 목적이 아니다.
'모든 정점을 어떻게 돌아야 하는가'가 핵심이다.
그래서 그래프의 탐색을 위한 별도의 알고리즘이 두 가지가 있다.
1) 깊이 우선 탐색 (Depth First Search, DFS)
2) 너비 우선 탐색 (Breadth First Search, BFS)
위의 두 알고리즘이 그래프의 탐색에서 사용되는 알고리즘이다.
앞으로 둘은 DFS, BFS라고 하겠다.
[깊이 우선 탐색 (DFS)]
[깊이 우선 탐색의 원리]
깊이 우선 탐색에서의 '깊이'는 무엇을 기준으로 깊이라고 하는 것일까?
쉽게 생각하면 "탐색을 시작하는 정점에서부터 최대한 깊게 파고 들어간다"라고 생각하면 좋다.
우선 다음과 같은 그래프가 있다고 치자.
앞서 말했다시피, 모든 정점의 방문을 목적으로 하는 것이 그래프의 탐색이다.
탐색의 시작 위치는 '동수'에서부터 시작을 한다고 가정을 하자.
그리고 한 정점에서 다른 한 정점으로만 방문하고, 다른 정점에서도 동일하게 적용된다는 가정을 가지고 시작한다.
여기서 동수의 다음 방문 대상은 '지민'인지 '지율'인지에 대한 고민을 할 수도 있다.
보다 일반화를 하면 "연결된 정점이 둘 이상이면 어느 쪽 정점을 먼저 방문해야 하는가"에 대한 고민이 된다.
사실 어느쪽으로 가던 상관은 없다.
이는 실제 코드로 구현을 하면서 어느 쪽으로 우선 순위를 두는가에서 고려할 문제이다.
여기서는 '지민'에게 먼저 방문한다고 치자.
[동수 - 지민 - 민석 -정희 - 수정]까지 방문을 진행한 상황이다.
그리고 '수정'의 입장에서 다른 곳을 방문하려고 하는데 더 이상 새로 방문할 정점이 없다.
그래서 자신에게 방문했던 '정희'로 되돌아가게 된다.
그래서 '정희'로 되돌아오면 '정희' 역시 새로 방문할 정점이 더 없기 때문에 자신에게 방문했던 '민석'으로 돌아간다.
그리고 '민석'으로 돌아와서 아직 방문하지 않은 정점은 '지율'이다.
그래서 '지율'로 방문을 하게 된다.
'지율'까지 방문하게 되면 '지율'의 입장에서 새로 방문할 정점은 더 없다.
그래서 자신에게 방문했던 '민석'에게 돌아가고, '민석'도 새로 방문할 정점이 없으므로 '지민'으로 돌아간다.
마찬가지로 '지민'도 새로 방문할 정점이 더 없기 때문에 '동수'로 돌아간다.
마지막으로 '동수' 역시 새로 방문할 정점이 없기 때문에 탐색은 종료가 된다.
이처럼 DFS는 처음 시작한 정점에서 시작해서 시작한 정점으로 돌아오면 끝이 난다.
지금까지 DFS의 원리를 정리하였고, 이 과정의 핵심은 세 가지이다.
1) 한 사람(정점)에만 방문을 한다.
2) 방문할 사람(정점)이 없으면 자신에게 방문한 사람(이전 정점)에게 이를 알린다.
3) 처음 방문을 시작한 사람(정점)의 위치에서 방문은 끝이 난다 (탐색 완료).
[너비 우선 탐색 (BFS)]
[너비 우선 탐색의 원리]
이전의 DFS가 한 사람(정점)에만 방문을 하는 방식이라면, BFS는 자신과 연결된 모든 사람(정점)에 방문을 하는 방식이다.
너비 우선 탐색에서의 '너비'는 '폭'이라고도 한다.
그렇다면 무엇을 기준으로 폭이라고 하는 것일까?
쉽게 생각하면 "한 사람(정점)을 기준으로 방문이 가능한 정점의 수(폭)"라고 생각하면 좋다.
DFS는 깊이를 우선시 하는 방식이었다면 BFS는 '폭'을 우선시하는, '폭을 넓혀가는 방식'이다.
마찬가지로 위와 비슷한 그래프를 예로 들어 원리를 설명하고자 한다.
탐색의 시작 위치는 '지율'에서부터 시작을 한다.
여기서는 '지율'이 방문할 수 있는 '동수'와 '민석'에게 모두 방문을 한다.
그리고 DFS때와 마찬가지로 '동수'와 '민석' 중 누구에게 먼저 갈 것인지 고민을 할 수 있다.
일반화를 하면 "연결된 정점이 둘 이상이면 어느 쪽 정점을 먼저 방문해야 하는가"와 똑같은 고민이다.
DFS때와 마찬가지로 BFS에서도 어느쪽으로 가던 상관은 없다.
여기서는 '동수'에게 먼저 방문한 뒤에 '민석'에게 방문을 한다고 가정하자.
그렇게 되면 '지율'에서 '동수', '민석' 순으로 방문을 한 것이 된다.
그리고 '동수'와 '민석' 역시 다른 사람(정점)에 방문을 해야한다.
여기서는 먼저 방문한 곳이 '동수'이므로 '동수'가 주변 정점에 먼저 방문을 한다.
그래서 '동수'는 '지민'을 방문하게 된다.
그러면 그 다음에는 '지민'이 다른 정점을 방문해야 하는가?
아니다! 이전에 '동수', '민석' 순으로 방문을 했기 때문에 '민석'이 먼저 다른 정점에 방문을 해야한다.
'민석'은 '수정', '정희'를 방문하게 하게 된다.
그리고 이 시점에서 방문은 받았지만, 아직 다른 사람(정점)에 방문을 하지 않은 사람을 정리해보자.
'지민', '수정', '정희' 이 세 사람(정점)이 된다.
그런데 여기서 '지민'과 '수정'의 주변 정점은 이미 방문을 완료한 상태이므로 둘은 더 이상 방문을 할 필요가 없다.
그래서 마지막으로 남은 '정희'가 '명석'을 방문한다.
'정희'가 '명석'을 방문하게 되고, '명석'은 방문을 받은 상황이다.
그리고 '명석'은 다른 정점을 방문할 기회를 갖게 된다.
하지만 더 이상 방문할 정점이 없으므로 탐색은 종료된다.
이처럼 BFS는 처음 시작한 정점에서 시작해서 더 이상 방문할 정점이 없으면 끝이 난다.
지금까지 BFS의 원리를 정리하였고, 이 과정의 핵심은 다음과 같다.
1) 자신과 연결된 사람(정점) 모두에게 방문을 한다.
2) 방문을 받은 사람(정점)은 다른 사람(정점)을 방문할 기회를 얻게 된다.
그리고 그 기회는 순서대로 진행되어야 한다.
3) 마지막으로 방문을 받은 사람(정점)이 더 이상 방문할 정점이 없으면 탐색이 완료된다.
[DFS의 구현]
[DFS의 구현 모델]
실제로 구현하기에 앞서 사용될 자료구조들이 있다.
1) 스택: 경로 정보의 추적을 목적으로 사용
2) 배열: 방문 정보의 기록을 목적으로 사용
이 둘이 왜 사용되는지 이전의 예시를 기준으로 설명하고자 한다.
현재 시작점은 '동수'를 시작으로 하고 있다.
그래서 배열에는 '동수'를 방문했다고 기록을 한 상태에서 시작한다.
'동수'에서 '지민'으로 이동한 상황이다.
여기서 중요한 부분은 바로 이것이다.
"'동수'를 떠나서 '지민'에게 방문할 때, '동수'를 스택에 저장한다."
이처럼 방문한 정점을 떠날 때에는 떠나는 정점의 정보를 스택에 쌓아야 한다.
이후 수정까지 진행한 상황이라고 치면 아래의 그림과 같이 된다.
현재 '수정'까지 방문이 된 상태이고, 지나온 경로의 순서대로 스택에 정점들이 저장된 상황이다.
그리고 '수정'은 더 이상 방문할 정점이 없기 때문에 이전 정점으로 되돌아가야 한다.
이처럼 DFS에서는 갔던 길을 되돌아오는 상황이 발생하게 된다.
그래서 스택이 필요한 것이다.
자신과 연결된 정점들이 모두 방문을 완료한 상태이므로 자신을 방문했던 정점으로 돌아간다.
그 정점으로 돌아가기 위해서 스택에서 POP을 수행하면 해당 정점이 바로 이전 정점이 된다.
그리고 '정희'도 마찬가지로 자신과 연결된 모든 정점의 방문이 완료된 상태이므로 '민석'으로 돌아가면 된다.
그래서 '민석' 정점까지 돌아온 상황이다.
그리고 현재 상황에서 '민석'은 '지율'에 방문할 수 있다.
'민석'은 '지율'을 방문하게 되고 스택에는 다시 '민석'이 들어가게 된다.
여기서 주목할 점은 '민석'이 다시 스택에 들어간 것이다.
'민석'은 이전에 방문이 이뤄졌다.
하지만 방문 여부와 상관 없이 해당 정점을 떠나 다른 정점을 방문하면 그 정보는 스택에 저장된다는 것이다.
'지율'까지 방문이 완료되었고, 더 이상 방문할 정점은 없는 상황이다.
그래서 스택에 있는 것들을 하나씩 POP하면서 되돌아가면 시작점인 '동수'로 돌아오게 된다.
이처럼 DFS 알고리즘의 구현에 있어 정점의 이동에 가장 중요한 것은 '스택'이다.
[구현]
이전에 구현했던 스택과 리스트, 그래프의 코드를 다시 활용하고자 한다.
여기서 스택과 관련된 코드는 아래의 링크에 있는 연결 리스트 기반의 스택을 써도 된다.
https://sevenshards.tistory.com/5
[자료구조, C] 리스트 기반 스택을 이용한 계산기 구현
[ListBaseStack.h] /* * 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3 * 파일명: ListBaseStack.h * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-23 * 이전 버전 작성 일자: * 버전 내용: 중위 표기
sevenshards.tistory.com
별도로 코드를 수정하기가 귀찮을 수도 있으므로, 배열 기반의 스택 코드를 같이 수록하겠다.
[ArrayBaseStack.h]
/*
* 선형 자료구조 - 스택 (배열 기반)
* 파일명: ArrayBaseStack.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-03
* 이전 버전 작성 일자:
* 버전 내용: 간단한 배열 기반 스택 구현
* 이전 버전 내용:
*/
#ifndef __ARRAY_BASE_STACK_H__
#define __ARRAY_BASE_STACK_H__
#define TRUE 1
#define FALSE 0
#define STACK_LEN 100
typedef int Data; // 편의상 int를 Data로, 다른 데이터 타입 넣어서 메인 함수 바꿔가면서 하면 됨
typedef struct _arrayStack
{
Data stackArr[STACK_LEN]; // 배열을 기반으로 한 스택이므로 배열 사용, 현재 기준 int형 배열
int topIndex; // 현재 스택의 데이터가 저장된 위치를 기억하기 위해 사용하는 top 변수, 여기서는 topindex라고 하였음
} ArrayStack;
typedef ArrayStack Stack; // 편의상 ArrayStack이라고 쓰기 뭐하니 별칭으로 Stack이라고 함
void StackInit(Stack* pstack); // 스택 초기화
int SisEmpty(Stack* pstack); // 스택이 비어있는가 아닌가 확인
void SPush(Stack* pstack, Data data); // 스택에 데이터를 저장 (일반적인 stack의 push연산)
Data SPop(Stack* pstack); // 스택에 있는 데이터를 제거, 동시에 값을 반환 (일반적인 stack의 pop연산)
Data SPeek(Stack* pstack); // 스택에 마지막으로 들어가있는 값을 확인, 제거는 하지 않음 (일반적인 stack의 peek연산)
#endif
[ArrayBaseStack.c]
/*
* 선형 자료구조 - 스택 (배열 기반)
* 파일명: ArrayBaseStack.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-03
* 이전 버전 작성 일자:
* 버전 내용: 간단한 배열 기반 스택 구현
* 이전 버전 내용:
*/
#include <stdio.h>
#include <stdlib.h>
#include "ArrayBaseStack.h"
void StackInit(Stack* pstack) // 스택 초기화
{
pstack->topIndex = -1; // 배열이므로 현재 가리키는 인덱스는 -1로.
}
int SisEmpty(Stack* pstack) // 스택이 비어있는가 아닌가 확인
{
if (pstack->topIndex == -1) // 스택이 비어있다면
return TRUE;
else
return FALSE;
}
void SPush(Stack* pstack, Data data) // 스택에 데이터를 저장 (일반적인 stack의 push연산)
{
pstack->topIndex += 1; // 인덱스를 하나 증가시키고
pstack->stackArr[pstack->topIndex] = data; // 스택(배열)에 데이터를 저장
}
Data SPop(Stack* pstack) // 스택에 있는 데이터를 제거, 동시에 값을 반환 (일반적인 stack의 pop연산)
{
int rIdx; // 지워질 인덱스 값, 왜 처음부터 초기화를 안했는가?
if (SisEmpty(pstack)) // 먼저 스택이 비어있는가 아닌가를 확인
{
printf("Stack is Empty!"); // 비어있다면 다음을 화면에 출력하고
exit(-1); // 종료, 참고로 exit 함수는 stdlib.h에 있다
}
rIdx = pstack->topIndex; // 지워질 인덱스 값을 현재 스택의 topIndex 값을 주고
pstack->topIndex -= 1; // 인덱스 값을 하나 감소시킨다.
return pstack->stackArr[rIdx]; // 현재 지워질 인덱스가 가진 값을 반환하며 종료.
}
Data SPeek(Stack* pstack) // 스택에 마지막으로 들어가있는 값을 확인, 제거는 하지 않음 (일반적인 stack의 peek연산)
{
// pop 연산과 거의 동일함, 하지만 스택의 마지막 데이터는 지우지 않는 것이 포인트.
if (SisEmpty(pstack)) // 먼저 스택이 비어있는가 아닌가를 확인
{
printf("Stack is Empty!"); // 비어있다면 다음을 화면에 출력하고
exit(-1); // 종료, 참고로 exit 함수는 stdlib.h에 있다
}
return pstack->stackArr[pstack->topIndex]; // 현재 topIndex가 가진 값을 반환하며 종료.
}[ALGraphDFS.h]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: ALGraphDFS.h
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현
* 이전 버전 내용: 간단한 인접 리스트 기반 무방향 그래프 구현 (이전 파일명: ALGraph.h)
*/
#ifndef __ALGRAPH_H__
#define __ALGRAPH_H__
// 인접 리스트 기반으로 구현을 하므로 단일 연결 리스트를 사용
#include "SingleLinkedList.h"
// 정점의 이름을 상수화
// A는 0으로 초기화되어 1씩 증가
enum { A, B, C, D, E, F, G, H, I, J };
// 무방향 인접 리스트(Undirected Adjacent List) 그래프 구조체
typedef struct _ual
{
int numVertex; // 정점의 수
int numEdge; // 간선의 수
List* adjList; // 간선의 정보(어떤 정점과 연결되었는지에 대한 정보)
int* visitInfo; // 방문 정보(정점 방문 여부 정보) -> 방문 정보를 기록하기 위한 배열
} ALGraph;
// 그래프 자료구조의 ADT
// 초기화
void GraphInit(ALGraph* pg, int nv);
// 그래프의 리소스 해제 (삭제)
void GraphDestroy(ALGraph* pg);
// 간선 추가(연결)
void AddEdge(ALGraph* pg, int fromV, int toV);
// 간선 정보 출력
void ShowGraphEdgeInfo(ALGraph* pg);
// 깊이 우선 탐색(DFS) 기반 그래프의 정점 정보 출력
void DFSShowGraphVertex(ALGraph* pg, int startV);
#endif
[ALGraphDFS.c]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: ALGraphDFS.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현
* 이전 버전 내용: 간단한 인접 리스트 기반 무방향 그래프 구현 (이전 파일명: ALGraph.c)
*/
#include <stdio.h>
#include <stdlib.h>
#include "ALGraphDFS.h"
// 인접 리스트 기반으로 구현을 하므로 단일 연결 리스트를 사용
#include "SingleLinkedList.h"
// DFS 구현에 사용에 스택을 사용
#include "ArrayBaseStack.h"
// 저자는 출력의 형태를 좋게 하기 위해서 정렬 기준(우선순위 판별)을 넣었다.
// 사실 넣어도 그만이고 안넣어도 그만인 부분이다.
// 혹시라도 이 미흡한 코드를 보고 따라한다면 이 함수는 빼도 된다.
int WhoisPrecede(int d1, int d2)
{
// 오름차순 정렬
if (d1 < d2)
return 0; // d1의 우선 순위가 앞선다면 0을
else
return 1; // d2의 우선 순위가 앞서거나 같다면 1을
}
// 그래프 자료구조의 ADT
// 초기화
void GraphInit(ALGraph* pg, int nv)
{
pg->numVertex = nv; // 입력받은 nv는 정점의 수
pg->numEdge = 0; // 초기화시 간선의 수는 0
pg->adjList = (List*)malloc(sizeof(List) * pg->numVertex); // 정점의 수만큼 메모리 할당
pg->visitInfo = (int*)malloc(sizeof(int) * pg->numVertex); // 정점의 수만큼 메모리 할당
memset(pg->visitInfo, 0, sizeof(int) * pg->numVertex); // 배열의 모든 요소를 0으로 초기화
int i; // 반복문에서 사용할 변수 i
for (i = 0; i < nv; i++)
{
ListInit(&(pg->adjList[i])); // 정점의 수만큼 List 초기화
SetSortRule(&(pg->adjList[i]), WhoisPrecede); // 각 List에 정렬 기준 함수 등록 -> 정렬 기준을 안쓴다면 빼도 됨
}
}
// 그래프의 리소스 해제 (삭제)
void GraphDestroy(ALGraph* pg)
{
if (pg->adjList != NULL) // NULL이 아니라면 할당이 된 상황
free(pg->adjList); // 할당 해제
if (pg->visitInfo != NULL) // NULL이 아니라면 할당이 된 상황
free(pg->visitInfo); // 할당 해제
}
// 간선 추가(연결)
void AddEdge(ALGraph* pg, int fromV, int toV)
{
LInsert(&(pg->adjList[fromV]), toV); // from->to
LInsert(&(pg->adjList[toV]), fromV); // to->from
pg->numEdge += 1; // 간선 갯수 추가
}
// 간선 정보 출력
void ShowGraphEdgeInfo(ALGraph* pg)
{
int i; // 반복문에 사용할 변수 i
int vertex; // 정점
for (i = 0; i < pg->numVertex; i++)
{
printf("%c와 연결된 정점: ", i + 65); // 아스키 코드 65가 'A'
if (LFirst(&(pg->adjList[i]), &vertex))
{
printf("%c ", vertex += 65);
while (LNext(&(pg->adjList[i]), &vertex))
printf("%c ", vertex += 65);
}
printf("\n");
}
}
// 정점의 방문을 진행하는 함수
// 두 번째 인자로 전달된 이름의 정점에 방문을 진행
int VisitVertex(ALGraph* pg, int visitV)
{
if (pg->visitInfo[visitV] == 0) // 아직 방문하지 않았다면
{
pg->visitInfo[visitV] = 1; // 방문한 것으로 바꾼다. 0이면 아직 안들른 것, 1이면 들른것. flag 개념
printf("%c ", visitV + 65); // 방문한 정점의 이름을 출력
return TRUE; // 방문을 했으므로 TRUE 반환
}
return FALSE; // 방문을 못했으므로 FALSE 반환
}
// 깊이 우선 탐색(DFS) 기반 그래프의 정점 정보 출력
void DFSShowGraphVertex(ALGraph* pg, int startV)
{
Stack stack; // 경로 정보의 추적에 사용할 스택
int visitV = startV; // 시작 정점으로 방문한 정점을 초기화
int nextV; // 다음에 방문할 정점
StackInit(&stack); // 스택의 초기화
VisitVertex(pg, visitV); // 시작 정점을 방문
// 여기서 스택에 넣는 부분은 사실 필요가 없다.
// 카페에서 저자의 답변을 확인해본 결과는 다음과 같았다.
// VisitVertex와 SPush는 쌍을 이루는 것이 좋고, 가독성 차원에서 놔둔 것이라고.
// 실제로 디버깅을 하면 스택에는 시작 정점이 두 번 들어가는 것이 확인된다.
// 결론은 주석 처리해도 문제가 되지 않는다.
// SPush(&stack, visitV); // 시작 정점의 정보를 스택에 넣는다.
// visitV에 담긴 정점과 연결된 정점의 방문을 시도하기 위한 반복문
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) // 현재 정점과 연결된 간선이 있다면
{
// 현재 visitV와 연결된 정점의 정보는 nextV에 담긴 상태
int visitFlag = FALSE; // 방문 flag를 FALSE로 한다.
if (VisitVertex(pg, nextV) == TRUE) // 다음 정점 방문에 성공했다면
{
SPush(&stack, visitV); // visitV에 담긴 정점의 정보를 스택에 넣는다.
visitV = nextV; // 그리고 다음에 방문할 정점의 정보로 변경
visitFlag = TRUE; // 방문에 성공했으므로 TRUE로 변경
}
else // 방문에 성공하지 못했다면
{
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE) // 다른 방문할 정점을 찾는다.
{
if (VisitVertex(pg, nextV) == TRUE) // 정점 방문에 성공했다면
{
SPush(&stack, visitV); // visitV에 담긴 정점의 정보를 스택에 넣는다.
visitV = nextV; // 그리고 다음에 방문할 정점의 정보로 변경
visitFlag = TRUE; // 방문에 성공했으므로 TRUE로 변경
break; // 방문에 성공했으므로 반복 중단
}
}
}
if (visitFlag == FALSE) // 추가로 방문한 정점이 하나도 없다면
{
if (SisEmpty(&stack)) // 스택이 비었다면 탐색이 종료된 것
break;
else // 스택이 비어있는 상태가 아니라면
visitV = SPop(&stack); // 이전의 경로로 돌아가기 위해 스택에서 꺼낸다.
}
}
// 이후 탐색을 다시 수행할 수 있으므로 배열의 정보를 초기화
memset(pg->visitInfo, 0, sizeof(int) * pg->numVertex); // 배열의 모든 요소를 0으로 초기화
}
[DFSMain.c]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: DFSMain.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현
* 이전 버전 내용: 간단한 인접 리스트 기반 무방향 그래프 구현 (이전 파일명: ALGraphMain.c)
*/
#include <stdio.h>
#include "ALGraphDFS.h"
int main()
{
ALGraph graph; // 그래프 생성
GraphInit(&graph, 7); // 그래프 초기화
// 정점 연결 (간선 추가)
AddEdge(&graph, A, B);
AddEdge(&graph, A, D);
AddEdge(&graph, B, C);
AddEdge(&graph, C, D);
AddEdge(&graph, D, E);
AddEdge(&graph, E, F);
AddEdge(&graph, E, G);
ShowGraphEdgeInfo(&graph);
// A, C, E, G를 시작으로 DFS 탐색
DFSShowGraphVertex(&graph, A);
printf("\n");
DFSShowGraphVertex(&graph, C);
printf("\n");
DFSShowGraphVertex(&graph, E);
printf("\n");
DFSShowGraphVertex(&graph, G);
printf("\n");
GraphDestroy(&graph);
return 0;
}
소스 코드에 주석을 글이 너무 길어질 것 같아서 소스코드에 주석을 다는 형식으로 정리를 하였다.
그래프에서 사용했던 ALGraph.h와 ALGraph.c는 ALGraphDFS.h와 ALGraphDFS.c로 바꾸었다.
그리고 DFS 알고리즘에 대한 부분을 추가하였다.
https://sevenshards.tistory.com/30
[자료구조, C] 그래프(Graph)의 이해와 종류
[그래프에 들어가기에 앞서] 그래프 역시 자료구조이며, 비선형 자료구조에 해당한다. 그리고 트리 때와도 마찬가지로 데이터의 저장보다는 '표현'을 하는데 중점적이다. 실제로 그래프라는 자
sevenshards.tistory.com
[BFS의 구현]
[BFS의 구현 모델]
DFS와 마찬가지로 구현하기에 앞서 사용될 자료구조들이 있다.
1) 큐: 방문 차례의 기록을 목적으로 사용
2) 배열: 방문 정보의 기록을 목적으로 사용
DFS와 달리 BFS는 큐를 사용한다.
큐를 사용한 이유도 이전 예시를 되짚어가면서 확인해보자.
현재 시작점은 '지율'이다.
그래서 배열에는 '지율'의 방문 정보를 기록한다.
그리고 '지율'에서 '동수', '민석' 순으로 방문을 한다.
여기서 주목할 부분은 '동수'와 '민석'은 방문을 받았지만 다른 정점에 방문을 한 상태가 아니다.
그래서 방문할 차례를 저장하기 위해 큐에 저장하게 된다.
이후 큐에서 데이터를 하나 꺼내면 '동수'가 나오게 된다.
큐에서 나온 '동수'를 중심으로 방문 가능한 다른 정점에 방문을 하고, 큐에는 '지민'이 들어가게 된다.
그 다음은 큐에서 '민석'이 나오게 되고, '민석'을 중심으로 방문 가능한 다른 정점에 방문을 한다.
그리고 마찬가지로 방문을 받은 정점들을 큐에 저장한다.
이어서 큐에 있던 '지민', '수정' 이 나오게 되는데, 방문 가능한 다른 정점이 없다.
그래서 '정희'까지 큐에서 꺼내면 다음에 방문할 정점인 '명석'을 방문하게 된다.
그리고 마지막으로 '명석'이 큐에 들어가게 된다.
이후 큐에서 '명석'을 꺼낸 이후 방문 가능한 다른 정점이 없다면 탐색은 종료된다.
즉, 마지막에 큐가 비어있는 상태라면 탐색은 종료가 된 것이다.
DFS 알고리즘에서 핵심이 되었던 것이 스택이라면, BFS에서는 큐가 핵심이 된다.
[구현]
이전에 구현했던 DFS 알고리즘을 추가로 구현한 그래프의 코드를 다시 활용하고자 한다.
그리고 추가가 되는 것은 큐를 추가하는 것과 BFS 알고리즘을 추가하는 정도다.
여기서 큐는 배열 기반의 원형 큐를 써도 되고, 연결 리스트 기반의 큐를 써도 상관이 없다.
해당 글에서는 배열 기반의 원형 큐를 수록할 것이다.
별도로 연결 리스트 기반의 큐를 쓰고 싶다 하는 분은 깃허브에 코드가 있으니 그 코드를 쓰셔도 무방하다.
https://github.com/sevenshards00/DataStructure_C
GitHub - sevenshards00/DataStructure_C: 자료구조와 알고리즘 공부 모음 (C언어 기반)
자료구조와 알고리즘 공부 모음 (C언어 기반). Contribute to sevenshards00/DataStructure_C development by creating an account on GitHub.
github.com
[CircularQueue.h]
/*
* 선형 자료구조 - Queue (배열 기반, 원형 큐)
* 파일명: CircularQueue.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-05
* 이전 버전 작성 일자:
* 버전 내용: 배열 기반의 원형(Circular) Queue 구현
* 이전 버전 내용:
*/
#ifndef __C_QUEUE_H__
#define __C_QUEUE_H__
#define TRUE 1
#define FALSE 0
#define QUE_LEN 100 // 큐의 길이, 배열이므로 매크로로 100으로 고정
typedef int Data; // 편의상 받는 데이터는 int로 했고 Data로 지칭, 다른 데이터로 바꾼다면 여길 바꾸면 된다
typedef struct _circularqueue // 배열 기반 원형 큐의 구조체, 배열과 front, rear 셋으로 구성
{
Data arr[QUE_LEN]; // 현재 큐를 구성할 배열
int front; // front
int rear; // rear
} CQueue;
typedef CQueue Queue; // 편의상 CQueue를 Queue로 별칭 붙여 사용
void QueueInit(Queue* pq); // Queue 초기화
int QisEmpty(Queue* pq); // Queue가 비었는가 확인
void QEnqueue(Queue* pq, Data data); // Queue에 데이터 삽입
Data QDequeue(Queue* pq); // Queue에 들어있는 데이터 반환 및 삭제
Data QPeek(Queue* pq); // 현재 Front가 가리키는 값 반환
#endif
[CircularQueue.c]
/*
* 선형 자료구조 - Queue (배열 기반, 원형 큐)
* 파일명: CircularQueue.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-05
* 이전 버전 작성 일자:
* 버전 내용: 배열 기반의 원형(Circular) Queue 구현
* 이전 버전 내용:
*/
#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"
void QueueInit(Queue* pq) // Queue 초기화
{
pq->front = 0; // front는 0을 가리키고
pq->rear = 0; // rear도 0을 가리킨다
}
int QisEmpty(Queue* pq) // Queue가 비었는가 확인
{
if (pq->front == pq->rear) // front와 rear가 똑같다면
return TRUE; // 비어있으므로 TRUE 반환
else
return FALSE; // 비어있지 않다면 FALSE 반환
}
// 배열 기반 원형 큐에서만 쓰이는 함수
// 배열 내에서 front와 rear가 계속 돌아야하므로 사용한다.
int NextPosIdx(int pos)
{
// 실제 배열 인덱스의 끝은 QUE_LEN-1
// 그리고 현재 인덱스가 끝을 가리킨다면
// 다시 0부터 돌려보내기 위함
//
if (pos == QUE_LEN - 1) // 현재 인덱스가 끝을 가리킨다면
return 0; // 0으로 돌려보낸다
else // 그게 아니라면
return pos + 1; // 다음 인덱스를 가리키게 한다
}
void QEnqueue(Queue* pq, Data data) // Queue에 데이터 삽입
{
if (NextPosIdx(pq->rear) == pq->front) // rear의 다음이 front라면? Queue가 꽉 찼다는 것
{
printf("Queue Fulled\n");
exit(-1); // 더 이상 채울 수 없으므로 종료
}
//그게 아니라면
pq->rear = NextPosIdx(pq->rear); // rear를 한 칸 앞으로 이동하고
pq->arr[pq->rear] = data; // 데이터를 넣는다.
}
Data QDequeue(Queue* pq) // Queue에 들어있는 데이터 반환 및 삭제
{
if (QisEmpty(pq)) // Queue가 비었다면
{
printf("Queue is Empty\n");
exit(-1); // 수행 못하므로 종료
}
// 그게 아니라면
pq->front = NextPosIdx(pq->front); // front를 다음 인덱스로 바꾸고
return pq->arr[pq->front]; // 현재 front가 가리키는 인덱스의 값을 반환
}
Data QPeek(Queue* pq) // 현재 Front가 가리키는 값 반환
{
if (QisEmpty(pq)) // Queue가 비었다면
{
printf("Queue is Empty\n");
exit(-1); // 수행 못하므로 종료
}
// 그게 아니라면
return pq->arr[NextPosIdx(pq->front)]; // 현재 front가 가리키는 인덱스의 값을 반환
}
[ALGraphBFS.h]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: ALGraphBFS.h
* 파일 버전: 0.3
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 너비 우선 탐색(Breadth First Search) 추가 구현
* 이전 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현 (이전 파일명: ALGraphDFS.h)
*/
#ifndef __ALGRAPH_H__
#define __ALGRAPH_H__
// 인접 리스트 기반으로 구현을 하므로 단일 연결 리스트를 사용
#include "SingleLinkedList.h"
// 정점의 이름을 상수화
// A는 0으로 초기화되어 1씩 증가
enum { A, B, C, D, E, F, G, H, I, J };
// 무방향 인접 리스트(Undirected Adjacent List) 그래프 구조체
typedef struct _ual
{
int numVertex; // 정점의 수
int numEdge; // 간선의 수
List* adjList; // 간선의 정보(어떤 정점과 연결되었는지에 대한 정보)
int* visitInfo; // 방문 정보(정점 방문 여부 정보) -> 방문 정보를 기록하기 위한 배열
} ALGraph;
// 그래프 자료구조의 ADT
// 초기화
void GraphInit(ALGraph* pg, int nv);
// 그래프의 리소스 해제 (삭제)
void GraphDestroy(ALGraph* pg);
// 간선 추가(연결)
void AddEdge(ALGraph* pg, int fromV, int toV);
// 간선 정보 출력
void ShowGraphEdgeInfo(ALGraph* pg);
// 깊이 우선 탐색(DFS) 기반 그래프의 정점 정보 출력
void DFSShowGraphVertex(ALGraph* pg, int startV);
// 너비 우선 탐색(BFS) 기반 그래프의 정점 정보 출력
void BFSShowGraphVertex(ALGraph* pg, int startV);
#endif[ALGraphBFS.c]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: ALGraphBFS.c
* 파일 버전: 0.3
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 너비 우선 탐색(Breadth First Search) 추가 구현
* 이전 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현 (이전 파일명: ALGraphDFS.c)
*/
#include <stdio.h>
#include <stdlib.h>
#include "ALGraphBFS.h"
// 인접 리스트 기반으로 구현을 하므로 단일 연결 리스트를 사용
#include "SingleLinkedList.h"
// DFS 구현에 스택을 사용
#include "ArrayBaseStack.h"
// BFS 구현에 큐를 사용
#include "CircularQueue.h"
// 저자는 출력의 형태를 좋게 하기 위해서 정렬 기준(우선순위 판별)을 넣었다.
// 사실 넣어도 그만이고 안넣어도 그만인 부분이다.
// 혹시라도 이 미흡한 코드를 보고 따라한다면 이 함수는 빼도 된다.
int WhoisPrecede(int d1, int d2)
{
// 오름차순 정렬
if (d1 < d2)
return 0; // d1의 우선 순위가 앞선다면 0을
else
return 1; // d2의 우선 순위가 앞서거나 같다면 1을
}
// 그래프 자료구조의 ADT
// 초기화
void GraphInit(ALGraph* pg, int nv)
{
pg->numVertex = nv; // 입력받은 nv는 정점의 수
pg->numEdge = 0; // 초기화시 간선의 수는 0
pg->adjList = (List*)malloc(sizeof(List) * pg->numVertex); // 정점의 수만큼 메모리 할당
pg->visitInfo = (int*)malloc(sizeof(int) * pg->numVertex); // 정점의 수만큼 메모리 할당
memset(pg->visitInfo, 0, sizeof(int) * pg->numVertex); // 배열의 모든 요소를 0으로 초기화
int i; // 반복문에서 사용할 변수 i
for (i = 0; i < nv; i++)
{
ListInit(&(pg->adjList[i])); // 정점의 수만큼 List 초기화
SetSortRule(&(pg->adjList[i]), WhoisPrecede); // 각 List에 정렬 기준 함수 등록 -> 정렬 기준을 안쓴다면 빼도 됨
}
}
// 그래프의 리소스 해제 (삭제)
void GraphDestroy(ALGraph* pg)
{
if (pg->adjList != NULL) // NULL이 아니라면 할당이 된 상황
free(pg->adjList); // 할당 해제
if (pg->visitInfo != NULL) // NULL이 아니라면 할당이 된 상황
free(pg->visitInfo); // 할당 해제
}
// 간선 추가(연결)
void AddEdge(ALGraph* pg, int fromV, int toV)
{
LInsert(&(pg->adjList[fromV]), toV); // from->to
LInsert(&(pg->adjList[toV]), fromV); // to->from
pg->numEdge += 1; // 간선 갯수 추가
}
// 간선 정보 출력
void ShowGraphEdgeInfo(ALGraph* pg)
{
int i; // 반복문에 사용할 변수 i
int vertex; // 정점
for (i = 0; i < pg->numVertex; i++)
{
printf("%c와 연결된 정점: ", i + 65); // 아스키 코드 65가 'A'
if (LFirst(&(pg->adjList[i]), &vertex))
{
printf("%c ", vertex += 65);
while (LNext(&(pg->adjList[i]), &vertex))
printf("%c ", vertex += 65);
}
printf("\n");
}
}
// 정점의 방문을 진행하는 함수
// 두 번째 인자로 전달된 이름의 정점에 방문을 진행
int VisitVertex(ALGraph* pg, int visitV)
{
if (pg->visitInfo[visitV] == 0) // 아직 방문하지 않았다면
{
pg->visitInfo[visitV] = 1; // 방문한 것으로 바꾼다. 0이면 아직 안들른 것, 1이면 들른것. flag 개념
printf("%c ", visitV + 65); // 방문한 정점의 이름을 출력
return TRUE; // 방문을 했으므로 TRUE 반환
}
return FALSE; // 방문을 못했으므로 FALSE 반환
}
// 깊이 우선 탐색(DFS) 기반 그래프의 정점 정보 출력
void DFSShowGraphVertex(ALGraph* pg, int startV)
{
Stack stack; // 경로 정보의 추적에 사용할 스택
int visitV = startV; // 시작 정점으로 방문한 정점을 초기화
int nextV; // 다음에 방문할 정점
StackInit(&stack); // 스택의 초기화
VisitVertex(pg, visitV); // 시작 정점을 방문
// 여기서 스택에 넣는 부분은 사실 필요가 없다.
// 카페에서 저자의 답변을 확인해본 결과는 다음과 같았다.
// VisitVertex와 SPush는 쌍을 이루는 것이 좋고, 가독성 차원에서 놔둔 것이라고.
// 실제로 디버깅을 하면 스택에는 시작 정점이 두 번 들어가는 것이 확인된다.
// 결론은 주석 처리해도 문제가 되지 않는다.
// SPush(&stack, visitV); // 시작 정점의 정보를 스택에 넣는다.
// visitV에 담긴 정점과 연결된 정점의 방문을 시도하기 위한 반복문
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) // 현재 정점과 연결된 간선이 있다면
{
// 현재 visitV와 연결된 정점의 정보는 nextV에 담긴 상태
int visitFlag = FALSE; // 방문 flag를 FALSE로 한다.
if (VisitVertex(pg, nextV) == TRUE) // 다음 정점 방문에 성공했다면
{
SPush(&stack, visitV); // visitV에 담긴 정점의 정보를 스택에 넣는다.
visitV = nextV; // 그리고 다음에 방문할 정점의 정보로 변경
visitFlag = TRUE; // 방문에 성공했으므로 TRUE로 변경
}
else // 방문에 성공하지 못했다면
{
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE) // 다른 방문할 정점을 찾는다.
{
if (VisitVertex(pg, nextV) == TRUE) // 정점 방문에 성공했다면
{
SPush(&stack, visitV); // visitV에 담긴 정점의 정보를 스택에 넣는다.
visitV = nextV; // 그리고 다음에 방문할 정점의 정보로 변경
visitFlag = TRUE; // 방문에 성공했으므로 TRUE로 변경
break; // 방문에 성공했으므로 반복 중단
}
}
}
if (visitFlag == FALSE) // 추가로 방문한 정점이 하나도 없다면
{
if (SisEmpty(&stack)) // 스택이 비었다면 탐색이 종료된 것
break;
else // 스택이 비어있는 상태가 아니라면
visitV = SPop(&stack); // 이전의 경로로 돌아가기 위해 스택에서 꺼낸다.
}
}
// 이후 탐색을 다시 수행할 수 있으므로 배열의 정보를 초기화
memset(pg->visitInfo, 0, sizeof(int) * pg->numVertex); // 배열의 모든 요소를 0으로 초기화
}
// 너비 우선 탐색(BFS) 기반 그래프의 정점 정보 출력
void BFSShowGraphVertex(ALGraph* pg, int startV)
{
Queue queue; // 방문할 차례(순서)의 기록을 목적으로 큐 생성
int visitV = startV; // 시작 정점으로 방문할 정점을 초기화
int nextV; // 다음에 방문할 정점
QueueInit(&queue); // 큐 초기화
VisitVertex(pg, visitV); // 시작 정점 방문
// visitV에 담긴 정점과 연결된 정점의 모든 정점에 방문하기 위한 반복문
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) // 현재 정점과 연결된 간선이 있다면
{
// 현재 visitV와 연결된 정점의 정보는 nextV에 담긴 상태
if (VisitVertex(pg, nextV) == TRUE) // 다음 정점 방문에 성공했다면
QEnqueue(&queue, nextV); // nextV에 방문했으므로 큐에 저장
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE) // 이어서 방문할 정점을 찾는다.
{
if (VisitVertex(pg, nextV) == TRUE) // 정점 방문에 성공했다면
QEnqueue(&queue, nextV); // nextV에 방문했으므로 큐에 저장
}
if (QisEmpty(&queue)) // 큐가 비었다면 탐색이 종료된 것
break;
else // 큐가 비어있는 상태가 아니라면
visitV = QDequeue(&queue); // 큐에서 하나 정점을 하나 꺼내어 다시 반복문 수행.
}
// 이후 탐색을 다시 수행할 수 있으므로 배열의 정보를 초기화
memset(pg->visitInfo, 0, sizeof(int) * pg->numVertex); // 배열의 모든 요소를 0으로 초기화
}[BFSMain.c]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: ALGraphBFS.h
* 파일 버전: 0.3
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 너비 우선 탐색(Breadth First Search) 추가 구현
* 이전 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현 (이전 파일명: DFSMain.c)
*/
#include <stdio.h>
#include "ALGraphBFS.h"
int main()
{
ALGraph graph; // 그래프 생성
GraphInit(&graph, 7); // 그래프 초기화
// 정점 연결 (간선 추가)
AddEdge(&graph, A, B);
AddEdge(&graph, A, D);
AddEdge(&graph, B, C);
AddEdge(&graph, C, D);
AddEdge(&graph, D, E);
AddEdge(&graph, E, F);
AddEdge(&graph, E, G);
ShowGraphEdgeInfo(&graph);
printf("\n");
// A, C, E, G를 시작으로 DFS 탐색
printf("DFS 탐색\n");
DFSShowGraphVertex(&graph, A);
printf("\n");
DFSShowGraphVertex(&graph, C);
printf("\n");
DFSShowGraphVertex(&graph, E);
printf("\n");
DFSShowGraphVertex(&graph, G);
printf("\n\n");
printf("BFS 탐색\n");
// A, C, E, G를 시작으로 BFS 탐색
BFSShowGraphVertex(&graph, A);
printf("\n");
BFSShowGraphVertex(&graph, C);
printf("\n");
BFSShowGraphVertex(&graph, E);
printf("\n");
BFSShowGraphVertex(&graph, G);
printf("\n\n");
GraphDestroy(&graph);
return 0;
}
그래프는 앞서 작성했던 ALGraphDFS.h와 ALGraphDFS.c를 ALGraphBFS.h, ALGraphBFS.c로 이름을 바꾸었다.
그리고 BFS 알고리즘과 관련된 함수가 추가로 구현을 하는 방식을 이용했다.
DFS때와 마찬가지로 글이 길어지지 않도록 코드에 주석을 충분히 달아두었다.
<그래프의 탐색>
[그래프의 탐색에 들어가기에 앞서]
연결 리스트나 배열과 같은 선형 자료구조에서는 탐색해야 할 방향이 정해져있다.
그래서 탐색과 조회를 진행하는 것이 어렵지 않았다.
트리와 같은 비선형 자료구조는 노드의 연결 방향이 일정하지 않기 때문에 탐색을 진행하는 것이 비교적 어렵다.
그렇지만 이진 탐색 트리는 노드가 연결되는 규칙이 있었기 때문에 비교적 간단한 편이었다.
말 그대로 '탐색'을 고려해서 만들어진 트리이기 때문이다.
그런데 그래프에서의 탐색은 어떻게 해야할까?
지금까지 학습했던 자료구조들 중에서 탐색 과정이 꽤 복잡한 편이다.
적어도 연결 리스트나 배열같은 선형 자료구조도 그렇고, 이진 탐색 트리도 그랬듯 '틀'이 있었다.
정형화된 구조가 있었기 때문에 탐색을 어떻게 할 것인가를 정의할 수 있었지만 그래프는 그렇지 않다.
그래프는 정점이나 간선의 갯수가 모두 다르고, 정형화된 틀이 없기 때문이다.
그래서 그래프에서 탐색은 특정 데이터를 찾는 것이 목적이 아니다.
'모든 정점을 어떻게 돌아야 하는가'가 핵심이다.
그래서 그래프의 탐색을 위한 별도의 알고리즘이 두 가지가 있다.
1) 깊이 우선 탐색 (Depth First Search, DFS)
2) 너비 우선 탐색 (Breadth First Search, BFS)
위의 두 알고리즘이 그래프의 탐색에서 사용되는 알고리즘이다.
앞으로 둘은 DFS, BFS라고 하겠다.
[깊이 우선 탐색 (DFS)]
[깊이 우선 탐색의 원리]
깊이 우선 탐색에서의 '깊이'는 무엇을 기준으로 깊이라고 하는 것일까?
쉽게 생각하면 "탐색을 시작하는 정점에서부터 최대한 깊게 파고 들어간다"라고 생각하면 좋다.
우선 다음과 같은 그래프가 있다고 치자.
앞서 말했다시피, 모든 정점의 방문을 목적으로 하는 것이 그래프의 탐색이다.
탐색의 시작 위치는 '동수'에서부터 시작을 한다고 가정을 하자.
그리고 한 정점에서 다른 한 정점으로만 방문하고, 다른 정점에서도 동일하게 적용된다는 가정을 가지고 시작한다.
여기서 동수의 다음 방문 대상은 '지민'인지 '지율'인지에 대한 고민을 할 수도 있다.
보다 일반화를 하면 "연결된 정점이 둘 이상이면 어느 쪽 정점을 먼저 방문해야 하는가"에 대한 고민이 된다.
사실 어느쪽으로 가던 상관은 없다.
이는 실제 코드로 구현을 하면서 어느 쪽으로 우선 순위를 두는가에서 고려할 문제이다.
여기서는 '지민'에게 먼저 방문한다고 치자.
[동수 - 지민 - 민석 -정희 - 수정]까지 방문을 진행한 상황이다.
그리고 '수정'의 입장에서 다른 곳을 방문하려고 하는데 더 이상 새로 방문할 정점이 없다.
그래서 자신에게 방문했던 '정희'로 되돌아가게 된다.
그래서 '정희'로 되돌아오면 '정희' 역시 새로 방문할 정점이 더 없기 때문에 자신에게 방문했던 '민석'으로 돌아간다.
그리고 '민석'으로 돌아와서 아직 방문하지 않은 정점은 '지율'이다.
그래서 '지율'로 방문을 하게 된다.
'지율'까지 방문하게 되면 '지율'의 입장에서 새로 방문할 정점은 더 없다.
그래서 자신에게 방문했던 '민석'에게 돌아가고, '민석'도 새로 방문할 정점이 없으므로 '지민'으로 돌아간다.
마찬가지로 '지민'도 새로 방문할 정점이 더 없기 때문에 '동수'로 돌아간다.
마지막으로 '동수' 역시 새로 방문할 정점이 없기 때문에 탐색은 종료가 된다.
이처럼 DFS는 처음 시작한 정점에서 시작해서 시작한 정점으로 돌아오면 끝이 난다.
지금까지 DFS의 원리를 정리하였고, 이 과정의 핵심은 세 가지이다.
1) 한 사람(정점)에만 방문을 한다.
2) 방문할 사람(정점)이 없으면 자신에게 방문한 사람(이전 정점)에게 이를 알린다.
3) 처음 방문을 시작한 사람(정점)의 위치에서 방문은 끝이 난다 (탐색 완료).
[너비 우선 탐색 (BFS)]
[너비 우선 탐색의 원리]
이전의 DFS가 한 사람(정점)에만 방문을 하는 방식이라면, BFS는 자신과 연결된 모든 사람(정점)에 방문을 하는 방식이다.
너비 우선 탐색에서의 '너비'는 '폭'이라고도 한다.
그렇다면 무엇을 기준으로 폭이라고 하는 것일까?
쉽게 생각하면 "한 사람(정점)을 기준으로 방문이 가능한 정점의 수(폭)"라고 생각하면 좋다.
DFS는 깊이를 우선시 하는 방식이었다면 BFS는 '폭'을 우선시하는, '폭을 넓혀가는 방식'이다.
마찬가지로 위와 비슷한 그래프를 예로 들어 원리를 설명하고자 한다.
탐색의 시작 위치는 '지율'에서부터 시작을 한다.
여기서는 '지율'이 방문할 수 있는 '동수'와 '민석'에게 모두 방문을 한다.
그리고 DFS때와 마찬가지로 '동수'와 '민석' 중 누구에게 먼저 갈 것인지 고민을 할 수 있다.
일반화를 하면 "연결된 정점이 둘 이상이면 어느 쪽 정점을 먼저 방문해야 하는가"와 똑같은 고민이다.
DFS때와 마찬가지로 BFS에서도 어느쪽으로 가던 상관은 없다.
여기서는 '동수'에게 먼저 방문한 뒤에 '민석'에게 방문을 한다고 가정하자.
그렇게 되면 '지율'에서 '동수', '민석' 순으로 방문을 한 것이 된다.
그리고 '동수'와 '민석' 역시 다른 사람(정점)에 방문을 해야한다.
여기서는 먼저 방문한 곳이 '동수'이므로 '동수'가 주변 정점에 먼저 방문을 한다.
그래서 '동수'는 '지민'을 방문하게 된다.
그러면 그 다음에는 '지민'이 다른 정점을 방문해야 하는가?
아니다! 이전에 '동수', '민석' 순으로 방문을 했기 때문에 '민석'이 먼저 다른 정점에 방문을 해야한다.
'민석'은 '수정', '정희'를 방문하게 하게 된다.
그리고 이 시점에서 방문은 받았지만, 아직 다른 사람(정점)에 방문을 하지 않은 사람을 정리해보자.
'지민', '수정', '정희' 이 세 사람(정점)이 된다.
그런데 여기서 '지민'과 '수정'의 주변 정점은 이미 방문을 완료한 상태이므로 둘은 더 이상 방문을 할 필요가 없다.
그래서 마지막으로 남은 '정희'가 '명석'을 방문한다.
'정희'가 '명석'을 방문하게 되고, '명석'은 방문을 받은 상황이다.
그리고 '명석'은 다른 정점을 방문할 기회를 갖게 된다.
하지만 더 이상 방문할 정점이 없으므로 탐색은 종료된다.
이처럼 BFS는 처음 시작한 정점에서 시작해서 더 이상 방문할 정점이 없으면 끝이 난다.
지금까지 BFS의 원리를 정리하였고, 이 과정의 핵심은 다음과 같다.
1) 자신과 연결된 사람(정점) 모두에게 방문을 한다.
2) 방문을 받은 사람(정점)은 다른 사람(정점)을 방문할 기회를 얻게 된다.
그리고 그 기회는 순서대로 진행되어야 한다.
3) 마지막으로 방문을 받은 사람(정점)이 더 이상 방문할 정점이 없으면 탐색이 완료된다.
[DFS의 구현]
[DFS의 구현 모델]
실제로 구현하기에 앞서 사용될 자료구조들이 있다.
1) 스택: 경로 정보의 추적을 목적으로 사용
2) 배열: 방문 정보의 기록을 목적으로 사용
이 둘이 왜 사용되는지 이전의 예시를 기준으로 설명하고자 한다.
현재 시작점은 '동수'를 시작으로 하고 있다.
그래서 배열에는 '동수'를 방문했다고 기록을 한 상태에서 시작한다.
'동수'에서 '지민'으로 이동한 상황이다.
여기서 중요한 부분은 바로 이것이다.
"'동수'를 떠나서 '지민'에게 방문할 때, '동수'를 스택에 저장한다."
이처럼 방문한 정점을 떠날 때에는 떠나는 정점의 정보를 스택에 쌓아야 한다.
이후 수정까지 진행한 상황이라고 치면 아래의 그림과 같이 된다.
현재 '수정'까지 방문이 된 상태이고, 지나온 경로의 순서대로 스택에 정점들이 저장된 상황이다.
그리고 '수정'은 더 이상 방문할 정점이 없기 때문에 이전 정점으로 되돌아가야 한다.
이처럼 DFS에서는 갔던 길을 되돌아오는 상황이 발생하게 된다.
그래서 스택이 필요한 것이다.
자신과 연결된 정점들이 모두 방문을 완료한 상태이므로 자신을 방문했던 정점으로 돌아간다.
그 정점으로 돌아가기 위해서 스택에서 POP을 수행하면 해당 정점이 바로 이전 정점이 된다.
그리고 '정희'도 마찬가지로 자신과 연결된 모든 정점의 방문이 완료된 상태이므로 '민석'으로 돌아가면 된다.
그래서 '민석' 정점까지 돌아온 상황이다.
그리고 현재 상황에서 '민석'은 '지율'에 방문할 수 있다.
'민석'은 '지율'을 방문하게 되고 스택에는 다시 '민석'이 들어가게 된다.
여기서 주목할 점은 '민석'이 다시 스택에 들어간 것이다.
'민석'은 이전에 방문이 이뤄졌다.
하지만 방문 여부와 상관 없이 해당 정점을 떠나 다른 정점을 방문하면 그 정보는 스택에 저장된다는 것이다.
'지율'까지 방문이 완료되었고, 더 이상 방문할 정점은 없는 상황이다.
그래서 스택에 있는 것들을 하나씩 POP하면서 되돌아가면 시작점인 '동수'로 돌아오게 된다.
이처럼 DFS 알고리즘의 구현에 있어 정점의 이동에 가장 중요한 것은 '스택'이다.
[구현]
이전에 구현했던 스택과 리스트, 그래프의 코드를 다시 활용하고자 한다.
여기서 스택과 관련된 코드는 아래의 링크에 있는 연결 리스트 기반의 스택을 써도 된다.
https://sevenshards.tistory.com/5
[자료구조, C] 리스트 기반 스택을 이용한 계산기 구현
[ListBaseStack.h] /* * 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3 * 파일명: ListBaseStack.h * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-23 * 이전 버전 작성 일자: * 버전 내용: 중위 표기
sevenshards.tistory.com
별도로 코드를 수정하기가 귀찮을 수도 있으므로, 배열 기반의 스택 코드를 같이 수록하겠다.
[ArrayBaseStack.h]
/*
* 선형 자료구조 - 스택 (배열 기반)
* 파일명: ArrayBaseStack.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-03
* 이전 버전 작성 일자:
* 버전 내용: 간단한 배열 기반 스택 구현
* 이전 버전 내용:
*/
#ifndef __ARRAY_BASE_STACK_H__
#define __ARRAY_BASE_STACK_H__
#define TRUE 1
#define FALSE 0
#define STACK_LEN 100
typedef int Data; // 편의상 int를 Data로, 다른 데이터 타입 넣어서 메인 함수 바꿔가면서 하면 됨
typedef struct _arrayStack
{
Data stackArr[STACK_LEN]; // 배열을 기반으로 한 스택이므로 배열 사용, 현재 기준 int형 배열
int topIndex; // 현재 스택의 데이터가 저장된 위치를 기억하기 위해 사용하는 top 변수, 여기서는 topindex라고 하였음
} ArrayStack;
typedef ArrayStack Stack; // 편의상 ArrayStack이라고 쓰기 뭐하니 별칭으로 Stack이라고 함
void StackInit(Stack* pstack); // 스택 초기화
int SisEmpty(Stack* pstack); // 스택이 비어있는가 아닌가 확인
void SPush(Stack* pstack, Data data); // 스택에 데이터를 저장 (일반적인 stack의 push연산)
Data SPop(Stack* pstack); // 스택에 있는 데이터를 제거, 동시에 값을 반환 (일반적인 stack의 pop연산)
Data SPeek(Stack* pstack); // 스택에 마지막으로 들어가있는 값을 확인, 제거는 하지 않음 (일반적인 stack의 peek연산)
#endif
[ArrayBaseStack.c]
/*
* 선형 자료구조 - 스택 (배열 기반)
* 파일명: ArrayBaseStack.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-03
* 이전 버전 작성 일자:
* 버전 내용: 간단한 배열 기반 스택 구현
* 이전 버전 내용:
*/
#include <stdio.h>
#include <stdlib.h>
#include "ArrayBaseStack.h"
void StackInit(Stack* pstack) // 스택 초기화
{
pstack->topIndex = -1; // 배열이므로 현재 가리키는 인덱스는 -1로.
}
int SisEmpty(Stack* pstack) // 스택이 비어있는가 아닌가 확인
{
if (pstack->topIndex == -1) // 스택이 비어있다면
return TRUE;
else
return FALSE;
}
void SPush(Stack* pstack, Data data) // 스택에 데이터를 저장 (일반적인 stack의 push연산)
{
pstack->topIndex += 1; // 인덱스를 하나 증가시키고
pstack->stackArr[pstack->topIndex] = data; // 스택(배열)에 데이터를 저장
}
Data SPop(Stack* pstack) // 스택에 있는 데이터를 제거, 동시에 값을 반환 (일반적인 stack의 pop연산)
{
int rIdx; // 지워질 인덱스 값, 왜 처음부터 초기화를 안했는가?
if (SisEmpty(pstack)) // 먼저 스택이 비어있는가 아닌가를 확인
{
printf("Stack is Empty!"); // 비어있다면 다음을 화면에 출력하고
exit(-1); // 종료, 참고로 exit 함수는 stdlib.h에 있다
}
rIdx = pstack->topIndex; // 지워질 인덱스 값을 현재 스택의 topIndex 값을 주고
pstack->topIndex -= 1; // 인덱스 값을 하나 감소시킨다.
return pstack->stackArr[rIdx]; // 현재 지워질 인덱스가 가진 값을 반환하며 종료.
}
Data SPeek(Stack* pstack) // 스택에 마지막으로 들어가있는 값을 확인, 제거는 하지 않음 (일반적인 stack의 peek연산)
{
// pop 연산과 거의 동일함, 하지만 스택의 마지막 데이터는 지우지 않는 것이 포인트.
if (SisEmpty(pstack)) // 먼저 스택이 비어있는가 아닌가를 확인
{
printf("Stack is Empty!"); // 비어있다면 다음을 화면에 출력하고
exit(-1); // 종료, 참고로 exit 함수는 stdlib.h에 있다
}
return pstack->stackArr[pstack->topIndex]; // 현재 topIndex가 가진 값을 반환하며 종료.
}[ALGraphDFS.h]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: ALGraphDFS.h
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현
* 이전 버전 내용: 간단한 인접 리스트 기반 무방향 그래프 구현 (이전 파일명: ALGraph.h)
*/
#ifndef __ALGRAPH_H__
#define __ALGRAPH_H__
// 인접 리스트 기반으로 구현을 하므로 단일 연결 리스트를 사용
#include "SingleLinkedList.h"
// 정점의 이름을 상수화
// A는 0으로 초기화되어 1씩 증가
enum { A, B, C, D, E, F, G, H, I, J };
// 무방향 인접 리스트(Undirected Adjacent List) 그래프 구조체
typedef struct _ual
{
int numVertex; // 정점의 수
int numEdge; // 간선의 수
List* adjList; // 간선의 정보(어떤 정점과 연결되었는지에 대한 정보)
int* visitInfo; // 방문 정보(정점 방문 여부 정보) -> 방문 정보를 기록하기 위한 배열
} ALGraph;
// 그래프 자료구조의 ADT
// 초기화
void GraphInit(ALGraph* pg, int nv);
// 그래프의 리소스 해제 (삭제)
void GraphDestroy(ALGraph* pg);
// 간선 추가(연결)
void AddEdge(ALGraph* pg, int fromV, int toV);
// 간선 정보 출력
void ShowGraphEdgeInfo(ALGraph* pg);
// 깊이 우선 탐색(DFS) 기반 그래프의 정점 정보 출력
void DFSShowGraphVertex(ALGraph* pg, int startV);
#endif
[ALGraphDFS.c]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: ALGraphDFS.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현
* 이전 버전 내용: 간단한 인접 리스트 기반 무방향 그래프 구현 (이전 파일명: ALGraph.c)
*/
#include <stdio.h>
#include <stdlib.h>
#include "ALGraphDFS.h"
// 인접 리스트 기반으로 구현을 하므로 단일 연결 리스트를 사용
#include "SingleLinkedList.h"
// DFS 구현에 사용에 스택을 사용
#include "ArrayBaseStack.h"
// 저자는 출력의 형태를 좋게 하기 위해서 정렬 기준(우선순위 판별)을 넣었다.
// 사실 넣어도 그만이고 안넣어도 그만인 부분이다.
// 혹시라도 이 미흡한 코드를 보고 따라한다면 이 함수는 빼도 된다.
int WhoisPrecede(int d1, int d2)
{
// 오름차순 정렬
if (d1 < d2)
return 0; // d1의 우선 순위가 앞선다면 0을
else
return 1; // d2의 우선 순위가 앞서거나 같다면 1을
}
// 그래프 자료구조의 ADT
// 초기화
void GraphInit(ALGraph* pg, int nv)
{
pg->numVertex = nv; // 입력받은 nv는 정점의 수
pg->numEdge = 0; // 초기화시 간선의 수는 0
pg->adjList = (List*)malloc(sizeof(List) * pg->numVertex); // 정점의 수만큼 메모리 할당
pg->visitInfo = (int*)malloc(sizeof(int) * pg->numVertex); // 정점의 수만큼 메모리 할당
memset(pg->visitInfo, 0, sizeof(int) * pg->numVertex); // 배열의 모든 요소를 0으로 초기화
int i; // 반복문에서 사용할 변수 i
for (i = 0; i < nv; i++)
{
ListInit(&(pg->adjList[i])); // 정점의 수만큼 List 초기화
SetSortRule(&(pg->adjList[i]), WhoisPrecede); // 각 List에 정렬 기준 함수 등록 -> 정렬 기준을 안쓴다면 빼도 됨
}
}
// 그래프의 리소스 해제 (삭제)
void GraphDestroy(ALGraph* pg)
{
if (pg->adjList != NULL) // NULL이 아니라면 할당이 된 상황
free(pg->adjList); // 할당 해제
if (pg->visitInfo != NULL) // NULL이 아니라면 할당이 된 상황
free(pg->visitInfo); // 할당 해제
}
// 간선 추가(연결)
void AddEdge(ALGraph* pg, int fromV, int toV)
{
LInsert(&(pg->adjList[fromV]), toV); // from->to
LInsert(&(pg->adjList[toV]), fromV); // to->from
pg->numEdge += 1; // 간선 갯수 추가
}
// 간선 정보 출력
void ShowGraphEdgeInfo(ALGraph* pg)
{
int i; // 반복문에 사용할 변수 i
int vertex; // 정점
for (i = 0; i < pg->numVertex; i++)
{
printf("%c와 연결된 정점: ", i + 65); // 아스키 코드 65가 'A'
if (LFirst(&(pg->adjList[i]), &vertex))
{
printf("%c ", vertex += 65);
while (LNext(&(pg->adjList[i]), &vertex))
printf("%c ", vertex += 65);
}
printf("\n");
}
}
// 정점의 방문을 진행하는 함수
// 두 번째 인자로 전달된 이름의 정점에 방문을 진행
int VisitVertex(ALGraph* pg, int visitV)
{
if (pg->visitInfo[visitV] == 0) // 아직 방문하지 않았다면
{
pg->visitInfo[visitV] = 1; // 방문한 것으로 바꾼다. 0이면 아직 안들른 것, 1이면 들른것. flag 개념
printf("%c ", visitV + 65); // 방문한 정점의 이름을 출력
return TRUE; // 방문을 했으므로 TRUE 반환
}
return FALSE; // 방문을 못했으므로 FALSE 반환
}
// 깊이 우선 탐색(DFS) 기반 그래프의 정점 정보 출력
void DFSShowGraphVertex(ALGraph* pg, int startV)
{
Stack stack; // 경로 정보의 추적에 사용할 스택
int visitV = startV; // 시작 정점으로 방문한 정점을 초기화
int nextV; // 다음에 방문할 정점
StackInit(&stack); // 스택의 초기화
VisitVertex(pg, visitV); // 시작 정점을 방문
// 여기서 스택에 넣는 부분은 사실 필요가 없다.
// 카페에서 저자의 답변을 확인해본 결과는 다음과 같았다.
// VisitVertex와 SPush는 쌍을 이루는 것이 좋고, 가독성 차원에서 놔둔 것이라고.
// 실제로 디버깅을 하면 스택에는 시작 정점이 두 번 들어가는 것이 확인된다.
// 결론은 주석 처리해도 문제가 되지 않는다.
// SPush(&stack, visitV); // 시작 정점의 정보를 스택에 넣는다.
// visitV에 담긴 정점과 연결된 정점의 방문을 시도하기 위한 반복문
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) // 현재 정점과 연결된 간선이 있다면
{
// 현재 visitV와 연결된 정점의 정보는 nextV에 담긴 상태
int visitFlag = FALSE; // 방문 flag를 FALSE로 한다.
if (VisitVertex(pg, nextV) == TRUE) // 다음 정점 방문에 성공했다면
{
SPush(&stack, visitV); // visitV에 담긴 정점의 정보를 스택에 넣는다.
visitV = nextV; // 그리고 다음에 방문할 정점의 정보로 변경
visitFlag = TRUE; // 방문에 성공했으므로 TRUE로 변경
}
else // 방문에 성공하지 못했다면
{
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE) // 다른 방문할 정점을 찾는다.
{
if (VisitVertex(pg, nextV) == TRUE) // 정점 방문에 성공했다면
{
SPush(&stack, visitV); // visitV에 담긴 정점의 정보를 스택에 넣는다.
visitV = nextV; // 그리고 다음에 방문할 정점의 정보로 변경
visitFlag = TRUE; // 방문에 성공했으므로 TRUE로 변경
break; // 방문에 성공했으므로 반복 중단
}
}
}
if (visitFlag == FALSE) // 추가로 방문한 정점이 하나도 없다면
{
if (SisEmpty(&stack)) // 스택이 비었다면 탐색이 종료된 것
break;
else // 스택이 비어있는 상태가 아니라면
visitV = SPop(&stack); // 이전의 경로로 돌아가기 위해 스택에서 꺼낸다.
}
}
// 이후 탐색을 다시 수행할 수 있으므로 배열의 정보를 초기화
memset(pg->visitInfo, 0, sizeof(int) * pg->numVertex); // 배열의 모든 요소를 0으로 초기화
}
[DFSMain.c]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: DFSMain.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현
* 이전 버전 내용: 간단한 인접 리스트 기반 무방향 그래프 구현 (이전 파일명: ALGraphMain.c)
*/
#include <stdio.h>
#include "ALGraphDFS.h"
int main()
{
ALGraph graph; // 그래프 생성
GraphInit(&graph, 7); // 그래프 초기화
// 정점 연결 (간선 추가)
AddEdge(&graph, A, B);
AddEdge(&graph, A, D);
AddEdge(&graph, B, C);
AddEdge(&graph, C, D);
AddEdge(&graph, D, E);
AddEdge(&graph, E, F);
AddEdge(&graph, E, G);
ShowGraphEdgeInfo(&graph);
// A, C, E, G를 시작으로 DFS 탐색
DFSShowGraphVertex(&graph, A);
printf("\n");
DFSShowGraphVertex(&graph, C);
printf("\n");
DFSShowGraphVertex(&graph, E);
printf("\n");
DFSShowGraphVertex(&graph, G);
printf("\n");
GraphDestroy(&graph);
return 0;
}
소스 코드에 주석을 글이 너무 길어질 것 같아서 소스코드에 주석을 다는 형식으로 정리를 하였다.
그래프에서 사용했던 ALGraph.h와 ALGraph.c는 ALGraphDFS.h와 ALGraphDFS.c로 바꾸었다.
그리고 DFS 알고리즘에 대한 부분을 추가하였다.
https://sevenshards.tistory.com/30
[자료구조, C] 그래프(Graph)의 이해와 종류
[그래프에 들어가기에 앞서] 그래프 역시 자료구조이며, 비선형 자료구조에 해당한다. 그리고 트리 때와도 마찬가지로 데이터의 저장보다는 '표현'을 하는데 중점적이다. 실제로 그래프라는 자
sevenshards.tistory.com
[BFS의 구현]
[BFS의 구현 모델]
DFS와 마찬가지로 구현하기에 앞서 사용될 자료구조들이 있다.
1) 큐: 방문 차례의 기록을 목적으로 사용
2) 배열: 방문 정보의 기록을 목적으로 사용
DFS와 달리 BFS는 큐를 사용한다.
큐를 사용한 이유도 이전 예시를 되짚어가면서 확인해보자.
현재 시작점은 '지율'이다.
그래서 배열에는 '지율'의 방문 정보를 기록한다.
그리고 '지율'에서 '동수', '민석' 순으로 방문을 한다.
여기서 주목할 부분은 '동수'와 '민석'은 방문을 받았지만 다른 정점에 방문을 한 상태가 아니다.
그래서 방문할 차례를 저장하기 위해 큐에 저장하게 된다.
이후 큐에서 데이터를 하나 꺼내면 '동수'가 나오게 된다.
큐에서 나온 '동수'를 중심으로 방문 가능한 다른 정점에 방문을 하고, 큐에는 '지민'이 들어가게 된다.
그 다음은 큐에서 '민석'이 나오게 되고, '민석'을 중심으로 방문 가능한 다른 정점에 방문을 한다.
그리고 마찬가지로 방문을 받은 정점들을 큐에 저장한다.
이어서 큐에 있던 '지민', '수정' 이 나오게 되는데, 방문 가능한 다른 정점이 없다.
그래서 '정희'까지 큐에서 꺼내면 다음에 방문할 정점인 '명석'을 방문하게 된다.
그리고 마지막으로 '명석'이 큐에 들어가게 된다.
이후 큐에서 '명석'을 꺼낸 이후 방문 가능한 다른 정점이 없다면 탐색은 종료된다.
즉, 마지막에 큐가 비어있는 상태라면 탐색은 종료가 된 것이다.
DFS 알고리즘에서 핵심이 되었던 것이 스택이라면, BFS에서는 큐가 핵심이 된다.
[구현]
이전에 구현했던 DFS 알고리즘을 추가로 구현한 그래프의 코드를 다시 활용하고자 한다.
그리고 추가가 되는 것은 큐를 추가하는 것과 BFS 알고리즘을 추가하는 정도다.
여기서 큐는 배열 기반의 원형 큐를 써도 되고, 연결 리스트 기반의 큐를 써도 상관이 없다.
해당 글에서는 배열 기반의 원형 큐를 수록할 것이다.
별도로 연결 리스트 기반의 큐를 쓰고 싶다 하는 분은 깃허브에 코드가 있으니 그 코드를 쓰셔도 무방하다.
https://github.com/sevenshards00/DataStructure_C
GitHub - sevenshards00/DataStructure_C: 자료구조와 알고리즘 공부 모음 (C언어 기반)
자료구조와 알고리즘 공부 모음 (C언어 기반). Contribute to sevenshards00/DataStructure_C development by creating an account on GitHub.
github.com
[CircularQueue.h]
/*
* 선형 자료구조 - Queue (배열 기반, 원형 큐)
* 파일명: CircularQueue.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-05
* 이전 버전 작성 일자:
* 버전 내용: 배열 기반의 원형(Circular) Queue 구현
* 이전 버전 내용:
*/
#ifndef __C_QUEUE_H__
#define __C_QUEUE_H__
#define TRUE 1
#define FALSE 0
#define QUE_LEN 100 // 큐의 길이, 배열이므로 매크로로 100으로 고정
typedef int Data; // 편의상 받는 데이터는 int로 했고 Data로 지칭, 다른 데이터로 바꾼다면 여길 바꾸면 된다
typedef struct _circularqueue // 배열 기반 원형 큐의 구조체, 배열과 front, rear 셋으로 구성
{
Data arr[QUE_LEN]; // 현재 큐를 구성할 배열
int front; // front
int rear; // rear
} CQueue;
typedef CQueue Queue; // 편의상 CQueue를 Queue로 별칭 붙여 사용
void QueueInit(Queue* pq); // Queue 초기화
int QisEmpty(Queue* pq); // Queue가 비었는가 확인
void QEnqueue(Queue* pq, Data data); // Queue에 데이터 삽입
Data QDequeue(Queue* pq); // Queue에 들어있는 데이터 반환 및 삭제
Data QPeek(Queue* pq); // 현재 Front가 가리키는 값 반환
#endif
[CircularQueue.c]
/*
* 선형 자료구조 - Queue (배열 기반, 원형 큐)
* 파일명: CircularQueue.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-05
* 이전 버전 작성 일자:
* 버전 내용: 배열 기반의 원형(Circular) Queue 구현
* 이전 버전 내용:
*/
#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"
void QueueInit(Queue* pq) // Queue 초기화
{
pq->front = 0; // front는 0을 가리키고
pq->rear = 0; // rear도 0을 가리킨다
}
int QisEmpty(Queue* pq) // Queue가 비었는가 확인
{
if (pq->front == pq->rear) // front와 rear가 똑같다면
return TRUE; // 비어있으므로 TRUE 반환
else
return FALSE; // 비어있지 않다면 FALSE 반환
}
// 배열 기반 원형 큐에서만 쓰이는 함수
// 배열 내에서 front와 rear가 계속 돌아야하므로 사용한다.
int NextPosIdx(int pos)
{
// 실제 배열 인덱스의 끝은 QUE_LEN-1
// 그리고 현재 인덱스가 끝을 가리킨다면
// 다시 0부터 돌려보내기 위함
//
if (pos == QUE_LEN - 1) // 현재 인덱스가 끝을 가리킨다면
return 0; // 0으로 돌려보낸다
else // 그게 아니라면
return pos + 1; // 다음 인덱스를 가리키게 한다
}
void QEnqueue(Queue* pq, Data data) // Queue에 데이터 삽입
{
if (NextPosIdx(pq->rear) == pq->front) // rear의 다음이 front라면? Queue가 꽉 찼다는 것
{
printf("Queue Fulled\n");
exit(-1); // 더 이상 채울 수 없으므로 종료
}
//그게 아니라면
pq->rear = NextPosIdx(pq->rear); // rear를 한 칸 앞으로 이동하고
pq->arr[pq->rear] = data; // 데이터를 넣는다.
}
Data QDequeue(Queue* pq) // Queue에 들어있는 데이터 반환 및 삭제
{
if (QisEmpty(pq)) // Queue가 비었다면
{
printf("Queue is Empty\n");
exit(-1); // 수행 못하므로 종료
}
// 그게 아니라면
pq->front = NextPosIdx(pq->front); // front를 다음 인덱스로 바꾸고
return pq->arr[pq->front]; // 현재 front가 가리키는 인덱스의 값을 반환
}
Data QPeek(Queue* pq) // 현재 Front가 가리키는 값 반환
{
if (QisEmpty(pq)) // Queue가 비었다면
{
printf("Queue is Empty\n");
exit(-1); // 수행 못하므로 종료
}
// 그게 아니라면
return pq->arr[NextPosIdx(pq->front)]; // 현재 front가 가리키는 인덱스의 값을 반환
}
[ALGraphBFS.h]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: ALGraphBFS.h
* 파일 버전: 0.3
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 너비 우선 탐색(Breadth First Search) 추가 구현
* 이전 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현 (이전 파일명: ALGraphDFS.h)
*/
#ifndef __ALGRAPH_H__
#define __ALGRAPH_H__
// 인접 리스트 기반으로 구현을 하므로 단일 연결 리스트를 사용
#include "SingleLinkedList.h"
// 정점의 이름을 상수화
// A는 0으로 초기화되어 1씩 증가
enum { A, B, C, D, E, F, G, H, I, J };
// 무방향 인접 리스트(Undirected Adjacent List) 그래프 구조체
typedef struct _ual
{
int numVertex; // 정점의 수
int numEdge; // 간선의 수
List* adjList; // 간선의 정보(어떤 정점과 연결되었는지에 대한 정보)
int* visitInfo; // 방문 정보(정점 방문 여부 정보) -> 방문 정보를 기록하기 위한 배열
} ALGraph;
// 그래프 자료구조의 ADT
// 초기화
void GraphInit(ALGraph* pg, int nv);
// 그래프의 리소스 해제 (삭제)
void GraphDestroy(ALGraph* pg);
// 간선 추가(연결)
void AddEdge(ALGraph* pg, int fromV, int toV);
// 간선 정보 출력
void ShowGraphEdgeInfo(ALGraph* pg);
// 깊이 우선 탐색(DFS) 기반 그래프의 정점 정보 출력
void DFSShowGraphVertex(ALGraph* pg, int startV);
// 너비 우선 탐색(BFS) 기반 그래프의 정점 정보 출력
void BFSShowGraphVertex(ALGraph* pg, int startV);
#endif[ALGraphBFS.c]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: ALGraphBFS.c
* 파일 버전: 0.3
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 너비 우선 탐색(Breadth First Search) 추가 구현
* 이전 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현 (이전 파일명: ALGraphDFS.c)
*/
#include <stdio.h>
#include <stdlib.h>
#include "ALGraphBFS.h"
// 인접 리스트 기반으로 구현을 하므로 단일 연결 리스트를 사용
#include "SingleLinkedList.h"
// DFS 구현에 스택을 사용
#include "ArrayBaseStack.h"
// BFS 구현에 큐를 사용
#include "CircularQueue.h"
// 저자는 출력의 형태를 좋게 하기 위해서 정렬 기준(우선순위 판별)을 넣었다.
// 사실 넣어도 그만이고 안넣어도 그만인 부분이다.
// 혹시라도 이 미흡한 코드를 보고 따라한다면 이 함수는 빼도 된다.
int WhoisPrecede(int d1, int d2)
{
// 오름차순 정렬
if (d1 < d2)
return 0; // d1의 우선 순위가 앞선다면 0을
else
return 1; // d2의 우선 순위가 앞서거나 같다면 1을
}
// 그래프 자료구조의 ADT
// 초기화
void GraphInit(ALGraph* pg, int nv)
{
pg->numVertex = nv; // 입력받은 nv는 정점의 수
pg->numEdge = 0; // 초기화시 간선의 수는 0
pg->adjList = (List*)malloc(sizeof(List) * pg->numVertex); // 정점의 수만큼 메모리 할당
pg->visitInfo = (int*)malloc(sizeof(int) * pg->numVertex); // 정점의 수만큼 메모리 할당
memset(pg->visitInfo, 0, sizeof(int) * pg->numVertex); // 배열의 모든 요소를 0으로 초기화
int i; // 반복문에서 사용할 변수 i
for (i = 0; i < nv; i++)
{
ListInit(&(pg->adjList[i])); // 정점의 수만큼 List 초기화
SetSortRule(&(pg->adjList[i]), WhoisPrecede); // 각 List에 정렬 기준 함수 등록 -> 정렬 기준을 안쓴다면 빼도 됨
}
}
// 그래프의 리소스 해제 (삭제)
void GraphDestroy(ALGraph* pg)
{
if (pg->adjList != NULL) // NULL이 아니라면 할당이 된 상황
free(pg->adjList); // 할당 해제
if (pg->visitInfo != NULL) // NULL이 아니라면 할당이 된 상황
free(pg->visitInfo); // 할당 해제
}
// 간선 추가(연결)
void AddEdge(ALGraph* pg, int fromV, int toV)
{
LInsert(&(pg->adjList[fromV]), toV); // from->to
LInsert(&(pg->adjList[toV]), fromV); // to->from
pg->numEdge += 1; // 간선 갯수 추가
}
// 간선 정보 출력
void ShowGraphEdgeInfo(ALGraph* pg)
{
int i; // 반복문에 사용할 변수 i
int vertex; // 정점
for (i = 0; i < pg->numVertex; i++)
{
printf("%c와 연결된 정점: ", i + 65); // 아스키 코드 65가 'A'
if (LFirst(&(pg->adjList[i]), &vertex))
{
printf("%c ", vertex += 65);
while (LNext(&(pg->adjList[i]), &vertex))
printf("%c ", vertex += 65);
}
printf("\n");
}
}
// 정점의 방문을 진행하는 함수
// 두 번째 인자로 전달된 이름의 정점에 방문을 진행
int VisitVertex(ALGraph* pg, int visitV)
{
if (pg->visitInfo[visitV] == 0) // 아직 방문하지 않았다면
{
pg->visitInfo[visitV] = 1; // 방문한 것으로 바꾼다. 0이면 아직 안들른 것, 1이면 들른것. flag 개념
printf("%c ", visitV + 65); // 방문한 정점의 이름을 출력
return TRUE; // 방문을 했으므로 TRUE 반환
}
return FALSE; // 방문을 못했으므로 FALSE 반환
}
// 깊이 우선 탐색(DFS) 기반 그래프의 정점 정보 출력
void DFSShowGraphVertex(ALGraph* pg, int startV)
{
Stack stack; // 경로 정보의 추적에 사용할 스택
int visitV = startV; // 시작 정점으로 방문한 정점을 초기화
int nextV; // 다음에 방문할 정점
StackInit(&stack); // 스택의 초기화
VisitVertex(pg, visitV); // 시작 정점을 방문
// 여기서 스택에 넣는 부분은 사실 필요가 없다.
// 카페에서 저자의 답변을 확인해본 결과는 다음과 같았다.
// VisitVertex와 SPush는 쌍을 이루는 것이 좋고, 가독성 차원에서 놔둔 것이라고.
// 실제로 디버깅을 하면 스택에는 시작 정점이 두 번 들어가는 것이 확인된다.
// 결론은 주석 처리해도 문제가 되지 않는다.
// SPush(&stack, visitV); // 시작 정점의 정보를 스택에 넣는다.
// visitV에 담긴 정점과 연결된 정점의 방문을 시도하기 위한 반복문
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) // 현재 정점과 연결된 간선이 있다면
{
// 현재 visitV와 연결된 정점의 정보는 nextV에 담긴 상태
int visitFlag = FALSE; // 방문 flag를 FALSE로 한다.
if (VisitVertex(pg, nextV) == TRUE) // 다음 정점 방문에 성공했다면
{
SPush(&stack, visitV); // visitV에 담긴 정점의 정보를 스택에 넣는다.
visitV = nextV; // 그리고 다음에 방문할 정점의 정보로 변경
visitFlag = TRUE; // 방문에 성공했으므로 TRUE로 변경
}
else // 방문에 성공하지 못했다면
{
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE) // 다른 방문할 정점을 찾는다.
{
if (VisitVertex(pg, nextV) == TRUE) // 정점 방문에 성공했다면
{
SPush(&stack, visitV); // visitV에 담긴 정점의 정보를 스택에 넣는다.
visitV = nextV; // 그리고 다음에 방문할 정점의 정보로 변경
visitFlag = TRUE; // 방문에 성공했으므로 TRUE로 변경
break; // 방문에 성공했으므로 반복 중단
}
}
}
if (visitFlag == FALSE) // 추가로 방문한 정점이 하나도 없다면
{
if (SisEmpty(&stack)) // 스택이 비었다면 탐색이 종료된 것
break;
else // 스택이 비어있는 상태가 아니라면
visitV = SPop(&stack); // 이전의 경로로 돌아가기 위해 스택에서 꺼낸다.
}
}
// 이후 탐색을 다시 수행할 수 있으므로 배열의 정보를 초기화
memset(pg->visitInfo, 0, sizeof(int) * pg->numVertex); // 배열의 모든 요소를 0으로 초기화
}
// 너비 우선 탐색(BFS) 기반 그래프의 정점 정보 출력
void BFSShowGraphVertex(ALGraph* pg, int startV)
{
Queue queue; // 방문할 차례(순서)의 기록을 목적으로 큐 생성
int visitV = startV; // 시작 정점으로 방문할 정점을 초기화
int nextV; // 다음에 방문할 정점
QueueInit(&queue); // 큐 초기화
VisitVertex(pg, visitV); // 시작 정점 방문
// visitV에 담긴 정점과 연결된 정점의 모든 정점에 방문하기 위한 반복문
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) // 현재 정점과 연결된 간선이 있다면
{
// 현재 visitV와 연결된 정점의 정보는 nextV에 담긴 상태
if (VisitVertex(pg, nextV) == TRUE) // 다음 정점 방문에 성공했다면
QEnqueue(&queue, nextV); // nextV에 방문했으므로 큐에 저장
// 가독성 차원에서 '== TRUE' 삽입, 어차피 반환 결과가 TRUE, FALSE이긴 하지만 코드 읽기 편하려면 넣는게 좋다
while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE) // 이어서 방문할 정점을 찾는다.
{
if (VisitVertex(pg, nextV) == TRUE) // 정점 방문에 성공했다면
QEnqueue(&queue, nextV); // nextV에 방문했으므로 큐에 저장
}
if (QisEmpty(&queue)) // 큐가 비었다면 탐색이 종료된 것
break;
else // 큐가 비어있는 상태가 아니라면
visitV = QDequeue(&queue); // 큐에서 하나 정점을 하나 꺼내어 다시 반복문 수행.
}
// 이후 탐색을 다시 수행할 수 있으므로 배열의 정보를 초기화
memset(pg->visitInfo, 0, sizeof(int) * pg->numVertex); // 배열의 모든 요소를 0으로 초기화
}[BFSMain.c]
/*
* 비선형 자료구조 - 인접 리스트(Adjacent List) 기반 무방향 그래프
* 파일명: ALGraphBFS.h
* 파일 버전: 0.3
* 작성자: Sevenshards
* 작성 일자: 2023-11-30
* 이전 버전 작성 일자: 2023-11-30
* 버전 내용: 너비 우선 탐색(Breadth First Search) 추가 구현
* 이전 버전 내용: 깊이 우선 탐색(Depth First Search) 추가 구현 (이전 파일명: DFSMain.c)
*/
#include <stdio.h>
#include "ALGraphBFS.h"
int main()
{
ALGraph graph; // 그래프 생성
GraphInit(&graph, 7); // 그래프 초기화
// 정점 연결 (간선 추가)
AddEdge(&graph, A, B);
AddEdge(&graph, A, D);
AddEdge(&graph, B, C);
AddEdge(&graph, C, D);
AddEdge(&graph, D, E);
AddEdge(&graph, E, F);
AddEdge(&graph, E, G);
ShowGraphEdgeInfo(&graph);
printf("\n");
// A, C, E, G를 시작으로 DFS 탐색
printf("DFS 탐색\n");
DFSShowGraphVertex(&graph, A);
printf("\n");
DFSShowGraphVertex(&graph, C);
printf("\n");
DFSShowGraphVertex(&graph, E);
printf("\n");
DFSShowGraphVertex(&graph, G);
printf("\n\n");
printf("BFS 탐색\n");
// A, C, E, G를 시작으로 BFS 탐색
BFSShowGraphVertex(&graph, A);
printf("\n");
BFSShowGraphVertex(&graph, C);
printf("\n");
BFSShowGraphVertex(&graph, E);
printf("\n");
BFSShowGraphVertex(&graph, G);
printf("\n\n");
GraphDestroy(&graph);
return 0;
}
그래프는 앞서 작성했던 ALGraphDFS.h와 ALGraphDFS.c를 ALGraphBFS.h, ALGraphBFS.c로 이름을 바꾸었다.
그리고 BFS 알고리즘과 관련된 함수가 추가로 구현을 하는 방식을 이용했다.
DFS때와 마찬가지로 글이 길어지지 않도록 코드에 주석을 충분히 달아두었다.
