[Data Structure] BFS vs DFS (인접 리스트)

BFS(stack) VS DFS(queue)

• BFS : 깊이 우선 탐색 - stack or 순환으로 구현
• DFS : 너비 우선 탐색 - queue로 구현

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

// 인접 리스트(BFS - 스택 / DFS - 큐)

#define MAX_VERTEX 50
#define TRUE 1
#define FALSE 0

typedef int element;

// 그래프 구현

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

typedef struct graph {
	int n;
	graphnode* list[MAX_VERTEX];
}graph;

int visited[MAX_VERTEX];

void init_visited(int arr[]) {
	for (int i = 0; i < MAX_VERTEX; i++) {
		arr[i] = FALSE;
	}
}

graph* createG() {
	return (graph*)malloc(sizeof(graph));
}

void init_graph(graph* g) {
	g->n = 0;
	for (int i = 0; i < MAX_VERTEX; i++)
		g->list[i] = NULL;
}

int is_fullG(graph* g) {
	return g->n == MAX_VERTEX;
}

int bool_vertex(graph* g, element v) {
	int flag = FALSE;
	for (int i = 0; i < g->n; i++) {
		if (g->list[i]->vertex == v)
			flag = TRUE;
	}
	if (flag == TRUE) return TRUE;
	else return FALSE;
}

void insert_vertex(graph* g, element v) {
	if (is_fullG(g)) {
		fprintf(stderr, "그래프 정점의 개수가 MAX에 도달했습니다\n\n");
		return;
	}
	else if (bool_vertex(g, v) == TRUE) {
		fprintf(stderr, "해당 정점은 이미 그래프에 존재합니다\n\n");
		return;
	}
	graphnode* new_node = (graphnode*)malloc(sizeof(graphnode));
	new_node->vertex = v; new_node->link = NULL;
	g->list[g->n++] = new_node;
}

void insert_edge(graph* g, element start, element end) {
	if (bool_vertex(g, start) == FALSE || bool_vertex(g, end) == FALSE) {
		fprintf(stderr, "해당 정점은 그래프에 없기 때문에 edge를 insert할 수 없습니다\n\n");
		return;
	}
	graphnode* new_node = (graphnode*)malloc(sizeof(graphnode));
	new_node->vertex = end;
	new_node->link = g->list[start]->link;
	g->list[start]->link = new_node;
}

void print_list(graph* g) {
	graphnode* p;
	for (int i = 0; i < g->n; i++) {
		p = g->list[i];
		printf("정점 %d의 인접 리스트 : ", i);
		while (p != NULL) {
			printf("%d -> ", p->vertex);
			p = p->link;
		}
		printf("NULL\n");
	}
}

// 큐 구현
#define MAX_QUEUE_SIZE 50

typedef struct queue {
	int front, rear;
	element queue[MAX_QUEUE_SIZE];
}queue;

queue* createQ() {
	return (queue*)malloc(sizeof(queue));
}

void init_queue(queue* q) {
	q->front = q->rear = 0;
}

int is_emptyQ(queue* q) {
	return q->front == q->rear;
}

int is_fullQ(queue* q) {
	return q->front == (q->rear + 1) % MAX_QUEUE_SIZE;
}

int bool_queue(queue* q, element v) {
	int flag = FALSE;
	for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
		if (q->queue[i] == v)
			flag = TRUE;
	}
	if (flag == TRUE) return TRUE;
	else return FALSE;
}

void enqueue(queue* q, element v) {
	if (is_fullQ(q)) {
		fprintf(stderr, "Error : Queue is full\n\n");
		return;
	}
	else if (bool_queue(q, v) == TRUE) {
		fprintf(stderr, "해당 정점은 이미 큐에 존재합니다\n\n");
		return;
	}
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->queue[q->rear] = v;
}

