[C언어로 쉽게 풀어쓴 자료구조] 10장 그래프 Ⅰ

C언어로 쉽게 풀어쓴 자료구조: 10장 그래프 Ⅰ

10.1 그래프란?

그래프(Graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료구조이다.

 

---

10.2 그래프의 정의와 용어

• 그래프는 정점(vertex)와 간선(edge)들의 유한 집합이다.
• 수학적으로는 G = (V, E)라 표기
• V(G)는 그래프 G의 정점들의 집합
• E(G)는 그래프 G의 간선들의 집합

 

무방향 그래프와 방향 그래프

 

• 간선의 종류에 따라 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다.
• 무방향 그래프는 양방향으로 갈수 있다.
• 방향 그래프는 간선에 방향성이 존재하는 그래프로, 한쪽 방향으로만 갈 수 있다.
• 방향 그래프에서 <a, b>와 <b, a>는 다른 간선이다.

 

가중치 그래프와 부분 그래프

 

• 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(weighted graph) 또는 네트워크(network)라 한다.
• 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 부분 그래프(subgraph)라 한다.

 

연결 그래프

 

• 무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재하는 그래프를 연결 그래프(connected graph)라 부른다.
• 모든 정점이 연결되 있지 않은 그래프를 비연결 그래프(unconnected graph)라 한다.

 

완전 그래프

• 그래프에 속해있는 모든 정점이 서로 연결된 그래프를 완전 그래프(complete graph)라 한다.
• 무방향 완전 그래프의 정점 수를 n이라 하면, 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n*(n-1)/2가 된다.

---

10.3 그래프의 표현 방법

• 인접 행렬(adjacency matrix): 2차원 배열을 사용하여 그래프를 표현한다.
• 인접 리스트(adjacency list): 연결 리스트를 사용하는 그래프를 표현한다.

 

인접행렬

• 그래프의 정점 수가 n이라면 n*n의 2차원 배열

 

 

인접행렬 c 코드

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

 

 

인접 리스트

• 인접 리스트(adjacency list)는 그래프를 표현함에 있어 각각의 정점에 인접한 정점들을 연결리스트로 표현한 것이다.

 

인접 리스트 c 구현

#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;
}

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

 

---

10.4 그래프의 탐색

• 깊이 우선 탐색(DFS, Depth First Search)
• 너비 우선 탐색(BFS, Breath First Search)

---

10.5 깊이 우선 탐색 (DFS)

• 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행

탐색 진행 과정

1. 시작 정점에서 출발하여 시작 정점 v을 방문하였다 표시
2. v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택한다.
3. 정점이 없다면 탐색 종료
4. 아직 방문하지 않은 정점 u가 있다면 u를 시작 정점으로 깊이 우선 탐색을 다시 시작

 

구현

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

1. 스택 사용

 

• 스택은 경로 정보를 추적한다
  1. 방문한 정점을 스택에 push
  2. 방문한 정점과 연결된 모든 정점이 이미 방문했다면 스택에서 값을 하나식 pop하여 가장 가까운 갈림길로 되돌아간다.
  3. 정점에 재방문한다면 스택에서pop
  4. 모든 정점을 방문했다면 스택에서 모든 값을 pop
• 배열은 방문 정보를 기록한다.

인접리스트

// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색
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 새로 시작
}

시간 복잡도 O(n+e)

 

행렬 사용

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 새로 시작
}

시간 복잡도 O(n^2)

---

10.6 너비 우선 탐색(BFS)

• 너비 우선 탐색(Breath First Search)은 시작 정점으로부터 가장 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

 

탐색 진행 과정

1. 시작 정점을 큐에 추가
2. 큐에서 정점을 꺼내서 정점을 방문
3. 인접 정점들을 큐에 추가
4. 큐가 소진될 때까지 반복

구현 

 

 

인접 리스트 사용

void bfs_list(GraphType* g, int v)
{
	GraphNode* w;
	QueueType q;

	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->vextex);
				enqueue(&q, w->vertex);	//정점을 큐에 삽입
			}
	}
}

행렬 사용

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); 	// 방문한 정점을 큐에 저장
			}
	}
}