[CS과목/자료구조] 10 그래프 1

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)

 

10.1 그래프란?

그래프의 소개

 그래프(graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조다. 그래프 이론(graph theory)은 컴퓨터 학문 분야의 활발한 연구 주제이며 문제 해결을 위한 도구로서 많은 이론과 응용이 존재한다. 우리는 여기서 그래프의 기본적인 알고리즘에 대해서 학습한다.

 

10.2 그래프의 정의와 용어

그래프의 정의

 그래프는 정점(vertex)과 간선(edge)들의 유한 집합이라 할 수 있다. 수학적으로는 G = (V, E)와 같이 표현한다. 여기서, V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 정점은 여러 가지 특성을 가질 수 있는 객체를 의미하고, 간선은 이러한 정점들 간의 관계를 의미한다. 정점은 노드(node)라고도 불리며, 간선은 링크(link)라고도 불린다.

 

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

 간선의 종류에 따라 그래프는 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다. 무방향 그래프의 간선은 간선을 통해서 양방향으로 갈 수 있음을 나타내며 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현된다. 방향 그래프는 간선에 방향성이 존재하는 그래프로서 도로의 일방통행길처럼 간선을 통하여 한쪽 방향으로만 갈 수 있음을 나타낸다. 정점 A에서 정점 B로만 갈 수 있는 간선은 <A, B>로 표시한다.

 

네트워크

 간선에 가중치를 할당하게 되면, 간선의 역할이 두 정점 간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있으므로 보다 복잡한 관계를 표현할 수 있게 된다. 이렇게 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(weighted graph)또는 네트워크(network)라 한다.

 

부분 그래프

 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 부분 그래프(subgraph)라 한다.

 

정점의 차수

 그래프에서 인접 정점(adjacent vertex)란 간선에 의해 직접 연결된 정점을 뜻한다. 무방향 그래프에서 정점의 차수(degree)는 그 정점에 인접한 정점의 수를 말한다. 방향 그래프에서는 외부에서 오는 간선의 개수를 진입 차수(in-degree)라 하고 외부로 향하는 간선의 개수를 진출 차수(out-degree)라 한다.

 

경로

 무방향 그래프에서 정점 s로부터 정점 e까지의 경로는 정점의 나열 s, v₁, v₂, … , vₖ, e로서, 나열된 정점들 간에는 반드시 간선 (s, v₁), (v₁, v₂), … , (vₖ, e)가 존재해야 한다. 만약 방향 그래프라면 <s, v₁>, <v₁, v₂>, … , <vₖ, e>가 있어야 한다. 경로 중에서 반복되는 간선이 없을 경우에 이러한 경로를 단순 경로(simple path)라 한다. 만약에 단순 경로의 시작 정점과 종료 정점이 동일하다면 이러한 경로를 사이클(cycle)이라 한다.

 

연결 그래프

 무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면 G는 연결되었다고 하며, 이러한 무방향 그래프 G를 연결 그래프(connected graph)라 부른다. 그렇지 않은 그래프는 비연결 그래프(unconnected graph)라고 한다. 트리는 그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프이다.

 

완전 그래프

 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프를 완전 그래프(complete graph)라고 한다.

 

10.3 그래프의 표현 방법

인접 행렬

 그래프의 정점 수가 n이라면 n x n의 2차원 배열인 인접 행렬(adjacent matrix) M의 각 원소를 다음의 규칙에 의해 할당함으로써 그래프를 메모리에 표현할 수 있다.

• if(간선 (i, j)가 그래프에 존재) M[i][j] = 1,    otherwise M[i][j] = 0.

 무방향 그래프인 인접 행렬은 대칭 행렬이 된다. 따라서 무방향 그래프의 경우, 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 절약할 수 있다. 정점의 차수는 인접 행렬의 행에 있는 값을 모두 더하면 된다.

 

                                                           degree(i) = Σ(K=0:n-1)M[i][k]

 

인접 행렬을 이용한 그래프 추상 데이터 타입의 구현

 그래프에 관련된 변수들을 하나의 구조체 GraphType에 정리하도록 하자. 인접 행렬의 이름을 adj_mat라고 하면 구조체는 다음과 같다.

#define MAX_VERTICES 50

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

 

 

 정점을 삽입하는 연산은 n을 하나 증가하면 된다. 간선을 삽입하는 연산은 해당 원소에 1을 삽입하면 된다.

// 그래프 초기화
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("그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}

// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
	if (start >= g->n || end >= g->n) {
		fprintf("그래프: 정점 번호 오류");
		return;
	}
	g->adj_mat[start][end] = 1;
	g->adj_mat[end][start] = 1;
}

 

10.4 그래프의 탐색

 그래프 탐색은 가장 기본적인 연산으로 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 그래프 탐색 방범은 깊이 우선 탐색(DFS: depth first search)과 너비 우선 탐색(BFS: breadth first search)의 두 가지가 있다. 탐색은 트리에서 생각하면 이해하기 쉽다.(트리도 그래피의 일종이라는 점을 명심하자.) 깊이 우선 탐색은 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 너비 우선 탐색은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

 

10.5 깊이 우선 탐색

 깊이 우선 탐색은 그래프의 시작 정점에서 출발하여 시작 정점 v를 방문하였다고 표시한다. 이어서 v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택한다. 만약 그러한 정점이 없다면 탐색은 종료한다.

 

깊이 우선 탐색의 구현(인접 행렬 버전)

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

 

10.6 너비 우선 탐색

 너비 우선 탐색을 위해서는 가까운 거리에 있는 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(queue)가 필요하다. 알고리즘은 큐에서 정점을 꺼내어 정점을 방문하고 인접 정점들을 큐에 추가한다. 큐가 소진할 때까지 동일한 코드를 반복한다. (queue는 원형큐 참고)

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