[알고리즘][그래프] 그래프의 탐색

chellchell·2020년 8월 25일

깊이 우선 탐색 너비 우선 탐색

알고리즘 이론

목록 보기

9/11

그래프의 탐색

그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문
모든 정점들을 특정한 순서에 따라 방문하는 알고리즘
어떤 간선이 사용되었는지, 어떤 순서로 정점들이 방문되었는지 → 그래프의 구조

-탐색 방법

깊이 우선 탐색(depth first search: DFS)
너비 우선 탐색(breath first search: BFS)

깊이 우선 탐색

순환 호출 이용
명시적인 스택 사용

인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색 구현

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define TRUE 1
#define FAlSE 0
#define MAX_VERTICES 50
typedef struct GraphType {
	int n;
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
}GraphType;
int visited[MAX_VERTICES];
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++;
}
//간선 삽입
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 dfs_mat(GraphType* g, int v) {
	int w;
	visited[v] = TRUE;
	printf("정점 %d -> ", v);
	for (w = 0; w < g->n; w++) {
		if (g->adj_mat[v][w] && !visited[w])
			dfs_mat(g, w);
	}
}
int main() {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	for (int i = 0; i < 4; i++)
		insert_vertex(g, i);
	insert_edge(g, 0, 1);
	insert_edge(g, 0, 2);
	insert_edge(g, 0, 3);
	insert_edge(g, 1, 2);
	insert_edge(g, 2, 3);

	printf("깊이 우선 탐색\n");
	dfs_mat(g, 0);
	printf("\n");
	free(g);
}

인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색 구현

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define TRUE 1
#define FAlSE 0
#define MAX_VERTICES 50

typedef struct GraphNode{
	int vertex;
	struct GraphNode* link;
}GraphNode;
typedef struct GraphType {
	int n;
	GraphNode* adj_list[MAX_VERTICES];
}GraphType;
int visited[MAX_VERTICES];
void init(GraphType* g) {
	int r;
	g->n = 0;
	for (r = 0; r < MAX_VERTICES; r++) {
			g->adj_list[r] = NULL;
	}
}
//정점 삽입
void insert_vertex(GraphType* g, int v) {
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}
//간선 삽입
void insert_edge(GraphType* g, int u, int v) {
	GraphNode* node;
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v;
	node->link = g->adj_list[u];
	g->adj_list[u] = node;

}
//인접 행렬로 표현된 그래프에 대한 깊이 탐색 그래프
void dfs_list(GraphType* g, int v) {
	GraphNode* w;
	visited[v] = TRUE;
	printf("정점 %d -> ", v);
	for (w = g->adj_list[v]; w ; w=w->link) {
		if (!visited[w->vertex])
			dfs_list(g, w->vertex);
	}
}
int main() {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	for (int i = 0; i < 4; i++)
		insert_vertex(g, i);
	insert_edge(g, 0, 1);
	insert_edge(g, 0, 2);
	insert_edge(g, 0, 3);
	insert_edge(g, 1, 2);
	insert_edge(g, 2, 3);

	printf("깊이 우선 탐색\n");
	dfs_list(g, 0);
	printf("\n");
	free(g);
}

c++ 구현

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int number = 7;
int c[7];
vector<int>a[8];
void dfs(int x) {
	if (c[x])
		return;
	c[x] = true;
	cout << x << ' ';
	for (int i = 0; i < a[i].size(); i++) {
		int y = a[x][i];
		dfs(y);
	}
}

너비 우선 탐색

가까운 거리에 있는 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조 필요 → 큐 사용

인접 행렬로 표현된 그래프에 대한 너비 우선 탐색 구현

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#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);
}
//초기화 함수
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->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
//삽입 함수
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;
}
//삭제 함수
element dequeue(QueueType* q) {
	if (is_empty(q))
		error("큐가 공백상태입니다\n");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->queue[q->front];
}
#define MAX_VERTICES 50
typedef struct GraphType {
	int n;//정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
}GraphType;
int visited[MAX_VERTICES];
//그래프 초기화
void graph_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++;
}
//간선 삽입 연산
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 bfs_mat(GraphType* g, int v) {
	int w;
	QueueType q;
	queue_init(&q);//큐 초기화
	visited[v] = TRUE;//정점 v 방문 표시
	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] = TRUE;//방문 표시
				printf("%d 방문 -> ", w);
				enqueue(&q, w);//방문한 정점을 큐에 저장
			}
		}
	}
}
int main(void) {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	graph_init(g);
	for (int i = 0; i < 6; i++) {
		insert_vertex(g, i);
	}
	insert_edge(g, 0, 2);
	insert_edge(g, 2, 1);
	insert_edge(g, 2, 3);
	insert_edge(g, 0, 4);
	insert_edge(g, 4, 5);
	insert_edge(g, 1, 5);

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

인접 리스트로 표현된 그래프에 대한 너비 우선 탐색 구현

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#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);
}
//초기화 함수
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->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
//삽입 함수
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;
}
//삭제 함수
element dequeue(QueueType* q) {
	if (is_empty(q))
		error("큐가 공백상태입니다\n");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->queue[q->front];
}
#define MAX_VERTICES 50
typedef struct GraphNode {
	int vertex;
	struct GraphNode* link;
}GraphNode;
typedef struct GraphType {
	int n;
	GraphNode* adj_list[MAX_VERTICES];
}GraphType;
void graph_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++;
}
void insert_edge(GraphType* g, int u, int v) {
	GraphNode* node;
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v;
	node->link = g->adj_list[u];
	g->adj_list[u] = node;
}
int visited[MAX_VERTICES];
void bfs_list(GraphType* g, int v) {
	GraphNode* w;
	QueueType q;
	queue_init(&q);//큐 초기화
	visited[v] = TRUE;//정점 v 방문 표시
	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] = TRUE;//방문 표시
				printf("%d 방문 -> ", w->vertex);
				enqueue(&q, w->vertex);//정점을 큐에 삽입 
			}
		}
	}
}
int main(void) {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	graph_init(g);
	for (int i = 0; i < 6; i++) {
		insert_vertex(g, i);
	}
	insert_edge(g, 0, 2);
	insert_edge(g, 2, 1);
	insert_edge(g, 2, 3);
	insert_edge(g, 0, 4);
	insert_edge(g, 4, 5);
	insert_edge(g, 1, 5);
	printf("너비 우선 탐색\n");
	bfs_list(g, 0);
	printf("\n");
	free(g);
}

c++ 구현

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int number = 7;
int c[7];
vector<int> a[8];

void bfs(int start) {
	queue<int>q;
	q.push(start);
	c[start] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		printf("%d ", x);
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (!c[y]) {
				q.push(y);
				c[y] = true;
			}
		}
	}
}