그래프 - 너비우선탐색

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다. 

너비우선탐색 Breath First Search : BFS

시작 정점으로부터
가장 가까운 정점을 먼저 방문하고
차차 멀리 떨어져있는 정점을 방문한다. 

다시 말해서,

 

가까운 거리에 있는 정점들을 
차례로 저장한 후
넣은 순서대로 꺼내서 방문하는 방식이다.

 

이를 위해서, 자료구조 Queue 큐를 사용한다. 

 

#알고리즘

breath_first_search(v):
	v를 방문했다고 표시
	큐 Queue에 정점 v를 삽입
	while (Queue가 공백이 아니면) do
		w <- Queue.pop()
		for all u in (w에 인접한 정점) do
			if (u 아직 방문안했으면)
				then u를 Queue에 삽입
				u 방문했다고 표시

 

1. 인접행렬로 bfs 탐색 순서 알아내기

#코드

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

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10

#define MAX_VERTICES 50

typedef int element;
typedef struct
{
	element queue[MAX_QUEUE_SIZE];	
	int front, rear;
} QueueType;
// 오류 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
// queue 초기화 함수
void queue_init(QueueType* q)
{
	q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType* q)
{
	return q->front == q->rear;
}
// 포화 상태 검출 함수
int is_full(QueueType* q)
{
	return (q->front == (q->rear + 1) % MAX_QUEUE_SIZE);
}
// 삽입 함수
void enqueue(QueueType* q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다.\n");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->queue[q->rear] = item;
}
// 삭제 함수
int dequeue(QueueType* q)
{
	if (is_empty(q))
		error("큐가 비어있습니다.\n");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->queue[q->front];
}

/********************그래프 선언**********************/
typedef struct GraphType {
	int n;		// 정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];

// 그래프 초기화
void graph_init(GraphType* g)
{
	g->n = 0;
	int r, c;
	for (r = 0; r < MAX_VERTICES; r++) 
	{
		for (c = 0; c < MAX_VERTICES; c++)
		{
			g->adj_mat[r][c] = 0;
		}
	}
}
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
	if ((g->n + 1) > MAX_VERTICES) {
		fprintf(stderr, "그래프: 정점의 개수 초과\n");
		return;
	}
	g->n++;
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int u, int v)
{
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류\n");
		return;
	}
	g->adj_mat[u][v] = 1;
	g->adj_mat[v][u] = 1;
}
// 너비우선탐색 함수
void bfs_mat(GraphType* g, int v)
{ // v: 시작정점
	QueueType q;

	queue_init(&q);
	// 1. 정점 v를 방문했다고 표시 및 출력
	visited[v] = TRUE;
	printf("%d 방문 -> ", v);
	// 2. 정점 v를 큐에 삽입하고 시작
	enqueue(&q, v);
	while (!is_empty(&q)) // 큐가 공백이 아닐 때까지 진행
	{
		// 3. 큐에서 정점 추출; 주변부터 차차 공략해가는 과정
		v = dequeue(&q);
		for (int i = 0; i < g->n; i++)
		{	
			if (g->adj_mat[v][i] && visited[i] == FALSE) 
			{	// 4. 추출한 정점 v의 인접 정점 중에서 아직 방문 안한 정점은
				// 5. 방문했다고 표시하고
				visited[i] = TRUE;
				printf("%d 방문 -> ", i);
				// 6. 큐에 추가
				enqueue(&q, i);
			}
		}
	}
}
int main()
{
	GraphType* g = (GraphType*)malloc(sizeof(GraphType));
	graph_init(g);
	for (int i = 0; i < 5; i++) {
		insert_vertex(g, i);
	}
	insert_edge(g, 0, 1);
	insert_edge(g, 0, 2);
	insert_edge(g, 0, 3);
	insert_edge(g, 1, 4);
	insert_edge(g, 1, 2);
	insert_edge(g, 1, 0);
	insert_edge(g, 2, 0);
	insert_edge(g, 2, 1);
	insert_edge(g, 3, 0);
	insert_edge(g, 3, 4);
	insert_edge(g, 4, 1);
	insert_edge(g, 4, 3);
	
	printf("너비우선 탐색\n");
	bfs_mat(g, 2);
	printf("\n");
	free(g);
	return 0;
}

# 결과

# 그림으로 이해하기

시작정점을 2번으로 너비우선탐색을 하면, 아래와 같다.

즉, 방문 순서는 2->0->1->3->4 이다.

2. 인접리스트로 bfs 탐색 순서 알아내기

#코드

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICE 50
#define TRUE 1
#define FALSE 0

/********************큐 선언*******************/

#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct
{
	element queue[MAX_QUEUE_SIZE];
	int front, rear;
} QueueType;
// 오류 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
// queue 초기화 함수
void queue_init(QueueType* q)
{
	q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType* q)
{
	return q->front == q->rear;
}
// 포화 상태 검출 함수
int is_full(QueueType* q)
{
	return (q->front == (q->rear + 1) % MAX_QUEUE_SIZE);
}
// 삽입 함수
void enqueue(QueueType* q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다.\n");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->queue[q->rear] = item;
}
// 삭제 함수
int dequeue(QueueType* q)
{
	if (is_empty(q))
		error("큐가 비어있습니다.\n");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->queue[q->front];
}

/******************그래프 선언*******************/

// 각 정점마다 하나의 연결리스트가 필요하다
// 정점의 개수만큼의 포인터 배열(헤더노드)이 필요하다
// 하나의 노드 ==> GraphNode
// 포인터 배열의 이름 ==> adj_list

typedef struct GraphNode {		// 하나의 노드
	int vertex;					// 데이터 필드: 정점의 값을 저장할 곳
	struct GraphNode* link;		// 링크 필드: 인접정점을 가리킬 포인터 
	// 가리킬 변수의 타입이 하나의 정점이기 때문에 GraphNode 타입으로 선언해야 한다.
} GraphNode;

typedef struct GraphType {		// 그래프 전체
	int n;						// 해당 그래프의 정점의 개수
	GraphNode* adj_list[MAX_VERTICE]; // 헤더노드 집합; 각 연결 리스트의 첫번째 노드를 가리킴.
} GraphType;

int visited[MAX_VERTICE];

// 그래프 초기화
void init_adjList(GraphType* g)
{
	int v;
	g->n = 0; //그래프 정점의 개수 0으로 초기화
	for (v = 0; v < MAX_VERTICE; v++)
	{
		g->adj_list[v] = NULL;
	}
}
// 정점 삽입 연산: 값이 v인 정점을 삽입한다.
void insert_vertex_adjList(GraphType* g, int v)
{ // v: 삽입합 노드의 값
	if ((g->n) + 1 > MAX_VERTICE)
	{
		fprintf(stderr, "그래프: 정점의 개수 초과\n");
		return;
	}
	g->n++;
}
// 간선 삽입 연산: 정점 u와 v를 연결한다 : 정점 u에 간선 (u,v)를 맨 처음에 삽입
void insert_edge_adjList(GraphType* g, int u, int v)
{
	if (u >= g->n || v >= g->n)
	{
		fprintf(stderr, "그래프: 정점 번호 오류\n");
		return;
	}
	GraphNode* node = (GraphNode*)malloc(sizeof(GraphNode));
	if (node == NULL) {
		printf("malloc 오류: 할당 안됨\n");
		return;
	}
	node->vertex = v;
	node->link = g->adj_list[u];
	g->adj_list[u] = node;	// adj_list의 한 원소는 GraphNode를 가리키는 포인터 타입이니까 할당 가능
}
// 너비우선 탐색 연결리스트로 구현
void bfs_list(GraphType* g, int v)
{
	GraphNode* u;
	QueueType q;

	queue_init(&q);
	// 1. 시작정점 v 방문했음 표시 및 출력
	visited[v] = TRUE;
	printf("%d 방문 -> ", v);
	// 2. 시작정점 v를 q 에 삽입하고 시작 (그래야 while문이 돌아간다)
	enqueue(&q, v);
	
	while (!is_empty(&q)) // 큐가 공백이 아닐 때까지
	{
		// 3. 큐에서 정점을 추출한다.
		v = dequeue(&q);
		// 4. 정점 v의 인접정점 중에서
		for (u = g->adj_list[v]; u != NULL; u = u->link)
		{	// 5. 아직 방문 안한 정점 u 에 대해
			if (!visited[u->vertex])
			{
				// 6. 방문했다고 표시하고, 큐에 삽입한다
				visited[u->vertex] = TRUE;
				printf("%d 방문 -> ", u->vertex);
				enqueue(&q, u->vertex);
			}
			
		}
	}
}
int main()
{
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init_adjList(g);
	for (int i = 0; i < 5; i++) {
		insert_vertex_adjList(g, i);
	}
	insert_edge_adjList(g, 0, 1);
	insert_edge_adjList(g, 0, 2);
	insert_edge_adjList(g, 0, 3);
	insert_edge_adjList(g, 1, 4);
	insert_edge_adjList(g, 1, 2);
	insert_edge_adjList(g, 1, 0);
	insert_edge_adjList(g, 2, 0);
	insert_edge_adjList(g, 2, 1);
	insert_edge_adjList(g, 3, 0);
	insert_edge_adjList(g, 3, 4);
	insert_edge_adjList(g, 4, 1);
	insert_edge_adjList(g, 4, 3);

	printf("너비 우선 탐색\n");
	bfs_list(g, 2);
	printf("\n");

	free(g);
	return 0;
}

#결과

#그림으로 이해하기

이 그래프에 대해서, 연결 리스트로 표현하면 아래와 같다.

단, 주의해야 할 점은

연결리스트로 표현할 때 작은 값부터 추가하되,

각 연결 리스트의 맨 앞에 추가한다는 점이다. 

이에 대해서 너비우선탐색을 실시하면 다음과 같다. 

너비우선 탐색 순서

즉, 너비 우선 탐색은 내 주변에 있는 정점들을 모두 방문한 다음에

좀 더 멀리는 정점들을 차차 발견해 나가는 방식이다.

 

3. 시간 복잡도

인접리스트로 표현된 경우에는, O(n+e) 

인접 행렬로 표현된 경우에는, O(n^2) 시간이 걸린다.

 

희소 그래프를 사용할 경우에는 인접리스트를 사용하는 것이 더 효율적이다.