Data Structure – BFS (adjacency list & adjacency matrix)

By MasterCSE, Data Structure

BFS (너비 우선 탐색)

  1. 먼저 v를 방문한 후, v에 인접한 정점을 차례로 방문한다.
  2. 다음으로 두 번째 방문한 정점과 인접한 정점을 방문하고, 이후 세 번째 방문한 정점과 인접한 정점을 방문한다.
  3. 이 과정을 반복한다.

각 정점을 방문할 때 그에 인접한 정점을 큐에 삽입하고,
다음으로 방문할 정점은 큐에서 삭제하여 얻는다.

(방문: 큐에 저장, visited 원소 값=1)

adjacency list Version (인접 리스트 버전)

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

#define MAX_QUEUE_SIZE 10
typedef int element;
typedef struct {
	element data[MAX_QUEUE_SIZE];
	int front, rear;
}QueueType;
typedef QueueType* QueueType_ptr;
QueueType q;

void qinit(QueueType_ptr q) {
	q->front = 0;
	q->rear = 0;
}
int is_empty(QueueType_ptr q) {
	if (q->front == q->rear)
		return 1;
	else
		return 0;
};
int is_full(QueueType_ptr q) {
	if ((q->rear + 1) % MAX_QUEUE_SIZE == q->front)
		return 1;
	else
		return 0;
}
void enqueue(QueueType_ptr q, int item) {
	if (!is_full(q)) {
		q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
		q->data[q->rear] = item;
	}
	else
		printf("큐가 꽉 찼습니다");
}
int dequeue(QueueType_ptr q) {
	if (!is_empty(q)) {
		q->front = (q->front + 1) % MAX_QUEUE_SIZE;
		return q->data[q->front];
	}
	else
		printf("큐가 비어 있습니다");
}


typedef struct GraphNode {
	int vertex;
	struct GraphNode* link;
}GraphNode;

#define MAX_VERTICES 50

typedef struct GraphType {
	int n; // 정점의 개수
	GraphNode* adj_list[MAX_VERTICES];
}GraphType;

// 그래프 초기화
void init(GraphType* g) {
	int v;
	g->n = 0;
	for (v = 0; v < MAX_VERTICES; v++)
		g->adj_list[v] = NULL;
}

