Chapter 14. 그래프의 탐색 (3)

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

이제 너비 우선 탐색 방법인 BFS를 구현해 볼 차례입니다. BFS의 구현을 위해서는 큐와 배열이 필요합니다. 배열은 DFS와 마찬가지로 각 정점에 방문한 정보를 기록하기 위해 사용됩니다. 그리고 DFS의 스택이 떠나온 정점을 저장하기 위해 사용됐다면, BFS에서 큐는 새로 방문한 정점들을 저장하기 위해 사용됩니다. 

DFS의 구현 방법을 설명할 때 사용한 것과 같은 그래프입니다. 이번에도 지율을 시작으로 모든 정점들을 방문할 것입니다.

지율이 시작 정점이므로 방문 기록을 남깁니다. 지율은 동수와 민석 모두에게 연락합니다. 다만, 동수에게 먼저 연락하고 그다음 민석에게 연락합니다. 이 순서대로 방문한 정점을 큐에 저장합니다.

이제 큐에서 정점 하나를 꺼냅니다. 큐에서 나오는 정점은 동수입니다. 따라서 동수로부터 연락 가능한 정점인 지민에게 연락하고, 지민을 큐에 저장합니다.

이어서 큐에서 정점을 하나 꺼냅니다. 이번에는 민석이 큐에서 나왔으므로, 민석으로부터 수정과 정희에게 연락합니다. 다만, 수정에게 먼저 연락하고 정희에게 연락합니다.

똑같이 큐에서 지민을 꺼냅니다. 지민은 연락할 정점이 없습니다. 이어서 큐에서 나오는 수정 또한 연락할 정점이 없습니다. 큐에서 정희를 꺼내고 정희는 명석에게 연락합니다.

이로써 모든 정점을 방문했지만 아직 끝난 게 아닙니다. 큐에서 명석을 꺼내고 명석이 더 이상 연락할 정점이 없다는 것까지 확인한 후에야 비로소 BFS가 종료됩니다.

---

이제 BFS를 코드로 구현해 보겠습니다. 앞서 구현했던 ALGraph.h 파일과 ALGraph.c 파일을 확장하여 ALGraph.BFS 파일과 ALGraphBFS.c 파일을 만듭니다. 그리고 확장 과정에서 다음의 함수가 추가됩니다.

void BFShowGraphVertex(ALGraph* pg, int startV);

DFS 방법을 이미 구현해 봤기 때문에 BFS의 구현은 어렵지 않습니다. 먼저, ALGraphBFS.h 파일을 보이겠습니다.

//ALGraphBFS.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 BFShowGraphVertex(ALGraph* pg, int startV);    // 추가된 함수BFS 기반, 정점의 정보 출력

#endif

다음은 ALGraphBFS.c 파일입니다.

//ALGraphDFS.c
//수정날짜 : 2021.03.27
//작성자 : KOEY
#include "ALGraphBFS.h"
#include "LLBQueue.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 BFShowGraphVertex(ALGraph* pg, int startV)
{
	Queue queue;
	int visitV = startV;
	int nextV;

	QueueInit(&queue);
	VisitVertex(pg, visitV);

	while (LFirst(&(pg->adjList[visitV]), &nextV))
	{
		nextV = nextV - 'A';

		if (VisitVertex(pg, nextV))
		{
			Inqueue(&queue, nextV);
		}

		while (LNext(&(pg->adjList[visitV]), &nextV))
		{
			nextV = nextV - 'A';

			if (VisitVertex(pg, nextV))
			{
				Inqueue(&queue, nextV);
			}
		}

		if (QueueIsEmpty(&queue))
		{
			break;
		}
		else
		{
			visitV = Dequeue(&queue);
		}
	}

	memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

위 파일에서,

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;    //방문 실패
}

위 함수는 DFS의 것과 같으며,

void BFShowGraphVertex(ALGraph* pg, int startV)
{
	Queue queue;
	int visitV = startV;
	int nextV;

	QueueInit(&queue);
	VisitVertex(pg, visitV);

	while (LFirst(&(pg->adjList[visitV]), &nextV))
	{
		nextV = nextV - 'A';

		if (VisitVertex(pg, nextV))
		{
			Inqueue(&queue, nextV);
		}

		while (LNext(&(pg->adjList[visitV]), &nextV))
		{
			nextV = nextV - 'A';

			if (VisitVertex(pg, nextV))
			{
				Inqueue(&queue, nextV);
			}
		}

		if (QueueIsEmpty(&queue))
		{
			break;
		}
		else
		{
			visitV = Dequeue(&queue);
		}
	}

	memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

위 함수가 BFS를 구현하는 함수입니다. DFS에 비해 코드를 이해하는 데에 어려움은 없을 것으로 보입니다. 그만큼 DFS에 비하면 간단한 수준으로 구현되었습니다.

 

이제 그 외 다른 파일들을 보이고 main 함수를 정의하여 그 실행결과를 확인해 보겠습니다.

//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;
}

//LLBQueue.h
//수정날짜 : 2021.03.28
//작성자 : KOEY
#ifndef LINKED_LIST_BASE_QUEUE_H
#define LINKED_LIST_BASE_QUEUE_H

#define TRUE 1
#define FALSE 0

typedef int QData;

typedef struct QNode
{
	QData data;
	struct QNode* next;
}QNode;

typedef struct LLBQueue
{
	QNode* tail;
}LLBQueue;

typedef LLBQueue Queue;

void QueueInit(Queue* pq);
int QueueIsEmpty(Queue* pq);
void Inqueue(Queue* pq, QData data);
QData Dequeue(Queue* pq);
QData QPeek(Queue* pq);
void DeleteQueue(Queue* pq);

#endif

//LLBQueue.c
//수정날짜 : 2021.03.28
//작성자 : KOEY
#include "LLBQueue.h"
#include <stdlib.h>
#include <stdio.h>

void QueueInit(Queue* pq)
{
	pq->tail = NULL;
}

int QueueIsEmpty(Queue* pq)
{
	if (pq->tail == NULL)
	{
		return TRUE;
	}

	return FALSE;
}

void Inqueue(Queue* pq, QData data)
{
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		printf("메모리 공간이 부족합니다.\n");
		exit(1);
	}

	newNode->data = data;

	if (pq->tail == NULL)
	{
		newNode->next = newNode;
	}
	else
	{
		newNode->next = pq->tail->next;
		pq->tail->next = newNode;
	}

	pq->tail = newNode;
}

QData Dequeue(Queue* pq)
{
	QNode* delNode = pq->tail->next;
	QData delData = delNode->data;

	if (pq->tail == delNode)
	{
		pq->tail = NULL;
	}
	else
	{
		pq->tail->next = delNode->next;
	}

	free(delNode);
	return delData;
}

QData QPeek(Queue* pq)
{
	return pq->tail->next->data;
}

void DeleteQueue(Queue* pq)
{
	while (!QueueIsEmpty(pq))
	{
		Dequeue(pq);
	}
}

//main.c
//수정날짜 : 2021.03.27
//작성자 : KOEY
#include <stdio.h>
#include "ALGraphBFS.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);    //그래프의 간선 정보 출력
	
	BFShowGraphVertex(&graph, A);
	printf("\n");
	BFShowGraphVertex(&graph, C);
	printf("\n");
	BFShowGraphVertex(&graph, E);
	printf("\n");
	BFShowGraphVertex(&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 B E C G F
C D B E A G F
E G F D C A B
G E F D C A B

*/