[자료구조]- 그래프1 인접 행렬/인접 리스트/DFS/BFS

박준수·2022년 8월 8일

[자료구조]

목록 보기

14/17

그래프란..

객체 사이의 연결 관계를 표현할 수 있는 자료구조다.

도로
미로
선수과목

그래프 정의와 용어

정의 : 정점과 간선들의 유한 집합이다.

정점 : 여러 가지 특성을 가질 수 잇는 객체 -> 노드
간선 : 이러한 정점들 간의 관계 -> 링크

용어

무방향 그래프 : 간선을 통해서 양방향으로 갈 수 있음
방향 그래프 : 간선에 방향성이 존재함으로 갈 수 있는 방향을 표시
네트워크(가중치 그래프) : 간선에 가중치, 비용을 할당한 그래프
부분 그래프 : 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프
정점의 차수 : 간선에 의해 직접 연결된 정점의 수
단순 경로 : 경로 중에서 반복되는 간선이 없는 경로
사이클 : 단순 경로의 시작 정점과 종료 정점이 동일한 경로
연결 그래프 : 무방향 그래프 중 모든 정점쌍에 대해 항상 경로가 존재
비연결 그래프 : 연결 그래프의 반대
완전 그래프 : 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프

그래프 추상 데이터 타입

create_graph() -> 그래프를 생성한다.
init(g) = 그래프 g를 초기화한다.
insert_vertex(g,v) -> 그래프 g에 정점 v를 삽입한다.
insert_edge(g,u,v) -> 그래프 g에 간선 (u,v)를 삽입한다.
delete_vertex(g,v) -> 그래프 g의 정점 v를 삭제한다.
delete_edge(g,u,v) -> 그래프 g의 간선 (u,v)를 삭제한다.
is_empty(g) -> 그래프 g가 공백 상태인지 확인한다.

그래프의 표현 방법

인접 행렬 : 2차원 배열을 사용하여 그래프를 표현
인접 리스트 : 연결 리스트를 사용하는 그래프를 표현

인접 행렬

if(간선 (i,j)가 그래프에 존재) -> M[i][j] = 1(무방향 그래프의 간선 (i,j)는 정점 i에서 정점 j로 서로가 연결이 되있음을 의미)
그렇지 않으면 -> M[i][j] = 0

n개의 정점을 가지는 그래프는 간선의 수에 무관하게 항상 $n^2$ 개의 메모리 공간이 필요하다. 즉 그래프에 간선이 많이 존재하는 밀집 그래프를 표현하는 경우에 적합하나 그래프 내에 적은 숫자의 간선 만을 가지는 희소 그래프의 경우에는 메모리의 낭비가 크다.

시간 복잡도
- 두 정점을 연결하는 간선의 존재 여부 : O(1)
- 정점의 차수 : 인접행렬의 행, 열을 조사 -> O(n)
- 그래프에 존재하는 모든 간선의 수 : 인접 행렬 전체를 조사 -> O( $n^2$ )

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

#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++;
}
// 간선 삽입 연산
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_mat(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");
	}
}

void 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);
	print_adj_mat(g);

	free(g);
}

인접 리스트

각 연결 리스트들은 헤더 노드를 가지고 있고 이 헤더 노드들은 하나의 배열로 구성되어 있다. 각각의 연결 리스트에 정점이 입력되는 순서에 따라 연결 리스트 내에서 정점들의 순서가 달라질수 있으므로 일관성을 유지하기 위하여 오름차순으로 연결된다고 가정하자.

시간 복잡도
- 그래프에 간선 (i,j)의 존재 여부나 정점 i의 차수 : 인접 리스트에서의 정점 i의 연결 리스트를 탐색 -> 연결리스트에 있는 노드의 수만큼 필요
- n개의 정점과 e개의 간선을 가진 그래프에서 전체 간선의 수 : O(n+e)

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

#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 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;
	}
	node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v;
	node->link = g->adj_list[u];	//노드의 위치는 상관없으므로 
	g->adj_list[u] = node;			// 삽입을 쉽게 하기 위하여 insert_first
}

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");
	}
}

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, 1, 0);
	insert_edge(g, 0, 2);
	insert_edge(g, 2, 0);
	insert_edge(g, 0, 3);
	insert_edge(g, 3, 0);
	insert_edge(g, 1, 2);
	insert_edge(g, 2, 1);
	insert_edge(g, 2, 3);
	insert_edge(g, 3, 2);
	print_adj_list(g);
	free(g);
	return 0;
}

그래프의 탐색

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

깊이 우선 탐색(DFS: depth first search)
- ex) 트리 탐색 : 시작 정점에서 한 반향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색
너비 우선 탐색(BFS: breath first search)
- ex) 트리 탐색 : 시작 정점으로부터 가가운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문

깊이 우선 탐색

순환 호출 : 인접 행렬, 인접 리스트
스택

순환호출 - 인접 행렬, 인접 리스트

정점 방문 여부를 기록하기 위해 배열 visited를 사용. False로 초기화 -> 방문 될때마다 TRUE로 변경

// 인접 행렬 //
#include <stdio.h>
#include <stdlib.h>

#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;		// 정점 v의 방문 표시 
	printf("정점 %d -> ", v);		// 방문한 정점 출력
	for (w = 0; w<g->n; w++) 		// 인접 정점 탐색
		if (g->adj_mat[v][w] && !visited[w])
			dfs_mat(g, w);	//정점 w에서 DFS 새로 시작
}

int main(void)
{
	GraphType *g;
	g = (GraphType *)malloc(sizeof(GraphType));
	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, 2);
	insert_edge(g, 4, 3);
	insert_edge(g, 1, 4);

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

인접 행렬이므로 DFS의 시간 복잡도는 O( $N^2$ )
///////////////////////////////////////////////////

// 인접 리스트 //
#include <stdio.h>
#include <stdlib.h>
#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 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;
	}
	node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v;
	node->link = g->adj_list[u];
	g->adj_list[u] = node;
}

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");
	}
}

// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_list(GraphType* g, int v)
{
	GraphNode* w;
	visited[v] = TRUE;   		// 정점 v의 방문 표시 
	printf("정점 %d -> ", v);		// 방문한 정점 출력
	for (w = g->adj_list[v]; w; w = w->link)// 인접 정점 탐색 
		if (!visited[w->vertex])
			dfs_list(g, w->vertex); //정점 w에서 DFS 새로 시작
}

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, 1, 0);
	insert_edge(g, 0, 2);
	insert_edge(g, 2, 0);
	insert_edge(g, 0, 3);
	insert_edge(g, 3, 0);
	insert_edge(g, 1, 2);
	insert_edge(g, 2, 1);
	insert_edge(g, 2, 3);
	insert_edge(g, 3, 2);
	print_adj_list(g); //인접리스트 그래프 생성 결과
	printf("\n");
	dfs_list(g, 0);		// dfs 인접리스트 탐색 결과

	free(g);
	return 0;
}

인접 리스트이므로 시간복잡도는 O(n+e)

너비 우선 탐색

가까운 거리에 있는 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐가 필요하다. 큐에 정점을 꺼내서 정점을 방문하고 인접 정점들을 큐에 추가하는 형식. 즉 거리가 0인 시작 정점을 방문한 후 거리가 1,2,3....인 정점 등의 순서로 방문한다.

// 인접 행렬 //
#include <stdio.h>
#include <stdlib.h>

#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("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->queue[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	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<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, 2);
	insert_edge(g, 1, 4);
	insert_edge(g, 3, 4);

	printf("너비 우선 탐색\n");
	bfs_mat(g, 2);	// 정점 2부터 탐색
	printf("\n");
	free(g);
	return 0;
}

인접 행렬이므로 시간복잡도는 O( $n^2$ )이다.
///////////////////////////////////////

// 인접 리스트 //
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 100

//// 큐 알고리즘 
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("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->queue[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->queue[q->front];
}

//// 그래프 너비 우선 탐색 알고리즘
#define MAX_VERTICES 100
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 graf_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;
	}
	node = (GraphNode*)malloc(sizeof(GraphNode));
	node->vertex = v;
	node->link = g->adj_list[u];
	g->adj_list[u] = node;
}


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));
	graf_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);
	return 0;
}

인접 리스트이므로 BFS의 시간복잡도는 O(n+e)이다.

박준수

방구석개발자

이전 포스트

[자료구조] - 우선순위 큐 /최대 히프/최소 히프/히프 정렬/응용

다음 포스트

[자료구조]- 그래프1 인접 행렬/인접 리스트/DFS/BFS

[자료구조]

[자료구조] - 우선순위 큐 /최대 히프/최소 히프/히프 정렬/응용

[자료구조] - 그래프2 /최소비용신장트리/Kruskal알고리즘/Prim알고리즘

0개의 댓글