개념정리/자료구조
자료구조 공부 #21 (그래프2)
한반가
2021. 6. 14. 15:20
2021.06.08 - [이론공부/자료구조] - 자료구조 공부 #20 (그래프)
신장 트리
- 그래프 내의 모든 정점을 포함하는 트리
- n개의 정점을 가지는 그래프의 신장트리는 n-1개의 간선을 가진다
신장 트리는 그래프의 최소 연결 부분 그래프 이다.
신장트리는 깊이 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다.
depth_first_search(v):
v 를 방문되었다표시;
for all u ∈ (v에 인접한 정점) do
if (u가 아직 방문되지 않았으면)
then (v,u)를 신장 트리 간선이라고 표시;
depth_first_search(u)
최소비용 신장트리
- 네트워크(그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결
- MST의 응용 (Minimun Spanning Tree) = 최소 비용 신장트리
- 도로 건설 - 도시들을 모두 연결하면서 도로의 길이를 최소가 되도록 하는 문제
- 전기회로 - 단자들을 모두 연결하면서 전선의 길이를 최소로 하는 문제
- 통신 - 전화선의 길이를 최소로 하면서 전화 케이블 망을 구성하는 문제
- 배관 - 파이프를 모두 연결하면서 총길이를 최소로 하는 문제
- kruskal 알고리즘과 prime 알고리즘이 대표적이다.
- MST 조건
- 본래 그래프의 모든 노드를 포함
- 간선의 가중치 합이 최소여야함
- 모든 노드가 서로 연결되어 있어야함
- 트리의 속성을 만족 해야함 (사이클 존재X)
Kruskal의 MST 알고리즘
- 탐욕적인 방법 (Greedy Method)
- 주요 알고리즘 설계기법
- 각 단계에서 최선의 답을 선택하는 과정을 반복함으로써 최종적인 해답에 도달
- 탐욕적인 방법은 항상 최적의 해답을 주는지 검증 필요
- Kruskal MST 알고리즘은 최적의 해답임이 증명됬다.
Union-Find 알고리즘
- 일반적으로 널리 사용되는 알고리즘으로 서로소 집합을 표현할 때 사용하는 알고리즘
- Union-Find 연산
- make-set(x) : 초기화, x를 유일한 원소로 하는 새로운 집합을 생성
- union(x,y) : 합하기. x가 속한 집합과 y가 속한 집합을 합친다. x, y 두집합을 합치는 연산
- find(x) : 찾기, x가 속한 집합의 대표값 (루트 노드 값)을 반환, x가 어떤 집합에 속해있는지 찾는 연산
- Kruskal의 MST 알고리즘에서 사이클 검사에 사용함
알고리즘
더보기
더보기
int parent[MAX_VERTICES];
void set_init(int n) {
for (int i = 0; i < n; i++)
parent[i] = -1;
}
// curr가 속하는 집합을 반환한다.
int set_find(int curr) {
if (parent[curr] == -1)
return curr; // 루트
while (parent[curr] != -1) curr = parent[curr];
return curr;
}
// 두개의 원소가 속한 집합을 합친다.
void set_union(int a, int b) {
int root1 = set_find(a); // 노드 a의 루트를 찾는다.
int root2 = set_find(b); // 노드 b의 루트를 찾는다.
if (root1 != root2) // 합한다.
parent[root1] = root2;
}
C++로 Kruskal 알고리즘 구현
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000
int parent[MAX_VERTICES]; // 부모 노드
// 초기화
void set_init(int n) {
for (int i = 0; i < n; i++)
parent[i] = -1;
}
// curr가 속하는 집합을 반환한다.
int set_find(int curr) {
if (parent[curr] == -1)
return curr; // 루트
while (parent[curr] != -1) curr = parent[curr];
return curr;
}
// 두 개의 원소가 속한 집합을 합친다.
void set_union(int a, int b) {
int root1 = set_find(a); // 노드 a의 루트를 찾는다.
int root2 = set_find(b); // 노드 b의 루트를 찾는다.
if (root1 != root2) // 합한다.
parent[root1] = root2;
}
struct Edge { // 간선을 나타내는 구조체
int start, end, weight;
};
typedef struct GraphType {
int n; // 간선의 개수
struct Edge edges[2 * MAX_VERTICES];
} GraphType;
// 그래프 초기화
void graph_init(GraphType* g) {
g->n = 0;
for (int i = 0; i < 2 * MAX_VERTICES; i++) {
g->edges[i].start = 0;
g->edges[i].end = 0;
g->edges[i].weight = INF;
}
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end, int w) {
g->edges[g->n].start = start;
g->edges[g->n].end = end;
g->edges[g->n].weight = w;
g->n++;
}
// qsort()에 사용되는 함수
int compare(const void* a, const void* b) {
struct Edge* x = (struct Edge*)a;
struct Edge* y = (struct Edge*)b;
return (x->weight - y->weight);
}
// kruskal의 최소 비용 신장 트리 프로그램
void kruskal(GraphType* g) {
int edge_accepted = 0; // 현재까지 선택된 간선의 수
int uset, vset; // 정점 u와 정점 v의 집합 번호
struct Edge e;
set_init(g->n); // 집합 초기화
qsort(g->edges, g->n, sizeof(struct Edge), compare);
printf("크루스칼 최소 신장 트리 알고리즘 \n");
int i = 0;
while (edge_accepted < (g->n - 1)) { // 간선의 수 < (n-1)
e = g->edges[i];
uset = set_find(e.start); // 정점 u의 집합 번호
vset = set_find(e.end); // 정점 v의 집합 번호
if (uset != vset) { // 서로 속한 집합이 다르면
printf("간선 (%d,%d) %d 선택\n", e.start, e.end, e.weight);
edge_accepted++;
set_union(uset, vset); // 두 개의 집합을 합친다.
}
i++;
}
}
int main(void) {
GraphType* g;
g = (GraphType*)malloc(sizeof(GraphType));
graph_init(g);
insert_edge(g, 0, 1, 29);
insert_edge(g, 1, 2, 16);
insert_edge(g, 2, 3, 12);
insert_edge(g, 3, 4, 22);
insert_edge(g, 4, 5, 27);
insert_edge(g, 5, 0, 10);
insert_edge(g, 6, 1, 15);
insert_edge(g, 6, 3, 18);
insert_edge(g, 6, 4, 25);
kruskal(g);
free(g);
return 0;
}교재에서 이용한 코드를 그대로 참고함
Kruskal의 알고리즘 복잡도
- Kruskal 알고리즘은 대부분 간선들을 정렬하는 시간에 좌우 된다
- 사이클 테스트 등의 작접은 정렬에 비해 매우 신속하게 수행된다
- 네트워크 간선 e개를 퀵 정렬과 같은 효율적인 알고리즘으로 정렬 한다면 Kruskal 알고리즘의 시간 복잡도는 O(elog2e)가 된다.
Prim의 MST 알고리즘
- 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해 나감
- 신장 트리 집합에 인접한 정점 중에서 최저 간선으로 연결된 정점 선택하여 신장 트리에 집합 추가함
Kruskal 알고리즘과 Prime 알고리즘 비교
- Kruskal : Edge 기반 - 무조건 최저 간선만을 선택 -> edge의 가중치로 정렬이 필요함
- Prime : Vertex 기반 - 이전 단뎨에서 만들어진 신장 트리를 확장하는 방식
C++로 Pim 구현
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000L
typedef struct GraphType {
int n; // 정점의 개수
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int selected[MAX_VERTICES];
int distance[MAX_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] && (distance[i] < distance[v])) v = i;
return (v);
}
void prim(GraphType* g, int s) {
int i, u, v;
for (u = 0; u < g->n; u++)
distance[u] = INF;
distance[s] = 0;
for (i = 0; i < g->n; i++) {
u = get_min_vertex(g->n);
selected[u] = TRUE;
if (distance[u] == INF) return;
printf("정점 %d 추가\n", u);
for (v = 0; v < g->n; v++)
if (g->weight[u][v] != INF) {
if (!selected[v] && g->weight[u][v] < distance[v]) {
distance[v] = g->weight[u][v];
}
}
}
}
int main(void) {
GraphType g = { 7,
{ { 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 } }
};
prim(&g, 0);
return 0;
}
코드 구조 이해, 결과
Prim의 알고리즘 복잡도
- 주 반복문이 정점의 수 n만큼 반복, 내부 반복문이 n번 반복하므로 Prim의 알고리즘은 O(n^2)의 복잡도를 가진다
- 희소 그래프 - edge의 수가 얼마 없는 그래프
- O(elog2e)인 Kruskal 알고리즘이 유리
- 밀집 그래프 - edge의 수가 최대 간선 수에 가까운 그래프
- O(n^2)인 Prim 알고리즘이 유리
최단 경로
- 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로
- 간선의 가중치는 비용, 거리, 시간 등
가중치 인접행렬
최단경로 알고리즘
- Dijkstra 알고리즘 : 하나의 시작 정점에서 다른 정점까지의 최단경로 계산
- Floyd 알고리즘 : 모든 정점에서 다른 모든 정점까지의 최단경로를 계산
Dijkstra의 최단경로 알고리즘
- 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로 찾는다
- 집합 S : 시작 정점 v로부터의 최단 경로가 이미 발견된 정점들의 집합
- distance 배열 : 최단 경로가 알려진 정점들만을 이용한 다른 정점들까지의 최단 경로 길이
- 매 단계에서 가장 distance 값이 작은 정점을 S에 추가
S = { 0, 4 }
distance[0] = 0
distance[1] = min(distance[1], distance[4]+weight[4][1] = min(7, 3+2) = 5
distance[2] = min(distance[2], distance[4]+weight[4][2] =
distance[3] = min(distance[3], distance[4]+weight[4][3] = min(, 3+11) =
distance[4] = 3
distance[5] = min(distance[5], distance[4]+weight[4][5] = min(10, 3+) = 10
distance[6] = min(distance[6], distance[4]+weight[4][6] = min(, 3+5) = 8
C++로 구현
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000000 /* 무한대 (연결이 없는 경우) */
typedef struct GraphType {
int n; // 정점의 개수
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
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 print_status(GraphType* g) {
static int step = 1;
printf("STEP %d: ", step++);
printf("distance: ");
for (int i = 0; i < g->n; i++) {
if (distance[i] == INF)
printf(" * ");
else
printf("%2d ", distance[i]);
}
printf("\n");
printf(" found: ");
for (int i = 0; i < g->n; i++)
printf("%2d ", found[i]);
printf("\n\n");
}
void shortest_path(GraphType* g, int start) {
int i, u, w;
for (i = 0; i < g->n; i++) { /* 초기화 */
distance[i] = g->weight[start][i];
found[i] = FALSE;
}
found[start] = TRUE; /* 시작 정점 방문 표시 */
distance[start] = 0;
for (i = 0; i < g->n - 1; i++) {
print_status(g);
u = choose(distance, g->n, found);
found[u] = TRUE;
for (w = 0; w < g->n; w++)
if (!found[w])
if (distance[u] + g->weight[u][w] < distance[w])
distance[w] = distance[u] + g->weight[u][w];
}
}
int main(void) {
GraphType g = { 7,
{ { 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 } }
};
shortest_path(&g, 0);
return 0;
}
Dijkstra의 최단 경로 알고리즘 복잡도
- 네트워크에 n개의 정점이 있다면, Dijkstra의 최단경로 알고리즘은 주 반복문을 n번 반복하고 내부 반복문을 2n번 반복하므로 O(n^2)의 시간 복잡도를 가진다
Floyd 알고리즘
- Dijkstra 알고리즘은 정점의 수 만큼 반복수행으로 최단 경로를 찾는다
- Floyd 알고리즘은 모든 정점사이의 최단 경로를 한번에 찾아준다.
- 2차원 배열을 이용하여 3중 반복하는 Loop로 구성
- 인접행렬 weight[i][j] 구성 방법은 동일
- 2차원 배열을 A라고 하면, 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가지가 나누어진다- 정점 k를 거치지 않은 경우
- A(k)[i][j]는 k보다 큰 정점은 통과하지 않으므로 최단거리는 여전히 A(k-1)[i][j]이다
- 정점 k를 거치는 경우
- j에서 k까지의 최단거리 A(k-1)[i][j]에 k에서 j까지의 최단거리 A(k-1)[k][j]를 더한값
- 정점 k를 거치지 않은 경우
일일이 넘어가면서 배열에 값을 채워나가는 과정을 가지는듯 하다
.Floyd의 최단경로 알고리즘 복잡도
- 네트워크에 n개의 정점이 있다면, Floyd의 최단경로 알고리즘은 3중 반복실행되므로 시간복잡도는 O(n^3) 이다
- 모든 정점상의 최단경로를 구하려면 Dijkstra의 알고리즘 O(n^2)을 n번 반복해도 되며, 이경우 전체 복잡도는 O(n^3)가 된다
- Dijkstra와 Floyd 두 알고리즘의 비교에서 보면 시간복잡도는 동일한 결과를 나타내고 있지만 Floyd 알고리즘이 매우 간결한 반복구문을 사용하므로 Dijkstra 알고리즘보다 빨리 모든 정점 간의 최단 경로를 찾을 수 있다.
위상 정렬
- 방향 그래프에서 간선 <u, v>가 있다면 정점 u는 정점 v를 실행함
- 방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열
- 선수 과목은 과목들의 선행 관계 표현
- 위상 순서
- (0, 1, 2, 3, 4, 5), (1, 0, 2, 3, 4, 5)
- (2, 0, 1, 3, 4, 5)는 위상 순서가 아님
- 2번 정점이 0번 정점 앞에 오기 때문
C++ 구현
// 위상 정렬을 수행한다.
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);
printf("\n");
return (i == g->n); // 반환값이 1이면 성공, 0이면 실패
}
int main(void) {
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);
// 동적 메모리 반환 코드 생략
return 0;
}