element dequeue(queue* q) {
	if (is_emptyQ(q)) {
		fprintf(stderr, "Error : Queue is empty\n\n");
		return;
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->queue[q->front];
}

// 스택 구현
#define MAX_STACK_SIZE 50

typedef struct stack {
	int top;
	element stack[MAX_STACK_SIZE];
}stack;

stack* createS() {
	return (stack*)malloc(sizeof(stack));
}

void init_stack(stack* s) {
	s->top = -1;
}

int is_fullS(stack* s) {
	return s->top == MAX_STACK_SIZE - 1;
}

int is_emptyS(stack* s) {
	return s->top == -1;
}

int bool_stack(stack* s, element v) {
	int flag = FALSE;
	for (int i = 0; i < MAX_STACK_SIZE; i++) {
		if (s->stack[i] == v)
			flag = TRUE;
	}
	if (flag == TRUE) return TRUE;
	else return FALSE;
}

void push(stack* s, element v) {
	if (is_fullS(s)) {
		fprintf(stderr, "Error : Stack is full\n\n");
		return;
	}
	else if (bool_stack(s, v) == TRUE) {
		fprintf(stderr, "해당 정점은 이미 스택에 존재합니다\n\n");
		return;
	}
	s->stack[++s->top] = v;
}

element pop(stack* s) {
	if (is_emptyS(s)) {
		fprintf(stderr, "Error : Stack is empty\n\n");
		return;
	}
	return s->stack[s->top--];
}

void bfs_list_queue(graph* g, element v) {
	// BFS - 너비 우선 탐색
	queue* q; 
	q = createQ(); init_queue(q);

	enqueue(q, v);
	visited[v] = TRUE;
	graphnode* w; // v의 인접 정점node
	while (!is_emptyQ(q)) {
		v = dequeue(q);
		printf("정점 %d -> ", v);
		for (w = g->list[v]; w; w = w->link) {
			if (visited[w->vertex] == FALSE && bool_queue(q, w->vertex) == FALSE) {
				enqueue(q, w->vertex);
				visited[w->vertex] = TRUE;
			}
		}
	}
}

void dfs_list_stack(graph* g, element v) {
	// DFS - 깊이 우선 탐색
	stack* s;
	s = createS(); init_stack(s);

	push(s, v);
	visited[v] = TRUE;
	graphnode* w;
	while (!is_emptyS(s)) {
		v = pop(s);
		printf("정점 %d -> ", v);
		for (w = g->list[v]; w; w = w->link) {
			if (visited[w->vertex] == FALSE && bool_stack(s, w->vertex) == FALSE) {
				push(s, w->vertex);
				visited[w->vertex] = TRUE;
			}
		}
	}
}

int main(void) {
	graph* g1, * g2;
	g1 = createG(); init_graph(g1);
	g2 = createG(); init_graph(g2);

	printf("----------------------------\n");
	printf("V : {0, 1, 2, 3, 4}\n");
	printf("E : {(0, 1), (0, 2), (0, 4), (1, 2), (2, 3), (2, 4), (3, 4)}\n\n");
	for (int i = 0; i < 5; i++)
		insert_vertex(g1, i);
	insert_edge(g1, 0, 1);
	insert_edge(g1, 1, 0);
	insert_edge(g1, 0, 2);
	insert_edge(g1, 2, 0);
	insert_edge(g1, 0, 4);
	insert_edge(g1, 4, 0);
	insert_edge(g1, 1, 2);
	insert_edge(g1, 2, 1);
	insert_edge(g1, 2, 3);
	insert_edge(g1, 3, 2);
	insert_edge(g1, 2, 4);
	insert_edge(g1, 4, 2);
	insert_edge(g1, 3, 4);
	insert_edge(g1, 4, 3);

	print_list(g1);

	printf("\n깊이 우선 탐색 (DFS - Stack)\n");
	printf("시작 정점(0) : "); dfs_list_stack(g1, 0); printf("\n"); init_visited(visited);
	printf("시작 정점(1) : "); dfs_list_stack(g1, 1); printf("\n"); init_visited(visited);
	printf("시작 정점(2) : "); dfs_list_stack(g1, 2); printf("\n"); init_visited(visited);
	printf("시작 정점(3) : "); dfs_list_stack(g1, 3); printf("\n"); init_visited(visited);
	printf("시작 정점(4) : "); dfs_list_stack(g1, 4); printf("\n"); init_visited(visited);

	printf("\n너비 우선 탐색 (BFS - Queue)\n");
	printf("시작 정점(0) : "); bfs_list_queue(g1, 0); printf("\n"); init_visited(visited);
	printf("시작 정점(1) : "); bfs_list_queue(g1, 1); printf("\n"); init_visited(visited);
	printf("시작 정점(2) : "); bfs_list_queue(g1, 2); printf("\n"); init_visited(visited);
	printf("시작 정점(3) : "); bfs_list_queue(g1, 3); printf("\n"); init_visited(visited);
	printf("시작 정점(4) : "); bfs_list_queue(g1, 4); printf("\n"); init_visited(visited);

	printf("\n----------------------------\n");
	printf("V : {0, 1, 2, 3, 4, 5, 6, 7, 8}\n");
	printf("E : {(0, 1), (0, 2), (0, 3), (1, 4), (2, 5), (2, 6), (3, 7), (5, 8)}\n\n");
	for (int i = 0; i < 9; i++)
		insert_vertex(g2, i);

	insert_edge(g2, 0, 1);
	insert_edge(g2, 1, 0);
	insert_edge(g2, 0, 2);
	insert_edge(g2, 2, 0);
	insert_edge(g2, 0, 3);
	insert_edge(g2, 3, 0);
	insert_edge(g2, 1, 4);
	insert_edge(g2, 4, 1);
	insert_edge(g2, 2, 5);
	insert_edge(g2, 5, 2);
	insert_edge(g2, 2, 6);
	insert_edge(g2, 6, 2);
	insert_edge(g2, 3, 7);
	insert_edge(g2, 7, 3);
	insert_edge(g2, 5, 8);
	insert_edge(g2, 8, 5);

	print_list(g2);

	printf("\n깊이 우선 탐색 (DFS - Stack)\n");
	printf("시작 정점(0) : "); dfs_list_stack(g2, 0); printf("\n"); init_visited(visited);
	printf("시작 정점(1) : "); dfs_list_stack(g2, 1); printf("\n"); init_visited(visited);
	printf("시작 정점(2) : "); dfs_list_stack(g2, 2); printf("\n"); init_visited(visited);
	printf("시작 정점(3) : "); dfs_list_stack(g2, 3); printf("\n"); init_visited(visited);
	printf("시작 정점(4) : "); dfs_list_stack(g2, 4); printf("\n"); init_visited(visited);
	printf("시작 정점(5) : "); dfs_list_stack(g2, 5); printf("\n"); init_visited(visited);
	printf("시작 정점(6) : "); dfs_list_stack(g2, 6); printf("\n"); init_visited(visited);
	printf("시작 정점(7) : "); dfs_list_stack(g2, 7); printf("\n"); init_visited(visited);
	printf("시작 정점(8) : "); dfs_list_stack(g2, 8); printf("\n"); init_visited(visited);

	printf("\n너비 우선 탐색 (BFS - Queue)\n");
	printf("시작 정점(0) : "); bfs_list_queue(g2, 0); printf("\n"); init_visited(visited);
	printf("시작 정점(1) : "); bfs_list_queue(g2, 1); printf("\n"); init_visited(visited);
	printf("시작 정점(2) : "); bfs_list_queue(g2, 2); printf("\n"); init_visited(visited);
	printf("시작 정점(3) : "); bfs_list_queue(g2, 3); printf("\n"); init_visited(visited);
	printf("시작 정점(4) : "); bfs_list_queue(g2, 4); printf("\n"); init_visited(visited);
	printf("시작 정점(5) : "); bfs_list_queue(g2, 5); printf("\n"); init_visited(visited);
	printf("시작 정점(6) : "); bfs_list_queue(g2, 6); printf("\n"); init_visited(visited);
	printf("시작 정점(7) : "); bfs_list_queue(g2, 7); printf("\n"); init_visited(visited);
	printf("시작 정점(8) : "); bfs_list_queue(g2, 8); printf("\n"); init_visited(visited);

	return 0;
}

G1 / G2

G1 결과

G2 결과