[알고리즘] 그래프 4 - 그래프의 순회(너비 우선 탐색 BFS)

목차

너비 우선 탐색(BFS)

1. 큐를 활용: 너비 우선 탐색은 시작 노드에서 인접한 모든 노드를 먼저 방문한 후, 그 다음 레벨의 노드들을 방문하며, 이를 위해 큐를 사용한다.
2. 노드 방문: 시작 노드에서 인접한 노드를 먼저 모두 방문한 후, 다음 레벨의 노드로 이동하며 방문한 노드는 표시하여 중복 방문을 방지한다.
3. 너비 우선 탐색의 특징: 레벨 단위로 탐색하기 때문에 최단 경로를 찾는데 효과적이며, 큐를 사용하기 때문에 반복문으로 구현하기 용이하다.

즉, 시작 정점에 인접한 정점을 모두 차례로 방훈하고 나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례대로 방문하는 방법이다. 가까운 정점을 먼저 방문하고 난 뒤 멀리 있는 정점을 나중에 방문한다.

#pragma once
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX 30	// 헤드 포인터 배열의 최대 크기
#define FALSE 0       //추가!
#define TRUE 1        //추가!

// 인접 리스트의 노드 구조를 구조체로 정의
typedef struct graphNode {
	int vertex;							// 정점을 나타내는 데이터 필드
	struct graphNode* link;			// 다음 인접 정점을 연결하는 링크 필드
} graphNode;

// 그래프를 인접 리스트로 표현하기 위한 구조체 정의
typedef struct graphType {
	int n;								// 그래프의 정점 개수
	graphNode* adjList_H[MAX_VERTEX];	// 그래프 정점에 대한 헤드 포인터 배열
	int visited[MAX_VERTEX];			// 정점에 대한 방문 표시를 위한 배열 추가!
} graphType;

typedef int element;     // 연결 큐 원소(element)의 자료형을 int로 수정!

typedef struct QNode {    // 연결 큐의 노드를 구조체로 정의
	element data;
	struct QNode* link;
} QNode;

typedef struct {		// 연결 큐에서 사용하는 포인터 front와 rear를 구조체로 정의
	QNode* front, * rear;
} LQueueType;


void createGraph(graphType* g);
void insertVertex(graphType* g, int v);
void insertEdge(graphType* g, int u, int v);
void print_adjList(graphType* g);
void BFS_adjList(graphType* g, int v);
LQueueType* createLinkedQueue();
int isLQEmpty(LQueueType* LQ);
void enLQueue(LQueueType* LQ, element item);
element deLQueue(LQueueType* LQ);
element peekLQ(LQueueType* LQ);
void printLQ(LQueueType * LQ); 

// 공백 그래프를 생성하는 연산
void createGraph(graphType* g) {
	int v;
	g->n = 0;							// 그래프의 정점 개수를 0으로 초기화
	for (v = 0; v < MAX_VERTEX; v++) {
		g->adjList_H[v] = NULL;			// 그래프의 정점에 대한 헤드 포인터 배열을 NULL로 초기화
		g->visited[v] = FALSE;			// 그래프의 정점에 대한 배열 visited를 FALSE로 초기화 추가!
	}
}

// 그래프 g에 정점 v를 삽입하는 연산
void insertVertex(graphType* g, int v) {
	if (((g->n) + 1) > MAX_VERTEX) {
		printf("\n 그래프 정점의 개수를 초과하였습니다!");
		return;
	}
	g->n++;								// 그래프의 정점 개수 n을 하나 증가
}

// 그래프 g에 간선 (u, v)를 삽입하는 연산
void insertEdge(graphType* g, int u, int v) {
	graphNode* node;

	// 간선 (u, v)를 삽입하기 위해 정점 u와 정점 v가 현재 그래프에 있는지 확인
	if (u >= g->n || v >= g->n) {
		printf("\n 그래프에 없는 정점입니다!");
		return;
	}
	node = (graphNode*)malloc(sizeof(graphNode));
	node->vertex = v;
	node->link = g->adjList_H[u];	// 삽입 간선에 대한 노드를 리스트의 첫 번째 노드로 연결
	g->adjList_H[u] = node;
}