// 정점 삽입 연산
void insert_vertex(GraphType* g, int v) {
	if ((g->n) + 1 > MAX_VERTICES) {
		fprintf(stderr, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}

// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType* g, int u, int v) {
	GraphNode* node;
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	if (g->adj_list[u] == NULL) { // insert_first
		node = (GraphNode*)malloc(sizeof(GraphNode));
		node->vertex = v;
		node->link = g->adj_list[u];
		g->adj_list[u] = node;
	}
	else { //insert_last
		node = g->adj_list[u];
		while (node->link != NULL)
			node = node->link;
		node->link = (GraphNode*)malloc(sizeof(GraphNode));
		node->link->vertex = v;
		node->link->link = NULL;
	}
}

void print_adj_list(GraphType* g) {
	for (int i = 0; i < g->n; i++) {
		GraphNode* p = g->adj_list[i];
		printf("정정 %d의 인접 리스트", i);
		while (p != NULL) {
			printf("-> %d", p->vertex);
			p = p->link;
		}
		printf("\n");
	}
}

// 너비 우선 탐색 (BFS)
int visited[MAX_VERTICES];
void BFS(GraphType* g, int v) {
	GraphNode* w;
	QueueType_ptr q = (QueueType_ptr)malloc(sizeof(QueueType));

	qinit(q);
	visited[v] = 1; // TRUE
	printf("%d 방문 -> ", v);
	enqueue(q, v);
	while (!is_empty(q)) {
		v = dequeue(q);
		for (w = g->adj_list[v]; w; w = w->link) {
			if (!visited[w->vertex]) {
				visited[w->vertex] = 1;
				printf("%d 방문 -> ", w->vertex);
				enqueue(q, w->vertex);
			}
		}
	}
}

int main() {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	// 정점 삽입 
	for (int i = 0; i <= 7; i++)
		insert_vertex(g, i);

	// 에지 삽입 
	// 인접 리스트는 오름차순으로 정렬한다. insert_edge(g,u정점,u랑 인접한 v정점), (v가 작은 순서대로 삽입) 
	insert_edge(g, 0, 1);
	insert_edge(g, 0, 2);
	insert_edge(g, 1, 0);
	insert_edge(g, 1, 3);
	insert_edge(g, 1, 4);
	insert_edge(g, 2, 0);
	insert_edge(g, 2, 5);
	insert_edge(g, 2, 6);
	insert_edge(g, 3, 1);
	insert_edge(g, 3, 7);
	insert_edge(g, 4, 1);
	insert_edge(g, 4, 7);
	insert_edge(g, 5, 2);
	insert_edge(g, 5, 7);
	insert_edge(g, 6, 2);
	insert_edge(g, 6, 7);
	insert_edge(g, 7, 3);
	insert_edge(g, 7, 4);
	insert_edge(g, 7, 5);
	insert_edge(g, 7, 6);

	print_adj_list(g);

	printf("\n너비 우선 탐색\n");
	BFS(g, 0);
	printf("end\n");
	free(g);
	return 0;
}

adjacency matrix Version (인접 행렬 버전)

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

#define MAX_QUEUE_SIZE 10
typedef int element;
typedef struct {
	element data[MAX_QUEUE_SIZE];
	int front, rear;
}QueueType;
typedef QueueType* QueueType_ptr;
QueueType q;

void qinit(QueueType_ptr q) {
	q->front = 0;
	q->rear = 0;
}
int is_empty(QueueType_ptr q) {
	if (q->front == q->rear)
		return 1;
	else
		return 0;
};
int is_full(QueueType_ptr q) {
	if ((q->rear + 1) % MAX_QUEUE_SIZE == q->front)
		return 1;
	else
		return 0;
}
void enqueue(QueueType_ptr q, int item) {
	if (!is_full(q)) {
		q->rear = (q->rear + 1) % 5;
		q->data[q->rear] = item;
	}
	else
		printf("큐가 꽉 찼습니다");
}
int dequeue(QueueType_ptr q) {
	if (!is_empty(q)) {
		q->front = (q->front + 1) % 5;
		return q->data[q->front];
	}
	else
		printf("큐가 비어 있습니다");
}

#define MAX_VERTICES 50
typedef struct GraphType {
	int n; // 정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
}GraphType;

// 그래프 초기화
void init(GraphType* g) {
	int r, c;
	g->n = 0;
	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, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}

// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType* g, int start, int end) {
	if (start >= g->n || end >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	g->adj_mat[start][end] = 1;
	g->adj_mat[end][start] = 1;
}

void print_adj_list(GraphType* g) {
	for (int i = 0; i < g->n; i++) {
		for (int j = 0; j < g->n; j++) {
			printf("%2d ", g->adj_mat[i][j]);
		}
		printf("\n");
	}
}

// 너비 우선 탐색 (BFS)
int visited[MAX_VERTICES];
void BFS(GraphType* g, int v) {
	int w;
	QueueType_ptr q = (QueueType_ptr)malloc(sizeof(QueueType));

	qinit(q);
	visited[v] = 1; // TRUE
	printf("%d 방문 -> ", v);
	enqueue(q, v);
	while (!is_empty(q)) {
		v = dequeue(q);
		for (w = 0; w < g->n; w++) {
			if (g->adj_mat[v][w] && !visited[w]) {
				visited[w] = 1;
				printf("%d 방문 -> ", w);
				enqueue(q, w);
			}
		}
	}
}

int main() {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	// 정점 삽입 
	for (int i = 0; i <= 7; i++)
		insert_vertex(g, i);

	// 에지가 있으면 인접 행렬에 삽입  
	insert_edge(g, 0, 1);
	insert_edge(g, 0, 2);
	insert_edge(g, 1, 3);
	insert_edge(g, 1, 4);
	insert_edge(g, 3, 7);
	insert_edge(g, 4, 7);
	insert_edge(g, 7, 5);
	insert_edge(g, 5, 2);
	insert_edge(g, 2, 6);
	insert_edge(g, 7, 6);

	print_adj_list(g);

	printf("\n너비 우선 탐색\n");
	BFS(g, 0);
	printf("end\n");
	free(g);
	return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *