그래프(Graph)
[그래프란?]
- 그래프(graph) : 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조.
예) 지도
- 지도를 그래프로 표시하면 하나의 도시에서 다른 도시로 갈 때 최단 거리 경로가 어떤 것인지를 알고리즘을 이용해 쉽게 찾을 수 있음.
- 운영 체제에서 프로세스와 자원들이 어떻게 연관되는지를 그래프로 표현하게 되면 시스템의 효율이나 교착 상태 유무 등을 알아낼 수 있음.
- 그래프는 많은 문제들을 표현할 수 있는 훌륭한 논리적 도구.
- 선형 리스트나 트리의 구조로는 복잡한 문제들을 표현할 수 없음.
- 그래프 구조는 인접 행렬이나 인접 리스트로 메모리 에 표현되고 처리될 수 있으므로 광범위한 분야의 다양한 문제들을 그래프로 표현하여 컴퓨터 프로그래밍에 의해 해결할 수 있음.
- 그래프는 매우 보편적인 자료 구조로서 트리(tree)도 그래프의 하나의 특수한 종류로 볼 수 있음.
- 그래프 이론(graph theory) : 컴퓨터 학문 분야의 활발한 연구 주제이며 문제 해결을 위한 도구로서 많은 이론과 응용이 존재함.
- 그래프는 수학의 한 분야로서 수백 년간 연구되어 왔고 그래프의 많은 유용한 특성들이 밝혀져 왔음.
- 그러나 그래프 알고리즘을 컴퓨터 프로그램으로 구현하기 시작한 것은 오래되지 않았음.
- 그래프는 수학자 오일러(Euler)에 의해 처음 창안됨.
- 오일러는 위치라는 개념은 정점(vertex)으로, 위치 간의 관계는 간선(edge)로 표현하였음.
- 오일러는 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점으로 되돌아오는 경로를 오일러 경로(Eulerian tour)라 정의하고, 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다는 오일러 정리를 증명함.
- 그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성됨.
- 수학적으로는 G = (V, E)로 표시함. (V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미함.)
- 정점은 여러 가지 특성을 가질 수 있는 객체를 의미하고, 간선은 이러한 정점들 간의 관계를 의미함.
- 정점(vertex)은 노드(node)라고도 불리며, 간선(edge)은 링크(link)라고도 불림.
- 그래프는 정점을 원으로, 간선을 선으로 그려서 사각적으로 표현하기도 하지만 이러한 사각적인 형태가 그래프의 정의는 아님.
- 그래프는 오직 정점과 간선의 집합일 뿐이며, 그래프의 시각적 표현은 이해를 돕는 역할만을 함에 주의해야 함.
- 그래프는 간선의 종류에 따라 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분됨.
- 무방향 그래프의 간선은 간선을 통해서 양 방향을 갈 수 있음을 나타내며 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현함.
((A,B)와 (B, A)는 동일한 간선)
- 방향 그래프는 간선에 방향성이 존재하는 그래프로서 도로의 일방 통행길과 마찬가지로 간선을 통하여 한쪽 방향으로만 갈 수 있음을 나타냄.
- 점점 A에서 정점 B로만 갈 수 있는 간선은 <A, B>로 표시함. (<A, B>와 <B, A>는 서로 다른 간선)
- 그래프의 간선에 가중치를 할당하게 되면, 간선의 역할이 두 정점 간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있으므로 훨씬 복잡한 관계를 표현할 수 있게 됨.
- 가중치 그래프(weighted graph) 또는 네트워크(network) : 간선에 비용이나 가중치가 할당된 그래프
V(G1) = {0, 1, 2, 3), E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
V(G2) = {0, 1, 2, 3}, E(G2) = {(0, 1), (0, 2)}
V(G3) = {0, 1, 2}, E(G3) = {<0, 1>, <1, 0>, <1, 2>}
- 부분 그래프(subgraph) : 그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분집합으로 이루어진 그래프
- 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
-> (a)의 그래프 G1에서 정점 0의 인접 저점은 정점 1, 정점 2, 정점 3
- 무방향 그래프에서의 정점의 차수(degree) : 하나의 정점에 인접한 정점의 수
-> 그래프 G1의 정점 0은 정점 차수가 3.
- 무방향 그래프에 존재하는 정점의 모든 차수를 합하면 그래프의 간선 수의 2배가 됨. (하나의 간선이 두 개의 정점에 인접하기 때문.)
- 진입 차수(in-degree) : 방향 그래프에서 외부에서 오는 간선의 수
- 진출 차수(out-degree) : 방향 그래프에서 외부로 향하는 간선의 수
-> 방향 그래프 G#의 정점 1은 내차수가 1, 외차수가 2.
- 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합은 방향 그래프의 간선의 수가 됨.
- 무방향 그래프에서 정점 s로부터 정점 e까지의 경로는 정점의 나열 s, v1, v2, ..., vk, e로서, 나열된 정점들 간에는 반드시 간선 (s, v1), (v1, v2), ..., (vk, e)가 존재해야 함.
- 만약 방향 그래프라면 간선 <s, v1>, <v1, v2>, ..., <vk, e>가 있어야 함.
-> 그래프 G1에서 0, 1, 2, 3은 경로이지만 0, 1, 3, 2는 경로가 아님. (간선 (1, 3)이 존재하지 않기 때문)
- 경로 길이(path length) : 경로를 구성하는 데 사용된 간선의 수
- 단순 경로(simple path) : 경로 중에서 반복되는 간선이 없을 경우의 경로
- 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일할 때의 경로
-> 그래프 G1의 경로 1, 0, 2, 3은 단순 경로이고 경로 1, 0, 2, 0은 단순 경로가 아님.
-> 그래프 G1에서 경로 0, 1, 2, 0은 사이클이 됨.
-> 그래프 G3에서 경로 0, 1, 0도 사이클이 됨.
- 연결 그래프(connected graph) : 무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면 G는 연결되었다고 하며, 이러한 무방향 그래프 G
- 그렇지 않은 그래프는 비연결 그래프라고 함.
-> (b)의 G2는 비연결 그래프.
- 트리(tree) : 그래프의 특수한 형태로서 사이클을 가지지 않은 연결 그래프.
-> (b), (c), (d)는 모두 연결되어 있을 뿐만 아니라 사이클이 없으므로 트리.
- 완전 그래프(complete graph) : 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
- 무방향 완전 그래프의 정점 수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n*(n-1)./2.
[그래프의 표현 방법]
- 그래프 문제를 프로그램에 의해 해결하기 위해서는 그래프(정점의 집합과 간선의 집합)를 컴퓨터 메모리에 저장하여야 함.
- 그래프를 메모리에 표현하는 방법으로는 2차원 배열을 사용하는 인접 행렬(adjacency matrix)과 연결 리스트를 사용하는 인접 리스트(adjacency list)의 두 가지 방법이 있음.
- 그래프 문제의 특성에 따라 위의 두 가지 표현 방법은 각각 메모리 사용량과 처리 시간 등에서 장단점을 가지므로 문제에 적합한 표현 방법을 선택해야 함.
(1) 인접 행렬
- 2차원 배열인 인접 행렬(adjacency matrix) M의 각 원소를 다음의 규칙에 의해 할당함으로써 그래프를 메모리에 표현할 수 있음.
if(간선 (i, j)가 그래프에 존재 M[i][j] = 1,
otherwise M[i][j] = 0.
- 우리가 다루고 있는 그래프에서는 자체 간선을 허용하지 않으므로 인접 행렬의 대각선 성분은 모두 0으로 표시됨.
- 무방향 그래프의 인접 행렬은 대칭 행렬이 됨. (무방향 그래프의 간선 (i, j)는 정점 i에서 정점 j로의 연결뿐만 아니라 정점 j에서 정점 i로의 연결을 동시에 의미하기 때문)
- 따라서 무방향 그래프의 경우, 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 절약할 수 있음.
- 그러나 방향 그래프의 인접 행렬은 일반적으로 대칭이 아님.
- n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 n²개의 메모리 공간이 필요함.
- 이에 따라 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하는 경ㅇ에는 적합하나, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(sparse graph)의 경우에는 메모리의 낭비가 크므로 적합하지 않음.
- 인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 O(1) 시간 안에 즉시 알 수 있는 장점이 있음.
-> 정점 i와 정점 j를 연결하는 간선이 있는지를 알려면 M[i][j]의 값을 조사하면 바로 알 수 있음.
- 또한 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 O(n)의 연산에 의해 알 수 있음.
- 정점 i에 대한 차수는 다음과 같이 인접 배열의 i번째 행에 있는 값을 모두 더하면 됨.
- 반면에 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하므로 n²번의 조사가 필요하게 되어 O(n²)의 시간이 요구됨.
- 인접 행렬을 이용한 그래프 프로그램
// 인접 행렬을 이용한 그래프 프로그램
#include <stdio.h>
#define MAX_VERTICES 50
typedef struct GraphType {
int n; // 정점의 개수
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
// 그래프 초기화
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;
}
(2) 인접 리스트
- 인접 리스트(adjacency list) : 그래프를 표현함에 있어 각각의 정점에 인접한 정점들을 연결 리스트로 표시한 것.
- 각 연결 리스트의 노드들은 인접 정점을 저장하게 됨.
- 각 연결 리스트들은 헤드 포인터를 가지고 있고 이 헤드 포인터들은 하나의 배열로 구성되어 있음.
- 따라서 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정ㅇ점의 연결 리스트에 쉽게 접근할 수 있음.
- 무방향 그래프의 경우 정점 i와 정점 j를 연결하는 간선 (i, j)는 정점 i의 연결 리스트에 인접 정점 j로서 한 번 표현되고, 정점 j의 연결 리스트에 인접 정점 i로 다시 한 번 표현됨.
- 인접 리스트의 각각의 연결 리스트에 정점들이 입력되는 순서에 따라 연결 리스트 내에서 정점들의 순서가 달라질 수 있음.
- 정점의 수가 n개이고, 간선의 수가 e개인 무방향 그래프를 표시하기 위해서는 n개의 연결 리스트가 필요하고, n개의 헤드 포인터와 2e개의 노드가 필요함.
- 따라서 인접 리스트 표현은 간선의 개수가 적은 희소 그래프(sparse graph)의 표현에 적합함.
- 그래프의 간선 (i, j)의 존재 여부나 정점 i의 차수를 알기 위해서는 인접 리스트에서의 정점 i의 연결 리스트를 탐색해야 하므로 연결 리스트에 있는 노드의 수만큼, 즉 정점 차수만큼의 시간이 필요함.
- n개 정점과 e개의 간선을 가진 그래프에서 전체 간선의 수를 알아내려면 헤더 노드를 포함하여 모든 인접 리스트를 조사해야 하므로 O(n+e)의 연산이 요구됨.
- 인접 리스트를 이용한 그래프 프로그램
// 인접 리스트를 이용한 그래프 프로그램
#include <stdio.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 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++;
}
// 간선 삽입 연산, 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;
}
[그래프의 탐색]
- 그래프의 탐색 : 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.
- 그래프 탐색은 매우 중요함.
- 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결됨.
- 대표적으로 특정한 정점에서 다른 정점으로 갈 수 있는지 없는지를 탐색을 통하여 알 수 있음.
- 그래프의 탐색 방법에는 깊이 우선 탐색과 너비 우선 탐색의 두 가지 탐색 방법이 있음.
(1) 깊이 우선 탐색
- 깊이 우선 탐색(depth first search : DFS) : 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함.
- 깊이 우선 탐색은 그래프의 시작 정점에서 출발하여 먼저 시작 정점 v를 방문하고 방문하였다고 표시함.
- v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택함.
- 만약 그러한 정점이 없다면 탐색이 종료됨.
- 만약 아직 방문하지 않은 정점 u가 있다면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작함.
- 이 탐색이 끝나게 되면 다시 v에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾음.
- 만약 없으면 종료하고, 있다면 다시 그 정점을 시작 정점으로 하여 깊이 우선 탐색을 다시 시작함.
- 깊이 우선 탐색도 자기 자신을 다시 호출하는 순환 알고리즘의 형태를 가지고 있음.
- 깊이 우선 탐색을 구현하는 데는 2가지의 방법이 있음.
1. 순환 호출을 이용하는 방법
2. 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업하는 방법
- 이 글에서는 순환 호출을 이용하는 방법으로 깊이 우선 탐색을 구현하기로 함.
- 방문 여부를 기록하기 위해 배열 visited를 사용하며, 모든 정점의 visited 배열 값은 FALSE로 초기화되고 정점이 방문될 때마다 해당 정점의 visited 배열 값은 TRUE로 변경됨.
- 인접 배열로 표현된 그래프에 대한 깊이 우선 탐색 프로그램
// 인접 배열로 표현된 그래프에 대한 깊이 우선 탐색 프로그램
#include <stdio.h>
#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0
typedef struct GraphType {
int n; // 정점의 개수
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];
// 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색
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 새로 시작
}
}
}
- 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색 프로그램
// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색 프로그램
#include <stdio.h>
#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0
int visited[MAX_VERTICES];
typedef struct GraphNode {
int vertex;
struct GraphNode *link;
} GraphNode;
typedef struct GraphType {
int n; // 정점의 개수
GraphNode *adj_list[MAX_VERTICES];
} GraphType;
// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색
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->vertex에서 DFS 새로 시작
}
}
}
(2) 너비 우선 탐색
- 너비 우선 탐색(breadth first search : BFS) : 시작 정점으로부터 가까운 장점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.
- 너비 우선 탐색을 위해서는 방문한 정점들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(queue)가 필요함.
- 즉, 정점이 방문될 때마다 큐에 방문된 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우 큐의 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을 모두 차례대로 방문하게 됨.
- 초기 상태의 큐에는 시작 정점만이 저장되고, 너비 우선 탐색 과정은 큐가 소진될 때까지 계속함.
- 너비 우선 탐색의 특징은 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색이 진행된다는 것.
- 여기서 거리란 시작 정점으로부터 어떤 정점까지의 경로 중 가장 짧은 경로의 길이를 뜻함.
- 즉 너비 우선 탐색은 거리가 d인 정점들을 모두 방문한 다음, 거리가 (d+1)인 정점들을 모두 방문하게 됨.
- 거리가 0인 시작 정점을 방문한 후, 거리가 1인 모든 정점, 거리가 2인 모든 정점, 거리가 3인 모든 정점 등의 순서로 정점들을 방문해감.
- 인접 행렬로 표현된 그래프에 대한 너비 우선 탐색 프로그램
// 인접 행렬로 표현된 그래프에 대한 너비 우선 탐색 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0
typedef struct GraphType {
int n; // 정점의 개수
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];
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 init(QueueType *q) {
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q) {
return (q->front == q->rear); // front == rear이면 공백 상태
}
// 포화 상태 검출 함수
int is_full(QueueType *q) {
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front); // front == (rear + 1)이면 포화 상태
}
// 삽입 함수
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];
}
// 피크 함수
element peak(QueueType *q) {
if (is_empty(q)) {
error("큐가 공백상태입니다.");
}
return q->queue[(q->front + 1) % MAX_QUEUE_SIZE];
}
void bfs_mat(GraphType *g, int v) {
int w;
QueueType q;
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); // 방문한 정점을 큐에 저장
}
}
}
}
- 인접 리스트로 표현된 그래프에 대한 너비 우선 탐색 프로그램
// 인접 리스트로 표현된 그래프에 대한 너비 우선 탐색 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0
int visited[MAX_VERTICES];
typedef struct GraphNode {
int vertex;
struct GraphNode *link;
} GraphNode;
typedef struct GraphType {
int n; // 정점의 개수
GraphNode *adj_list[MAX_VERTICES];
} GraphType;
typedef int element;
typedef struct {
element queue[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
// 그래프 초기화
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++;
}
// 간선 삽입 연산, 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 error(char *message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
// 초기화 함수
void init(QueueType *q) {
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q) {
return (q->front == q->rear); // front == rear이면 공백 상태
}
// 포화 상태 검출 함수
int is_full(QueueType *q) {
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front); // front == (rear + 1)이면 포화 상태
}
// 삽입 함수
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];
}
// 피크 함수
element peak(QueueType *q) {
if (is_empty(q)) {
error("큐가 공백상태입니다.");
}
return q->queue[(q->front + 1) % MAX_QUEUE_SIZE];
}
// 너비 우선 탐색(인접 리스트)
void bfs_list(GraphType *g, int v) {
GraphNode *w;
QueueType q;
init(&q); // 큐 초기화
visited[v] = TRUE; // 정점 v 방문 표시
printf("%d ", v); // 정점 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); // 방문한 정점을 큐에 삽입
}
}
}
}
void main() {
int i;
GraphType g;
graph_init(&g);
// 인접 리스트 생성
for (i = 0; i < 4; i++) {
insert_vertex(&g, i);
}
insert_edge(&g, 0, 1);
insert_edge(&g, 1, 0);
insert_edge(&g, 0, 3);
insert_edge(&g, 3, 0);
insert_edge(&g, 1, 2);
insert_edge(&g, 2, 1);
insert_edge(&g, 1, 3);
insert_edge(&g, 3, 1);
insert_edge(&g, 2, 3);
insert_edge(&g, 3, 2);
bfs_list(&g, 0);
}
- 너비 우선 탐색은 그래프가 인접 리스트로 표현되어 있으면 전체 수행 시간이 O(n+e)이며, 인접 행렬로 표현되어 있는 경우는 O(n²) 시간이 걸림.
- 너비 우선 탐색도 깊이 우선 탐색과 같이 희소 그래프인 경우 인접 리스트를 사용하는 것이 효율적임.
[연결 성분]
- 연결 성분(connected component) : 최대로 연결된 부분 그래프. -> 연결된 부분 그래프들 중에서 크기가 최대인 그래프.
- 연결 성분을 찾기 위해서 깊이 우선 탐색이나 너비 우선 탐색을 이용함.
- 먼저 그래프 상의 임의의 정점을 선택해 깊이 우선 탐색이나 너비 우선 탐색을 시작하면 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결 성분이 됨.
- 다음에 방문 안 된 정점을 선택해서 다시 탐색을 실행하면 그 정점을 포함하는 연결 성분이 구해짐.
- 이러한 방법으로 그래프 상의 모든 정점이 방문될 때까지 이 과정을 되풀이하면 그래프에 존재하는 모든 연결 성분들을 찾을 수 있음.
- 깊이 우선 탐색 알고리즘을 이용해 연결 성분을 찾고자 할 경우, 깊이 우선 탐색 프로그램에서 정점 방문을 표시하는 문장인 visited[v] = TRUE를 visited[v] = count로 바꾸고, count를 증가시키면서 반복적으로 깊이 우선 탐색 프로그램을 호출함.
- 여기서 사용되는 count는 전역변수로서 0으로 초기화 되어야 함.
- 연결 성분 프로그램
// 연결 성분 프로그램
#include <stdio.h>
#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0
typedef struct GraphType {
int n; // 정점의 개수
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];
int count;
// 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_mat(GraphType *g, int v) {
int w;
visited[v] = count; // 정점 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 새로 시작
}
}
}
// 연결 성분
void find_connected_component(GraphType *g) {
int i;
count = 0;
for (i = 0; i < g->n; i++) {
if (!visited[i]) { // 방문되지 않았으면
count++;
dfs_mat(g, i);
}
}
}
[신장 트리]
- 신장 트리(spanning tree) : 그래프 내의 모든 정점을 포함하는 트리
- 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안됨.
- 따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 됨.
- 그래프에서 신장 트리를 찾으려면 깊이 우선 탐색이나 너비 우선 탐색을 사용할 수 있음.
- 하나의 그래프에는 많은 신장 트리가 존재 가능함.
- 신장 트리는 깊이 우선 탐색이나 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있음.
- (b)의 맨 왼쪽 신장 트리는 시작 정점 0으로 깊이 우선 탐색할 때 사용된 간선ㅇ로만 만들어진 신장 트리(깊이 우선 신장 트리)
- (b)의 중간 신장 트리는 시작 정점 0으로 너비 우선 탐색할 때 사용된 간선으로만 만들어진 신장 트리(너비 우선 신장 트리)
- 신장 트리 알고리즘
| depth_first_search(v) v를 방문되었다고 표시; for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면) then (v,u)를 신장트리 간선이라고 표시; depth_first_search(u); |
- 신장 트리는 그래프의 최소 연결 부분 그래프가 됨.
- 여기서 최소의 의미는 간선의 수가 가장 적다는 의미.
- n개의 정점을 가지는 그래프는 최소한 n-1개의 간선을 가져야 하며 n-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 트리가 됨.
- 따라서 신장 트리는 통신 네트워크 구축에 사용됨.
예) n개의 위치를 연결하는 통신 네트워크를 최소의 링크를 이용하여 구축하고자 할 경우, 최소 링크 수는 n-1이 되고 따라서 신장 트리들이 가능한 대안이 됨.
예) 회사 내의 모든 전화기를 가장 적은 수의 케이블을 사용하여 연결하고자 한다면 신장 트리를 구함으로써 해결할 수 있음.
- 그러나 각 링크의 구축 비용은 똑같지 않음.
- 따라서 단순히 가장 적은 링크만을 사용한다고 해서 최소 비용이 얻어지는 것은 아님.
- 각 링크, 즉 간선에 비용을 붙여서 링크의 구축 비용까지를 고려하여 최소 비용의 신장 트리를 선택할 필요가 있음.
[최소 비용 신장 트리]
- 통신망, 도로망, 유통망 등은 대개 길이, 구축 비용, 전송 시간 등의 가중치를 간선에 할당한 그래프인 네트워크로 표현될 수 있음.
- 이러한 통신망, 도로망, 유통망을 가장 적은 비용으로 구축하고자 한다면, 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 최소 비용 신장 트리(MST : minimum spanning tree)가 필요하게 됨.
- 최소 비용 신장 트리 : 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리
- 최소 비용 신장 트리를 구하는 방법으로는 Kruskal과 Prim이 제안한 알고리즘이 대표적임.
- 이 알고리즘들은 최소 비용 신장 트리가 간선의 가중치의 합이 최소이어야 하고, 반드시 (n-1)개의 간선만 사용해야 하며, 사이클이 포함되어서는 안 된다는 조건을 적절히 이용하고 있음.
(1) Kruskal의 MST 알고리즘
- Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용함.
- 탐욕적인 방법은 알고리즘 설계에 있어서 중요한 기법 중의 하나임.
- 탐욕적인 방법이란 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달함.
- 마치 음식을 먹을 때 매 순간에 가장 맛있다고 생각되는 것부터 먹는 것과 같음.
- 그 순간의 선택은 그 당시에는 최적임.
- 그러나 최적이라고 생각했던 해답들을 모아서 최종적인 해답을 만들었다고 해서, 그 해답이 전체적인 관점에서 최적이라는 보장은 없음.
- 따라서 탐욕적인 방법은 항상 최적의 해답을 주는지를 반드시 검증해야 함.
- 다행히 Kruskal의 알고리즘은 최적의 해답을 주는 것으로 증명되어 있음.
- Kruskal의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 근거하여, 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택함.
- 이러한 과정을 반복함으로써 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구할 수 있음.
- Kruskal의 알고리즘은 먼저 그래프의 e개의 간선들을 가중치의 오름차순으로 정렬함.
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택하여 현재의 최소 비용 신장 트리의 집합에 추가함.
- 만약 사이클을 형성하면 그 간선은 제외됨.
- Kruskal의 알고리즘은 최소 비용 신장 트리를 구하는 다른 알고리즘보다 간단해 보임.
- 하지만, 다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는지를 체크해야 함.
- 새로운 간선이 이미 다른 경로에 의하여 연결되어 있는 정점들을 연결할 때 사이클이 형성됨.
- union-find 알고리즘 : 지금 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사하는 알고리즘.
-> 간선의 양끝 정점이 서로 다른 집합에 속하는 경우 두 정점을 연결하여도 사이클이 형성되지 않음.
- union-find 연산은 Kruskal의 알고리즘에서만 사용되는 것은 아니고 일반적으로 널리 사용됨.
- union(x, y) 연산은 원소 x와 y가 속해 있는 집합을 입력으로 받아 2개의 집합의 합집합을 만듦.
- find(x) 연산은 원소 x가 속해 있는 집합을 반환함.
- 집합을 구현하는 데는 여러 가지 방법이 있을 수 있음. (비트 벡터, 배열, 연결 리스트를 이용하여 구현할 수 있음.)
- 그러나 가장 효율적인 방법은 트리 형태를 사용하는 것.
예) 집합 {1, 4}, {5, 2}, {3}, {6} 들은 (a)와 같이 표현되고, 이어서 union(4, 5)와 union(3, 6)을 한다면 (b)와 같은 트리로 변화하게 됨.
이 상태에서 find(4)를 한다면 루트인 정점 2가 집합의 대표로 반환되게 됨.
- find 연산에 소요되는 시간을 줄이려면 특정 정점과 루트와의 거리가 짧아야 함.
- 이것을 위하여 모든 정점이 루트 바로 아래에 있도록 하면 좋을 것.
- 이를 위하여 find 연산이 이루어질 때마다 모든 원소를 루트 노드 바로 밑에 놓음.
- 또한 union 연산 시에 정점의 개수가 적은 트리의 루트가 큰 트리의 루트를 가리키도록 하면 좋을 것.
- Kruskal의 최소 비용 신장 트리 프로그램
// Kruskal의 최소 비용 신장 트리 프로그램
#include <stdio.h>
#define MAX_VERTICES 100
#define INF 1000
int parent[MAX_VERTICES]; // 부모 노드
int num[MAX_VERTICES]; // 각 집합의 크기
// 초기화
void set_init(int n) {
int i;
for (i = 0; i<n; i++) {
parent[i] = -1;
num[i] = 1;
}
}
// vertex가 속하는 집합을 반환한다.
int set_find(int vertex) {
int p, s, i = -1;
for (i = vertex; (p = parent[i]) >= 0; i = p); // 루트 노드까지 반복
s = i; // 집합의 대표 원소
for (i = vertex; (p = parent[i]) >= 0; i = p) {
parent[i] = s; // 집합의 모든 원소들의 부모를 p로 설정
}
return s;
}
// 두개의 원소가 속한 집합을 합친다.
void set_union(int s1, int s2) {
if (num[s1] < num[s2]) {
parent[s1] = s2;
num[s2] += num[s1];
}
else {
parent[s2] = s1;
num[s1] += num[s2];
}
}
typedef struct {
int key; // 간선의 가중치
int u; // 정점 1
int v; // 정점 2
} element;
#define MAX_ELEMENT 100
typedef struct {
element heap[MAX_ELEMENT];
int heap_size;
} HeapType;
// 초기화 함수
init(HeapType *h) {
h->heap_size = 0;
}
// 히프 내용 출력 함수
print_heap(HeapType *h) {
int i;
int level = 1;
printf("\n===================");
for (i = 1; i <= h->heap_size; i++) {
if (i == level) {
printf("\n");
level *= 2;
}
printf("\t%d", h->heap[i].key);
}
printf("\n===================");
}
// 삽입 함수
void insert_min_heap(HeapType *h, element item) {
int i;
i = ++(h->heap_size);
// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
while ((i != 1) && (item.key < h->heap[i / 2].key)) {
h->heap[i] = h->heap[i / 2];
i /= 2;
}
h->heap[i] = item; // 새로운 노드를 삽입
}
// 삭제 함수
element delete_min_heap(HeapType *h) {
int parent, child;
element item, temp;
item = h->heap[1];
temp = h->heap[(h->heap_size)--];
parent = 1;
child = 2;
while (child <= h->heap_size) {
// 현재 노드의 자식노드중 더 작은 자식노드를 찾는다.
if ((child < h->heap_size) && (h->heap[child].key) > h->heap[child + 1].key) {
child++;
}
if (temp.key <= h->heap[child].key) break;
// 한단계 아래로 이동
h->heap[parent] = h->heap[child];
parent = child;
child *= 2;
}
h->heap[parent] = temp;
return item;
}
// 정점 u와 정점 v를 연결하는 가중치가 weight인 간선을 히프에 삽입
void insert_heap_edge(HeapType *h, int u, int v, int weight) {
element e;
e.u = u;
e.v = v;
e.key = weight;
insert_min_heap(h, e);
}
// 인접 행렬이나 인접 리스트에서 간선들을 읽어서 최소 히프에 삽입
// 현재는 예제 그래프의 간선들을 삽입한다.
void insert_all_edges(HeapType *h) {
insert_heap_edge(h, 0, 1, 29);
insert_heap_edge(h, 1, 2, 16);
insert_heap_edge(h, 2, 3, 12);
insert_heap_edge(h, 3, 4, 22);
insert_heap_edge(h, 4, 5, 27);
insert_heap_edge(h, 5, 0, 10);
insert_heap_edge(h, 6, 1, 15);
insert_heap_edge(h, 6, 3, 18);
insert_heap_edge(h, 6, 4, 25);
}
// kruskal의 최소 비용 신장 트리 프로그램
void kruskal(int n) {
int edge_accepted = 0; // 현재까지 선택된 간선의 수
HeapType h; // 최소 히프
int uset, vset; // 정점 u와 정점 v의 집합 번호
element e; // 히프 요소
init(&h); // 히프 초기화
insert_all_edges(&h); // 히프에 간선들을 삽입
set_init(n); // 집합 초기화
while (edge_accepted < (n - 1)) { // 간선의 수 < (n-1)
e = delete_min_heap(&h); // 최소 히프에서 삭제
uset = set_find(e.u); // 정점 u의 집합 번호
vset = set_find(e.v); // 정점 v의 집합 번호
if (uset != vset) { // 서로 속한 집합이 다르면
printf("(%d,%d) %d \n", e.u, e.v, e.key);
edge_accepted++;
set_union(uset, vset); // 두개의 집합을 합친다.
}
}
}
void main()
{
kruskal(7);
}
- 이 union-find 알고리즘을 사용하면 Kruskal의 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우됨.
- 따라서 간선 e개를 퀵 정렬과 같은 효율적인 알고리즘으로 정렬한다면 Kruskal 알고리즘의 시간 복잡도는 O(elog₂e)이 됨.
(2) Prim의 MST 알고리즘
- Prim의 알고리즘은 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법임.
- 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함됨.
- Prim의 방법은 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장함.
- 이 과정은 트리가 n-1개의 간선을 가질 때까지 계속됨.
- Kruskal의 알고리즘은 간선 선택을 기반으로 하는 알고리즘인 반면에, Prim의 알고리즘은 정점 선택을 기반으로 하는 알고리즘임.
- 또한 Kruskal의 알고리즘은 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법인 데 반하여 Prim의 알고리즘은 이전 단계에서 만들어진 신장 트리를 확장하는 방식임.
- Prim의 최소 비용 신장 트리 프로그램
// Prim의 최소 비용 신장 트리 프로그램
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define VERTICES 7
#define INF 1000L
int adj_mat[VERTICES][VERTICES] = {
{ 0, 29, INF, INF, INF, 10, INF },
{ 29, 0, 16, INF, INF, INF, 15 },
{ INF, 16, 0, 12, INF, INF, INF },
{ INF, INF, 12, 0, 22, INF, 18 },
{ INF, INF, INF, 22, 0, 27, 25 },
{ 10, INF, INF, INF, 27, 0, INF },
{ INF, 15, INF, 18, 25, INF, 0 } };
int selected[VERTICES];
int dist[VERTICES];
// 최소 dist[v] 값을 갖는 정점을 반환
int get_min_vertex(int n) {
int v, i;
for (i = 0; i <n; i++)
if (!selected[i]) {
v = i;
break;
}
for (i = 0; i < n; i++) {
if (!selected[i] && (dist[i] < dist[v])) v = i;
}
return (v);
}
void prim(int s, int n) {
int i, u, v;
for (u = 0; u<n; u++) {
dist[u] = INF;
}
dist[s] = 0;
for (i = 0; i<n; i++) {
u = get_min_vertex(n);
selected[u] = TRUE;
if (dist[u] == INF) return;
printf("%d ", u);
for (v = 0; v<n; v++) {
if (adj_mat[u][v] != INF) {
if (!selected[v] && adj_mat[u][v]< dist[v]) {
dist[v] = adj_mat[u][v];
}
}
}
}
}
void main()
{
prim(0, VERTICES);
}
- Prim의 알고리즘은 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 Prim의 알고리즘은 O(n²)의 복잡도를 가짐.
- Krustal의 알고리즘은 복잡도가 O(elog₂e)이므로 희박한 그래프를 대상으로 할 경우에는 Krustal의 알고리즘이 적합하고, 밀집한 그래프의 경우에는 Prim의 알고리즘이 유리하다고 할 수 있음.
[최단 경로]
- 최단 경로(shortest path) 문제 : 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제
- 간선의 가중치는 비용, 거리, 시간 등을 나타냄.
- 최단 경로를 발견하는 방법에는 2가지의 알고리즘이 있음.
1. Dijkstra 알고리즘 : 하나의 시작 정점에서 모든 다른 정점까지의 최단 경로를 구함.
2. Floyd 알고리즘 : 모든 정점에서 다른 모든 정점까지의 최단 경로를 구함.
- 가중치는 가중치 인접 행렬이라고 불리는 2차원 배열에 저장되어 있다고 가정.
- 여기서 인접 행렬과 가중치 인접 행렬과의 차이점을 주의 깊게 살펴보아야 함.
- 인접 행렬에서는 간선이 없으면 인접 행렬의 값이 0임.
- 그러나 가중치 인접 행렬에서는 간선의 가중치가 0일 수도 있기 때문에 0의 값이 간선이 없음을 나타내지 못함.
- 따라서 다른 방법을 강구해야 하는데, 이론적으로는 무한대의 값을 가중치 인접 행렬에 저장하면 됨.
- 즉, 무한대의 값이면 간선이 없다고 생각하면 됨.
- 그러나 컴퓨터에는 무한대의 값이 없음.
- 따라서 만약 간선이 존재하지 않으면 정수 중에서 상당히 큰 값을 무한대라고 생각하고 가중치 인접 행렬에 저장하는 것으로 함.
(1) Dijkstra의 최단 경로 알고리즘
- Dijkstra의 최단 경로 알고리즘 : 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘.
- 최단 경로는 경로의 길이순으로 구해짐.
- 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로 찾음.
- 집합 S -> 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합
- distance 배열 -> 최단경로가 알려진 정점들만을 이용한 다른 정점들까지의 최단경로 길이
-> distance 배열의 초기값(시작 정점 v)
- distance[v] = 0
- 다른 정점에 대한 distance 값은 시작정점과 해당 정점간의 가중치 값
- 매 단계에서 가장 distance 값이 작은 정점을 S에 추가
- distance 값이 가장 작은 정점을 u라고 하면, 시작 정점 v에서 정점 u까지의 최단거리는 경로 ①이 됨.
- 정점 w를 거쳐서 정점 u로 가는 가상적인 더 짧은 경로가 있다고 가정하면, 정점 v에서 정점 u까지의 거리는 정점 v에서 정점 w까지의 거리 ②와 정점 w에서 정점 u로 가는 거리③을 합한 값이 됨.
- 그러나 경로 ②는 경로 ①보다 항상 길 수 밖에 없음. (현재 distance 값이 가장 작은 정점은 u이기 때문.)
- 따라서 매 단계에서 distance 값이 가장 작은 정점들을 추가해나가면 시작 정점에서 모든 정점까지의 최단거리를 구할 수 있음.
- 새로운 정점이 S에 추가되면 distance값 갱신.
- 최단 경로 Dijkstra 프로그램
// 최단 경로 Dijkstra 프로그램
#include <stdio.h>
#define INT_MAX 2147483647 // 최대 정수
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 7 // 정점의 수
#define INF 1000 // 무한대(연결이 없는 경우)
int weight[MAX_VERTICES][MAX_VERTICES] = { // 네트워크의 인접행렬
{ 0, 7, INF, INF, 3, 10, INF },
{ 7, 0, 4, 10, 2, 6, INF },
{ INF, 4, 0, 2, INF, INF, INF },
{ INF, 10, 2, 0, 11, 9, 4 },
{ 3, 2, INF, 11, 0, INF, 5 },
{ 10, 6, INF, 9, INF, 0, INF },
{ INF, INF, INF, 4, 5, INF, 0 } };
int distance[MAX_VERTICES]; // 시작 정점으로부터의 최단 경로 거리
int found[MAX_VERTICES]; // 방문한 정점 표시
int choose(int distance[], int n, int found[])
{
int i, min, minpos;
min = INT_MAX;
minpos = -1;
for (i = 0; i<n; i++) {
if (distance[i]< min && !found[i]) {
min = distance[i];
minpos = i;
}
}
return minpos;
}
void shortest_path(int start, int n) {
int i, u, w;
for (i = 0; i<n; i++) { // 초기화
distance[i] = weight[start][i];
found[i] = FALSE;
}
found[start] = TRUE; // 시작 정점 방문 표시
distance[start] = 0;
for (i = 0; i<n; i++) {
u = choose(distance, n, found);
found[u] = TRUE;
for (w = 0; w<n; w++) {
if (!found[w]) {
if (distance[u] + weight[u][w] < distance[w]) {
distance[w] = distance[u] + weight[u][w];
}
}
}
}
}
void main()
{
shortest_path(0, MAX_VERTICES);
}
- 위 프로그램의 효율성을 높이기 위해서는 최솟값을 선택하는 choose 함수를 우선순위 큐로 대치하면 더 빠르게 수행시킬 수 있음.
- 네트워크에 n개의 정점이 있다면, Dijkstra 최단 경로 알고리즘은 주 반복문을 n번 반복하고 내부 반복문을 2n번 반복하므로 O(n²)의 복잡도를 가짐.
(2) Floyd의 최단 경로 알고리즘
- 그래프에 존재하는 모든 정점 사이의 최단 경로를 구하려면 Dijkstra의 알고리즘을 정점의 수만큼 반복 실행하면 됨.
- 그러나 모든 정점 사이의 최단 거리를 구하려면 더 간단하고 좋은 알고리즘이 있음.
- Floyd 알고리즘 : 그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 모두 찾아주는 알고리즘
- Floyd의 최단 경로 알고리즘은 2차원 배열 A를 이용하여 3중 반복을 하는 루프로 구성되어 있음.
- 인접 행렬 weight 구성
-> i==j이면, weight[i][j]=0
-> 두개의 정점 i, j 사이에 간선이 존재하지 않으면, weight[i][j]=∞
-> 정점 i, j 사이에 간선이 존재하면, weight[i][j]는 간선 (i, j)의 가중치
-> 배열 A의 초기 값은 인접 행렬 weight임.
- A^k [i][j]
-> 0부터 k까지의 정점만을 이용한 정점 i에서 j까지의 최단 경로 길이
- A^-1→A^0 → A^1 → … → A^n-1순으로 최단 경로 구해감.
- A^k-1까지 구해진 상태에서 k번째 정점이 추가로 고려되는 상황을 생각함.
- 0부터 k까지의 정점만을 사용하여 정점 i에서 정점 j로 가는 최단 경로는 다음의 2가지의 경우로 나뉘어짐.
1. 정점 k를 거치지 않는 경우: A^k[i][j] 는 k보다 큰 정점은 통과하지 않으므로 최단거리는 여전히 A^k-1[i][j]]임.
2. 정점 k를 거치는 경우: i에서 k까지의 최단거리 A^k-1[i][k]에 k에서 j까지의 최단거리 A^k-1[k][j]를 더한 값
- Floyd의 최단 경로 프로그램
// Floyd의 최단 경로 프로그램
#include <stdio.h>
#include <limits.h>
#define TRUE 1
#define FALSE 0
#define VERTICES 7 // 정점의 수
#define INF 10000 // 무한대 (연결이 없는 경우)
int weight[VERTICES][VERTICES] = { // 네트워크의 인접행렬
{ 0, 7, INF, INF, 3, 10, INF },
{ 7, 0, 4, 10, 2, 6, INF },
{ INF, 4, 0, 2, INF, INF, INF },
{ INF, 10, 2, 0, 11, 9, 4 },
{ 3, 2, INF, 11, 0, INF, 5 },
{ 10, 6, INF, 9, INF, 0, INF },
{ INF, INF, INF, 4, 5, INF, 0 } };
int A[VERTICES][VERTICES];
printA(int n) {
int i, j, k;
printf("===============================\n");
for (i = 0; i<n; i++) {
for (j = 0; j<n; j++) {
if (A[i][j] == INF) {
printf("INF ");
}
else printf("%3d ", A[i][j]);
}
printf("\n");
}
printf("===============================\n");
}
void floyd(int n) {
int i, j, k;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
A[i][j] = weight[i][j];
}
}
for (k = 0; k<n; k++) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (A[i][k] + A[k][j] < A[i][j]) {
A[i][j] = A[i][k] + A[k][j];
}
}
}
printA(n);
}
}
void main()
{
floyd(VERTICES);
}
- 두 개의 정점 사이의 최단 경로를 찾는 Dijkstra의 알고리즘은 시간 복잡도가 O(n²)이므로, 모든 정점 쌍의 최단 경로를 구하려면 Dijkstra의 알고리즘을 n번 반복해야 하고, 따라서 전체 복잡도는 O(n³)이 됨.
- 한 번에 모든 정점 간의 최단 경로를 구하는 Floyd의 알고리즘은 3중 반복문이 실행되므로 시간 복잡도가 O(n³)으로 표현되고, 이는 Dijkstra의 알고리즘과 비교해도 차이가 없다고 할 수 있음.
- 그러나 Floyd의 알고리즘은 매우 간결한 반복 구문을 사용하므로 Dijkstra의 알고리즘보다 상당히 빨리 모든 정점 간의 최단 경로를 찾을 수 있음.
[위상 정렬]
- 방향 그래프에서 간선 <u, v>가 있다면 정점 u는 정점 v를 선행함.
- 방향 그래프의 위상 정렬(topological sort) : 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것
- 방향 그래프를 대상으로 위상 정렬을 하기 위한 알고리즘은 간단함.
- 먼저 진입 차수가 0인 정점을 선택하고, 선택된 정점과 여기에 부속된 모든 간선을 삭제함.
- 이와 같이 진입 차수 0인 정점의 선택과 삭제 과정을 반복해서 모든 정점이 선택 및 삭제되면 알고리즘이 종료됨.
- 진입 차수 0인 정점이 여러 개 존재할 경우 어느 정점을 선택하여도 무방함. (따라서 하나의 그래프에는 복수의 위상 순서가 있을 수 있음.)
- 이 과정에서 선택되는 정렬의 순서를 위상 순서(topological order)라 함.
- 위의 과정 중에 그래프에 남아 있는 정점 중에 진입 차수 0인 정점이 없다면, 이러한 그래프로 표현된 프로젝트는 실행 불가능한 프로젝트가 되고 위상 정렬 알고리즘은 중단됨.
- 그래프 위상 정렬 프로그램
// 그래프 위상 정렬 프로그램
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50
#define MAX_STACK_SIZE 100
typedef struct GraphNode
{
int vertex;
struct GraphNode *link;
} GraphNode;
typedef struct GraphType {
int n; // 정점의 개수
GraphNode *adj_list[MAX_VERTICES];
} GraphType;
typedef int element;
typedef struct {
element stack[MAX_STACK_SIZE];
int top;
} StackType;
// 그래프 초기화
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++;
}
// 간선 삽입 연산, 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 init(StackType *s) {
s->top = -1;
}
// 공백 상태 검출 함수
int is_empty(StackType *s) {
return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s) {
return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item) {
if (is_full(s)) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
else s->stack[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s) {
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->stack[(s->top)--];
}
// 피크함수
element peek(StackType *s) {
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->stack[s->top];
}
// 위상정렬을 수행한다.
int topo_sort(GraphType *g) {
int i;
StackType s;
GraphNode *node;
// 모든 정점의 진입 차수를 계산
int *in_degree = (int *)malloc(g->n * sizeof(int));
for (i = 0; i < g->n; i++) { // 초기화
in_degree[i] = 0;
}
for (i = 0; i < g->n; i++) {
GraphNode *node = g->adj_list[i];//정점 i에서 나오는 간선들
while (node != NULL) {
in_degree[node->vertex]++;
node = node->link;
}
}
// 진입 차수가 0인 정점을 스택에 삽입
init(&s);
for (i = 0; i < g->n; i++) {
if (in_degree[i] == 0) push(&s, i);
}
// 위상 순서를 생성
while (!is_empty(&s)) {
int w;
w = pop(&s);
printf("%d", w); //정점 출력
node = g->adj_list[w]; //각 정점의 진입 차수를 변경
while (node != NULL) {
int u = node->vertex;
in_degree[u]--; //진입 차수를 감소
if (in_degree[u] == 0) push(&s, u);
node = node->link; // 다음 정점
}
}
free(in_degree);
return (i == g->n); // 반환값이 1이면 성공, 0이면 실패
}
void main()
{
GraphType g;
graph_init(&g);
insert_vertex(&g, 0);
insert_vertex(&g, 1);
insert_vertex(&g, 2);
insert_vertex(&g, 3);
insert_vertex(&g, 4);
insert_vertex(&g, 5);
//정점 0의 인접 리스트 생성
insert_edge(&g, 0, 2);
insert_edge(&g, 0, 3);
//정점 1의 인접 리스트 생성
insert_edge(&g, 1, 3);
insert_edge(&g, 1, 4);
//정점 2의 인접 리스트 생성
insert_edge(&g, 2, 3);
insert_edge(&g, 2, 5);
//정점 3의 인접 리스트 생성
insert_edge(&g, 3, 5);
//정점 4의 인접 리스트 생성
insert_edge(&g, 4, 5);
//위상 정렬
topo_sort(&g);
}
내용 출처 : C언어로 쉽게 풀어쓴 자료구조 (천인국 외 지음, 생능출판사)
'Computer Science > Data Structure' 카테고리의 다른 글
| [C++] 이진 탐색 트리(Binary Search Tree) (0) | 2021.05.16 |
|---|---|
| [C++] 트리 순회(Tree Traversal) (0) | 2021.05.15 |
| [C] 탐색(Search) (0) | 2017.06.21 |
| [C] 해싱(Hashing) (0) | 2017.06.20 |
| [C] 정렬(Sorting) (0) | 2017.06.18 |
| [C] 우선순위 큐(Priority Queue) (0) | 2017.06.17 |
| [C] 트리(Tree) (0) | 2017.06.01 |
| [C] 큐(Queue) (0) | 2017.05.23 |