// 그래프 g의 각 정점에 대한 인접 리스트를 출력하는 연산
void print_adjList(graphType* g) {
	int i;
	graphNode* p;
	for (i = 0; i < g->n; i++) {
		printf("\n\t\t정점 %c의 인접 리스트", i + 65);
		p = g->adjList_H[i];
		while (p) {
			printf(" -> %c", p->vertex + 65); // 정점 0~3을 A~D로 출력
			p = p->link;
		}
	}
}
// 그래프 g에서 정점 v에 대한 너비 우선 탐색 연산 : [알고리즘 8-2] 구현
void BFS_adjList(graphType* g, int v) {
	graphNode* w;
	LQueueType* Q;				// 큐
	Q = createLinkedQueue();	// 큐 생성
	g->visited[v] = TRUE;		// 시작 정점 v에 대한 배열 값을 TRUE로 설정
	printf(" %c", v + 65);
	enLQueue(Q, v);			// 현재 정점 v를 큐에 enQueue

	// 큐가 공백인 아닌 동안 너비 우선 탐색 수행
	while (!isLQEmpty(Q)) {
		v = deLQueue(Q);
		// 현재 정점 w를 방문하지 않은 경우 
		for (w = g->adjList_H[v]; w; w = w->link)	// 인접 정점이 있는 동안 수행
			if (!g->visited[w->vertex]) {	// 정점 w가 방문하지 않은 정점인 경우
				g->visited[w->vertex] = TRUE;
				printf(" %c", w->vertex + 65); // 정점 0~6을 A~G로 바꾸어 출력
				enLQueue(Q, w->vertex);
			}
	} // 큐가 공백이면 너비 우선 탐색 종료	
}

// 공백 연결 큐를 생성하는 연산
LQueueType* createLinkedQueue() {
	LQueueType* LQ;
	LQ = (LQueueType*)malloc(sizeof(LQueueType));
	LQ->front = NULL;
	LQ->rear = NULL;
	return LQ;
}

// 연결 큐가 공백 상태인지 검사하는 연산
int isLQEmpty(LQueueType* LQ) {
	if (LQ->front == NULL) {
		//printf(" Linked Queue is empty! ");
		return 1;
	}
	else return 0;
}

// 연결 큐의 rear에 원소를 삽입하는 연산
void enLQueue(LQueueType* LQ, element item) {
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	newNode->data = item;
	newNode->link = NULL;
	if (LQ->front == NULL) {		// 현재 연결 큐가 공백 상태인 경우
		LQ->front = newNode;
		LQ->rear = newNode;
	}
	else {						// 현재 연결 큐가 공백 상태가 아닌 경우
		LQ->rear->link = newNode;
		LQ->rear = newNode;
	}
}

// 연결 큐에서 원소를 삭제하고 반환하는 연산
element deLQueue(LQueueType* LQ) {
	QNode* old = LQ->front;
	element item;
	if (isLQEmpty(LQ)) return 1;
	else {
		item = old->data;
		LQ->front = LQ->front->link;
		if (LQ->front == NULL)
			LQ->rear = NULL;
		free(old);
		return item;
	}
}

// 연결 큐에서 원소를 검색하는 연산
element peekLQ(LQueueType* LQ) {
	element item;
	if (isLQEmpty(LQ)) return 1;
	else {
		item = LQ->front->data;
		return item;
	}
}

// 연결 큐의 원소를 출력하는 연산
void printLQ(LQueueType* LQ) {
	QNode* temp = LQ->front;
	printf(" Linked Queue : [");
	while (temp) {
		printf("%3d", temp->data); //출력형식 수정
		temp = temp->link;
	}
	printf(" ] ");
}

int main(void) {
	int i;
	graphType* G9;
	G9 = (graphType*)malloc(sizeof(graphType));
	createGraph(G9);
	// 그래프 G9 구성 : 정점 u에 대한 간선 (u,v)의 삽입순서는 v가 큰 것부터.
	for (i = 0; i < 7; i++)
		insertVertex(G9, i);
	insertEdge(G9, 0, 2);
	insertEdge(G9, 0, 1);
	insertEdge(G9, 1, 4);
	insertEdge(G9, 1, 3);
	insertEdge(G9, 1, 0);
	insertEdge(G9, 2, 4);
	insertEdge(G9, 2, 0);
	insertEdge(G9, 3, 6);
	insertEdge(G9, 3, 1);
	insertEdge(G9, 4, 6);
	insertEdge(G9, 4, 2);
	insertEdge(G9, 4, 1);
	insertEdge(G9, 5, 6);
	insertEdge(G9, 6, 5);
	insertEdge(G9, 6, 4);
	insertEdge(G9, 6, 3);
	printf("\n G의 인접 리스트 ");
	print_adjList(G9);  //G9의 인접 리스트를 확인용으로 출력
	 
	printf("\n\n///////////////\n\n너비 우선 탐색 >> ");
	BFS_adjList(G9, 0);     // 0번 정점인 정점 A에서 너비 우선 탐색 시작

	getchar();  return 0;
}
-----------------------------------------
 G의 인접 리스트 
                정점 A의 인접 리스트 -> B -> C
                정점 B의 인접 리스트 -> A -> D -> E
                정점 C의 인접 리스트 -> A -> E
                정점 D의 인접 리스트 -> B -> G
                정점 E의 인접 리스트 -> B -> C -> G
                정점 F의 인접 리스트 -> G
                정점 G의 인접 리스트 -> D -> E -> F

///////////////

너비 우선 탐색 >>  A B C D E G F

사용하는 이유:

1. 경로 및 구조 탐색: 그래프나 트리 구조에서 특정 경로를 찾거나 전체 구조를 탐색할 때 사용한다. DFS는 한 경로를 따라 최대한 깊게 들어가며, BFS는 레벨 단위로 탐색하여 너비 방향으로 탐색한다.
2. 문제 해결: 다양한 문제에서 최단 경로 찾기, 연결 요소 찾기, 사이클 탐지 등에 사용한다. 예를 들어, 미로 탐색, 지하 도로 네트워크 분석, 네트워크 트래픽 최적 경로 계산 등 다양한 분야에서 응용된다고 한다.
3. 그래프 알고리즘: 다양한 그래프 알고리즘의 기반이 되는데, 예를 들어, 최소 신장 트리(Minimum Spanning Tree) 알고리즘, 위상 정렬, 강한 연결 요소 찾기 등에서 DFS와 BFS를 사용한다.

중요도:

1. DFS의 중요성:
   • 재귀 구조 활용: DFS는 주로 재귀적인 구조로 구현되며, 트리 구조에서 더 간결하게 표현할 수 있다.
   • 깊이 우선 탐색의 특성: 특히 트리 구조에서는 한 경로를 완전히 탐색할 수 있어 재귀를 통한 간단한 구현이 가능하다.
2. BFS의 중요성:
   • 최단 경로 찾기: BFS는 레벨 단위로 탐색하므로, 최단 경로를 찾는 데 효과적이라고 한다.
   • 메모리 사용 측면: BFS는 큐를 사용하므로 상대적으로 적은 메모리를 사용한다고 한다.

사용되는 곳:

1. 네트워크 라우팅: 최적 경로를 찾기 위해 BFS에 사용.
2. 인공 지능: 게임 인공지능에서 상태 공간을 탐색하는 데 DFS와 BFS가 활용한다고 한다?
3. 데이터베이스 관리: 데이터베이스에서 관계형 데이터베이스의 인덱스 구조나 그래프 데이터베이스에서의 탐색에 사용한다.
4. 컴파일러 설계: 컴파일러에서 구문 분석 등에 사용한다.
5. 자연어 처리: 자연어 처리에서 문장 구조를 탐색하는 데 활용한다고한다.

잘못된 점 지적 부탁드립니다!