내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.
이번 12장 책 코드에 중간중간 오류코드들이 보인다... 이해를 조금 방해하는 수준이다.
1) 12장. 가중치 그래프(Weighted Graph)
가중치 그래프는 이전에 만들었던 AdjMatGraph class를 상속하여 사용한다.
이전에 사용했던 인접행렬에서는 간선이 있으면 1 없으면 0을 행렬에 저장했지만, 이번에는 가중치값을 행렬에 저장하였다.
일정 범위를 두고 그 범위 안의 값이면 간선이 있고, 이를 벗어나는경우는 간선이 없다고 여긴다.
WGraph.h
#pragma once
#include "AdjMatGraph.h"
const int inf = 100;
class WGraph : public AdjMatGraph {
public:
void insertEdge(int u, int v, int weight) {
if (weight > inf) weight = inf;
setEdge(u, v, weight);
}
bool hadEdge(int i, int j) { return (getEdge(i, j) < inf); }
void load(char* filename) {
FILE* fp = fopen(filename, "r");
if (fp != NULL) {
int n, val;
fscanf(fp, "%d", &n);
for (int i = 0; i < n; i++) {
char str[80];
fscanf(fp, "%s", str);
insertVertex(str[0]);
for (int j = 0; j < n; j++) {
fscanf(fp, "%d", &val);
insertEdge(i, j, val);
}
}
fclose(fp);
}
}
};책의 코드가 부분부분 틀린부분이 있는데 논리적으로 흐름을 따르면 수정가능한 부분들이다.
최소 비용 신장 트리
통신, 도로, 유통망 등은 이들의 비용, 시간에 따른 가중치를 간선에 할당할 수 있다.
이러한 연결망을 최소비용으로 구축하고자 한다면, 연결망에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결해야 한다.
이때 최소 비용 신장 트리 (MST: minimum spanning tree)가 필요하다.
이는 어떤 그레프의 신장 트리들 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다.
이를 해결하기 위한 방법으로 Kruskal과 Prim 의 알고리즘에 대하여 배웠다.
◆ Kruskal의 MST
Kruskal 알고리즘은 greedy method 알고리즘 설계에서 중요한 기법중 하나이다.
greedy method는 어떤 결정을 해야할때 마다 "그 순간에 최적" 이라고 생각되는 것을 선택하는 방법이다.
중요한 것이 순간순간 최적의 선택을 모아 만들어진 최종적인 결과가 "궁극적으로 최적" 이라는 보장은 없다.
따라서 greedy는 항상 최적의 답을 주는지 반드시 검증해야한다. Kruskal은 최적의 해답을 준다고 증명되어있다.
Kruskal은 각 단계에서 사이클을 이루지 않는 최소 비용의 간선을 선택해야 한다. 우선 알고리즘을 확인해 보자.
kruskal()
1. 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2. 가장 가중치가 작은 간선 e를 뽑는다.
3. e를 신장 트리에 넣을 경우 사이클이 생기면 삽입하지 않고 2번으로 이동한다.
4. 사이클이 생기지 않으면 최소 신장 트리에 삽입한다.
5. n-1개의 간선이 삽입될 때 까지 2번으로 이동한다.여기서 중요한 것 이 사이클이 생기는지를 어떻게 검사할것인가? 가 중요하다.
이미 선택된 간선들의 집합에 새로운 간선이 추가될때 사이클이 생성된다면 그 간선은 삭제해야한다.
따라서 지금 추가하는 간선의 양 끝이 같은 집합에 속해 있는지를 먼저 검사해야 한다.
이를 위해 사용하는 방식이 union-find 연산 이다.
◆ union-find 연산
union(x, y)는 원소 x와 y가 속해있는 집합을 input으로 하여 합집합을 ouput으로 만든다. find(x)는 여러 집합들 중에서 원소 x가 속해있는 집합을 반환하는 연산이다. 다음과 같이 5개의 정점 집합이 있다고 해보자.
{1}, {2}, {3}, {4}, {5}
여기에 union(1, 4), union(5, 2)를 하면 다음과 같이 변경된다.
{1, 4}, {2, 5}, {3}
여기서 한번더 union(4, 5)를 수행하면 다음과 같이 된다.
{1, 4, 2, 5}, {3}
find(4)를 하면 {1, 4, 2, 5}가 반환된다.
정점의 집합은 tree로 구현하는 것이 가장 효율적이다. 이 경우 하나의 트리가 하나의 집합을 나타내며, 트리의 노드 각각이 집합의 원소가 된다. 집합은 트리의 루트에 의해 대표된다.
간선 (u, v)가 사이클을 만드는지 알기위해서는 u와 v가 같은 집합에 있는지를 확인해야 한다.
예를 들어 바로 위의 사진에서 5와 3을 연결하면 사이클이 생기지 않지만, 4와 5를 연결하면 사이클이 생긴다.
이 둘간의 차이는 3과 5는 서로 다른집합에 있다는 것 이다.
union-find 연산을 처리하기 위해 정점 집합 클래스를 만든다. 그래프의 정점 수만큼 int 배열 parent가 필요하다.
배열의 각 항목은 각 정점이 속한 집합의 부모 정점 index를 나타낸다.
배열의 값이 -1인 경우는 그 정점 스스로가 root라는 것을 의미하며, 0에서 정점개수-1 사이의 값이면 어떤 집합에 속한 정점임을 의미한다.
다음 코드에서 findSet(v)은 정점 v가 속한 집합의 대표정점을 반환하고, unionSets(u, v)는 정점 u와 v를 하나의 합집합으로 만드는 연산이다.
VertexSets.h
#pragma once
const int max_vtxs = 20;
class VertexSets {
int parent[max_vtxs];
int nSets;
public:
explicit VertexSets(const int& n) : nSets(n) {
for (int i = 0; i < nSets; i++)
parent[i] = -1;
}
bool isRoot(const int& i) { return parent[i] < 0; }
int findSet(int v) {
while (!isRoot(v)) v = parent[v];
return v;
}
void unionSets(int s1, int s2) { // 집합 s1을 집합 s2에 합침
parent[s1] = s2; // parent[s1]이 s2를 가리킴. s1은 더이상 root가 아님
nSets--; // 집합의 수가 하나 줄어듬
}
};정점 집합 class가 구현되었으니 Kruskal 알고리즘을 구현할 수 있다. 간선의 정렬을 위해서 최소 힙을 사용한다.
최소 힙에 모든 간선을 삽입한 후 하나씩 꺼내면 가중치가 작은것 부터 나온다.
이러한 힙을 사용하여 가중치가 작은 간선부터 차례로 연결하다보면 완성된다.
책이 여기서부터 틀린부분이 많아진다... 예시로 설명하는 소스코드가 이상하다...
◆ Prime의 MST
Prime은 정점에서부터 시작하여 트리를 단계적으로 확장해나가는 방식이다.
처음에 시작정점이 트리에 삽입되고, 이후 인접 정점들중 간선의 가중치가 가장 낮은 정점을 트리에 삽입한다.
이 과정을 트리가 n-1 개의 간선을 가질때 까지 계속된다.
Prim()
1. 그레프에서 시작 정점을 선택하여 초기 트리를 만든다.
2. 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v를 선택한다.
3. 이 정점 v와 이때의 간선을 트리에 추가한다.
4. 모든 정점이 삽입될 때 까지 2번으로 이동.Kruskal이 간선을 기반이라면, Prime은 정점을 기반으로 한다. 즉 이전에 만들어진 신장 트리를 확장해나가는 방식 이다.
prim알고리즘은 구현을 위해서 고려해야할 사할들이 많다. 대표적으로 현재 tree에 인접한 정점들중 가장 가까운 정점을 찾는 과정이다. 이를 위해서 dist 라는 배열을 이용한다.
이 dist는 정점의 개수만큼 요소를 갖으며, dist[i]는 기존의 신장트리에서 i번째 정점 까지의 가장 가까운 거리를 저장한다. 말로만 들으면 이해가 안갈수 있다 다음 그림을 확인해 보자.
위의 그림을 보면 녹색 태두리 라인 안의 집합이 tree를 구성하고 있다. tree로부터 6번 정점 까지의 가장 가까운 거리 즉, dist[6]는 29가 되는 상황이다.
처음 tree가 만들어 질때(1번 원소만 포함할때)는 dist[1]만이 0을 갖고 나머지 정점의 dist들은 모두 무한대의 값을 갖는다. 처음에 트리에 시작 정점만 있으니 당연하다.
정점들이 tree에 추가되면서 각 정점의 dist값은 갱신된다. 위의 그림에서 tree에 5번 정점이 추가된다고 해보자. 즉 다음 그림처럼 말이다. 참고로 추가되기 전의 dist[5]는 11이다.
이제 dist[5]의 값은 0이 되었다. tree이 포함되어버렸으니 말이다!.
또한 5번 정점과 인접한 정점 6에서도 변화가 생기는데 이전 그림에서는 dist[6]은 29의 가중치를 나타내지만, 5번 정점이 tree에 추가된 이후 dist[6] 또한 16으로 변경되었다.
즉 새롭게 tree에 추가된 정점 u에 인접한 정점 v의 경우 기존의 dist[v]보다 간선 (u, v)의 가중치가 적으면 이제 dist[v]는 간선 (u, v)의 가중치가 되어야 한다.
이 과정을 모든 정점이 트리에 포함될때 까지 진행한다.
하.. 여기까지 책을 읽으면서 dist[i]배열에 관한 설명을 다시 내 나름데로 재해석 하였다.
처음 읽을때 설명이 잘 이해되지 않아 참고한 싸이트가 있으니 이곳도 같이 읽어보면 도움될 것 이다.
Prim 함수에서는 그래프의 각 정점이 이미 MST에 포함되었는지를 나타내기 위해 selected 배열을 사용한다.
WGraphMST.h (MST 기능이 추가된 가중치 그래프 클래스)
#pragma once
#include "MinHeap.h"
#include "WGraph.h"
#include "VertexSets.h"
class WGraphMST : public WGraph {
public:
int getMinVertex(bool* selected, int* dist) {
int minv = 0;
int mindist = inf;
for (int v = 0; v < size; v++)
if (!selected[v] && dist[v] < mindist) {
mindist = dist[v];
minv = v;
}
return minv;
}
void Prim(int s) {
bool selected[max_vtxs];
int dist[max_vtxs];
for (int i = 0; i < size; i++) {
dist[i] = inf;
selected[i] = false;
}
dist[s] = 0;
for (int i = 0; i < size; i++) {
int u = getMinVertex(selected, dist);
selected[u] = true;
if (dist[u] == inf) return;
printf("%c ", getVertex(u));
for (int v = 0; v < size; v++)
if (getEdge(u, v) != inf)
if (!selected[v] && getEdge(u, v) < dist[v])
dist[v] = getEdge(u, v);
}
printf("\n");
}
};또 책에는 위 코드가 떡하고 써있는데 생각없이 그냥 읽으면 뭔 내용인지 모르겠더라... 우선 getMinVertex() 에 대하여 살펴보자.
이 함수는 selected와 dist배열의 주소값을 인자로 받아 지금 까지 선택되지 않은 정점들 중에서 dist값이 가장 작은 정점을 반환해준다. 즉 MST에 아직 포함되지 않은 정점들 중에서 MST와 거리가 최소인 정점을 반환해주는 것 이다.
int getMinVertex(bool* selected, int* dist) {
int minv = 0;
int mindist = inf;
for (int v = 0; v < size; v++)
if (!selected[v] && dist[v] < mindist) {
mindist = dist[v];
minv = v;
}
return minv;
}인자로 주소값 2개를 받고있다. 이후 함수 내부에서 minv를 0으로 초기화 해 준다.
minv는 MST와 가장 가까운 거리의 정점 을 의미하며 처음에는 뭔지 모르니 일단 0으로 초기화 해 둔다.
mindist는 inf값으로 초기화를 했는데, 이는 무한의 거리를 의미한다.
현실적으로 진짜 무한값을 줄수는 없기때문에 적당히 큰 값을 잡아 상수로 만든것 이다.
이제 for문으로 모든 정점을 돌면서 ( 아직 tree에 포함되있지 않고 + mindist보다 값이 작은 ) 정점 v를 선택한다.
그림을 보면서 생각해 보자.
우선 조건문을 만족하는 4번 정점이 맨처음 선택될 것 이다. 이때 mindist값이 inf에서 22로 변경된다. minv 또한 4번이 된다.
다음으로 5번이 선택된다. 하지만 dist[5]는 inf로 조건문을 만족하지 못한다.
다음으로 6번이 선택된다. dist[6]은 29이며 mindist값인 22보다 크니 조건을 만족하지 못한다.
다음으로 7번이 선택된다. 이또한 dist값 27은 22보다 크니 조건을 만족하지 못한다.
따라서 minv는 4번이 되며 이를 반환한다.
void Prim(int s) {
bool selected[max_vtxs]; // 정점이 이미 포함되었는가?
int dist[max_vtxs]; // 거리
for (int i = 0; i < size; i++) { // 배열 초기화
dist[i] = inf;
selected[i] = false;
}
dist[s] = 0; // 시작 지점 설정
for (int i = 0; i < size; i++) {
int u = getMinVertex(selected, dist);
selected[u] = true;
if (dist[u] == inf) return; // 거리가 무한이면 안됨
printf("%c ", getVertex(u));
for (int v = 0; v < size; v++)
if (getEdge(u, v) != inf)
if (!selected[v] && getEdge(u, v) < dist[v])
dist[v] = getEdge(u, v);
}
printf("\n");
}prim함수에서 상단은 초기화를 해주고 있다. 이후 시작 정점을 0으로 초기화 해준다.
이후 새로운 정점 u에 최소거리의 정점을 반환해준다. 이후 selected[u]를 true로 변경하여 tree에 포함됨을 선언한후 출력한다.
그다음줄에서 dist의 갱신이 일어난다.
for (int v = 0; v < size; v++)
if (getEdge(u, v) != inf)
if (!selected[v] && getEdge(u, v) < dist[v])
dist[v] = getEdge(u, v);우선 u와 그 인근 정점 v의 간선을 얻어 inf 값이 아니고, 그 v가 선택되지 않았으며 간선 (u, v)값이 dist[v]보다 작다면 dist[v]값을 변경해 준다. 이는 위에서 그림으로 보인적이 있다.
Prim알고리즘은 주 반복문이 정점의 수인 n만큼 반복하고, 내부에서도 n번 반복하니 O(n2)의 시간 복잡도를 갖는다.
최단 경로
최단경로는 가중치 그래프에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.
이를 찾는 알고리즘으로는 Dijkstra와 Floyd 두가지 알고리즘이 있다.
Dijkstra 알고리즘은 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구한다.
이에 비해 Floyd 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구할 수 있다.
◆ Dijkstra 알고리즘
먼저 S를 시작 정점 v로부터의 최단 경로가 이미 발견된 정점들의 집합 이라고 하자.
이 알고리즘에서는 S에 있는 정점만을 거쳐 다른 정점으로 가는 최단거리를 기록하는 배열을 사용한다. 이를 dist라고 하자.
시작 정점 v에서의 dist[v]는 0이다. 가중치는 인접행렬에 저장되므로 인접 행렬을 weight라고 하면 최초에 모든 정점 w에 대해 dist[w] = weight[v][w]가 된다.
v에서 w로 가는 직접적인 간선이 없으면 무한대로 설정한다.
알고리즘의 매 단계에서 S안에 있지 않은 정점들중 최단거리의 정점 즉, dist가 가장작은 정점을 S에 추가한다.
이렇게 S를 추가해도 문제가 없는 것 일까? 이를 증명하는 방식이 재미있다. 다음 그림을 확인해 보자.
S에는 정점 V가 있는상황이다. 간선 1번이 v에서 u까지의 최단 경로인 상황이다.
만약 v에서 w를 거처 u로 가는 경로가 더 짧은 경로가 된다고 가정해 보자. 경로는 2+3이 될것이다.
하지만 경로 2는 항상 경로 1보다 크다. 왜냐하면 현재 dist값이 가장 작은 정점이 u임을 알고있기 때문이다.
따라서 간선1 이 길이가 n 이라면, 간선 2는 최소 n+1 이상이되며, 여기에 간선 3까지 더하면 n+1+a 로 맨처음 가정에 모순된다.
따라서 맨처음 던진 질문인 S를 추가하는 방식에 문제가 없다.
새로운 정점 u가 S에 포함되고 나면 S에 있지 않은 다른 정점들의 dist값을 수정해야 한다.
dist[w] = min(dist[w], dist[u] + weight[u][w])
최단거리 알고리즘을 확인해 보자.
// 입력: 가중치 그래프 G
// 출력: dist 배열, dist[u]는 v에서 u까지의 최단거리
shortestPath(v)
S <- {v}
for 각 정점 W∈G do
dist[w] = weight[v][w];
while 모든 정점이 S에 포함되지 않으면 do
u <- 집합 S에 속하지 않는 정점 중에서 최소 dist 정점;
S <- S∪{u}
for u에 인접하고 S에 있지 않은 각 정점 z do
if dist[u]+weight[u][z] < dist[z]
then dist[z] <- dist[u] + weight[u][z];
◆ Dijkstra 알고리즘 구현
#pragma once
#include "WGraph.h"
class WGraphDijkstra : public WGraph {
int dist[max_vixs];
bool found[max_vixs];
public:
int chooseVertex() {
int min = inf;
int minpos = -1;
for(int i = 0; i < size; i++)
if (dist[i] < min && !found[i]) {
min = dist[i];
minpos = i;
}
}
void ShortestPath(int start) {
for (int i = 0; i < size; i++) { // 초기화
dist[i] = getEdge(start, i);
found[i] = false;
}
found[start] = true; // 시작 노드 방문처리
dist[start] = 0; // 최초 거리
for (int i = 0; i < size; i++) {
printf("Step%2d:", i + 1);
printDistance();
int u = chooseVertex();
found[u] = true;
for (int w = 0; w < size; w++) {
if (found[w] == false)
if (dist[w] > dist[u] + getEdge(u, w))
dist[w] = dist[u] + getEdge(u, w);
}
}
}
void printDistance() {
for (int i = 0; i < size; i++)
printf("%5d", dist[i]);
printf("\n");
}
};DIjkstra 알고리즘은 실행 결과로서 시작 정점으로부터 다른 정점까지의 최단 경로의 거리 정보만을 제공한다. 효율을 위해 위으 최소값을 선택하는 chooseVertex()함수를 우선순위 큐로 대치하면 더 빨라진다.
◆ Floyd 알고리즘
그래프에 존재하는 모든 정점 사이의 최단경로를 구하고자 하면 위으 Dijkstra 알고리즘을 각 정점마다 반복시키면 된다. 하지만 이보다 더 간단한 알고리즘이 있는데 Floyd이다. 플로이드 알고리즘은 다음과 같이 간단한 삼중 반복문으로 표현된다. A의 초기 값은 인접 행렬인 weight가 된다.
floyd(G)
for k <- 0 to n - 1 // k는 거처가는 정점
for i <- 0 to n - 1 // i는 출발
for j <- 0 to n - 1 // j는 도착
A[i][j] = min(A[i][j], A[i][k] + A[k][j])이 알고리즘의 핵심은 거처가는 정점인 k에 있다.
( 정점 u에서 v까지 간선길이 ) vs ( u->k->v 까지의 간선길이합) 을 비교하여 더 작은 값을 인접배열에 갱신한다.
이를 n-1번 반복한다.
#pragma once
#include "WGraph.h"
class WGraphFloyd : public WGraph {
int A[max_vixs][max_vixs];
public:
void ShortestPathFloyd() {
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
A[i][j] = getEdge(i, j); // 초기화
for (int k = 0; k < size; k++) {
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
if (A[i][k] + A[k][j] < A[i][j])
A[i][j] = A[i][k] + A[k][j];
printA();
}
}
void printA() {
printf("=======================================\n");
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (A[i][j] == inf) printf(" INF ");
else printf("%4d ", A[i][j]);
}
printf("\n");
}
}
};
'CS > Data Structure (2021-1)' 카테고리의 다른 글
| [자료구조] C++로 쉽게 풀어쓴 자료구조 : 14장, 탐색 (0) | 2022.01.15 |
|---|---|
| [자료구조] C++로 쉽게 풀어쓴 자료구조 : 13장, 정렬 (0) | 2022.01.15 |
| [자료구조] C++로 쉽게 풀어쓴 자료구조 : 11장, 그래프 (0) | 2022.01.15 |
| [자료구조] C++로 쉽게 풀어쓴 자료구조 : 10장, 힙 (0) | 2022.01.15 |
| [자료구조] C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 9-1 (0) | 2022.01.15 |
댓글