HW13
1. 강의 내용 정리(Weighted graph, shortest path algorithm, minimum spanning tree)
Weighted graph란 가중치 그래프로서 간선에 가중치가 할당된 그래프이다.
예를 들어, 정점과 그들을 잇는 간선이 있으면 간선의 길이가 가중치라고 생각할 수 잇다.
이 가중치 그래프는 G = ( V, E , w)로 표현된다.
정점, 간선, 가중치
p를 경로라고하면 경로의 강도는 w(p)
adj가 이전 주에서는 그저 간선의 유무를 나타내는 0과 1뿐이었다면 이제는 간선의 가중치를 나타내기 위해 사용한다. 가중치는 반드시 양수이어야 한다.
adj의 값이 가중치로는 절대 나올수없는 infinite한 값을 가지면 간선이 존재하지 않는 것으로 판단한다.
MST, minimum spanning tree(최소 비용 신장트리)는 가중치 합이 최소인 신장트리를 말한다.
네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결한다.
MST의 조건 3가지
간선의 가중치의 합이 최소이어야 한다.
반드시 n-1개의 간선만 사용해야한다.
사이클이 포함되어서는 안된다.
Kruskal의 MST 알고리즘은 greedy method이다. 최적의 해답이다.
언제나 그 순간에 최적인 것만 선택하는 방법이다.
1. 모든 간선을 가중치에 따라 오름차순으로 정리
2. 가장 가중치가 적은 간선을 뽑는다.
3. 해당 간선을 트리에 넣을때 사이클이 생기면 삽입X 2번으로 돌아간다
4. 사이클이 생기지 않으면 MST에 삽입
5. n-1개의 간선이 삽입될때까지 2번으로 돌아간다.
연결될 정점이 서로같은 집합에 포함되면 사이클이 생기므로 유의
사이클 검사를 해서 사이클이 생기는 지 파악한다.
사이클 검사를 위한 union-find 함수를 만들어서 처리한다.
부모 정점은 -1.
최초에는 모든 정점들이 각각 고유한 집합이 되어야하므로 배열을 다 -1로 초기화한다.
prim의 MST알고리즘은 하나의 정점에서 시작해서 트리를 단계적으로 확장해가는 방법
인접한 애들 중에서 가중치가 제일 작은 정점을 선택해서 트리를 확장한다.
kruskal은 인접이 아니라 오름차순으로 가중치 정렬하고 나서 선택
kruscal이 간선을 기반으로하면 prim은 정점을 기반으로 한다.
Shortest path, 최단경로는 가중치 그래프에서 한 정점과 다른 정점을 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.
()가 경로
Dijkstra 알고리즘은 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구한다.
Floyd 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구할 수 있는 방법이다.
Dijsktra의 최단 경로 알고리즘은
집합 s = 이미 시작 정점 v로부터 최단 경로가 이미 발견된 정점들의 집합
s에 있는 정점들만 거쳐서 다른 정점으로 갈거임
이 최단 거리를 기록하는 배열을 dist라고 한다.
최초에는 dist[w] = weight[v][w]
w로 가는 최단거리는 v와w의 가중치와 같다
prim과 비슷하게 전개
정점이 추가될때마다 가중치를 더해서 갱신
infinite으로 되어있던 값들을 시작점에서 걸리는 가중치로 갱신
Floyd의 최단 경로 알고리즘
다익스트라는 정점의 수만큼 반복하여 실행하면 된다면
플로이드는 한꺼번에 찾아준다.
2차원 배열을 이용해서 3중반복을 하는 루프로 구성되어있다.
인접 행렬을 만든다.
같은 정점이라면 0
간선이 존재하지 않으면 infinite으로 표현한다.
정점 k가 추가된다고 생각하면
k를 거치지 않아도 최단거리가 나온다면 그대로이지만
k를 거쳐야 최단거리가 된다면 k이전의 최단 경로 + k이후의 최단경로를 합친다.
2. 제공한 코드 이해
#define MAX_VTXS 100 //최대 정점의 갯수는 100으로 하였다.
#define INF 9999 //간선의 유무를 판단하는 infinite한 값을 9999로 하였다.인접행렬 그래프를 표현하는 클래스
class AdjMatGraph {
protected:
int size; // 정점의 갯수
char vertices[MAX_VTXS]; //정점을 담는 array
int adj[MAX_VTXS][MAX_VTXS]; // 2차원 인접행렬
public:
AdjMatGraph() { reset(); } //초기화
char getVertex(int i) { return vertices[i]; } //정점의 이름을 가져오는 함수
int getEdge(int i, int j) { return adj[i][j]; } //정점 i와 정점j의 간선을 가져오는 함수
void setEdge(int i, int j, int val) { adj[i][j] = val; } //정점 i와 정점j의 간선을 설정
bool isEmpty() { return size == 0; } //비었는지 확인
bool isFull() { return size >= MAX_VTXS; } //꽉 찼는지 확인
void reset() {
size = 0; //사이즈를 0으로 초기화
for (int i = 0; i < MAX_VTXS; ++i)
for (int j = 0; j < MAX_VTXS; ++j)
setEdge(i, j, 0); //모든 행렬의 값의 가중치를 0으로 초기화
}
void insertVertex(char name) { //정점을 삽입
if (!isFull()) vertices[size++] = name; //정점을 담는 배열이 꽉차있지 않으면 size를 늘리고 마지막에 파라미터를 추가
else cout << "ERROR : 그래프 정점 개수 초과" << endl;
}
void insertEdge(int u, int v) { //간선 추가하는 함수, 유무만 0과 1로 표현
setEdge(u, v, 1);
setEdge(v, u, 1);
}
void display() {
cout << size << endl;
for (int i = 0; i < size; ++i) {
cout << getVertex(i) << " ";
for (int j = 0; j < size; ++j)
cout << getEdge(i, j) << "\t";
cout << endl;
}
}
};가중치 그래프(Weighted graph)를 표현하는 클래스
class WGraph : public AdjMatGraph {
public:
void insertEdge(int u, int v, int weight) { //간선 추가하는 함수, 정점 u, 정점 v, 가중치 weight
if (weight > INF) weight = INF; // infinite보다 값이 크면 9999로 가중치를 정한다. 즉, 간선이 없음을 표현
setEdge(u, v, weight); //간선을 가중치의 값대로 설정
}
bool hasEdge(int i, int j) { return (getEdge(i, j) < INF); }
// 정점 i와 정점 j의 간선이 있는지 확인하는 함수
// 정점 i와 정점 j의 간선이 9999보다 작으면 true 크거나 같으면 false를 반환
void load(string filename) { //파일에서 그래프값을 가져와서 그래프를 구성하는 함수
ifstream fp(filename);
if (fp.is_open()) {
int n, val;
fp >> n; // 정점의 전체 개수
for (int i = 0; i < n; i++) {
char str[80];
int val;
fp >> str; // 정점의 이름
insertVertex(str[0]); // 정점 삽입
for (int j = 0; j < n; j++) {
fp >> val; // 간선 정보
insertEdge(i, j, val); // 간선 삽입
}
}
}
else cout << "File can not be found !" << endl;
fp.close();
}
};정점 집합 클래스(Union-Find 연산), 사이클이 생기는지 확인용
합집합을 찾는 연산
#define MAX_ELEMENT 200 //요소의 최대 갯수
class VertexSets { //정점의 집합?
int parent[MAX_VTXS]; // 부모 정점의 id
int nSets; // 집합의 개수
public:
VertexSets(int n) : nSets(n) { //클래스 생성자
for (int i = 0; i < nSets; i++) //입력받은 정점갯수만큼 -1만들기
parent[i] = -1; // 초기에 모든 정점이 고유의 집합에 속함
}
bool isRoot(int i) { return parent[i] < 0; }// -1이면 root
int findSet(int v) { // v가 속한 집합을 찾아 root 반환
while (!isRoot(v)) v = parent[v]; // v가 속한 집합의 루트를 찾음
return v;
}
void unionSets(int s1, int s2) { // 집합 s1을 집합 s2와 합침, 정점들이 같은 그래프 안에 속하도록
parent[s1] = s2; // s1의 parent를 s2로 설정
nSets--; // 2개의 집합을 합쳐서 집합 개수는 1 감소
}
};힙노드 클래스
class HeapNode {
int key; // Key 값: 간선의 가중치
int v1; // 정점 1
int v2; // 정점 2
public:
HeapNode(int k = 0, int u = 0, int v = 0) : key(k), v1(u), v2(v) { } // 정점u, 정점 v, 가중치 k
void setKey(int k) { key = k; } //가중치 설정
void setKey(int k, int u, int v) { //정점 두개와 가중치 설정
key = k; v1 = u; v2 = v;
}
int getKey() { return key; }
int getV1() { return v1; }
int getV2() { return v2; }
void display() {
cout << "\t" << "(" << v1 << "-" << v2 << ") -- " << key << endl;
}
};최소힙을 구현하는 클래스
class MinHeap {
HeapNode node[MAX_ELEMENT]; //노드 최대갯수만큼 배열 만들기
int size; //노드 갯수
public:
MinHeap() : size(0) { } //일단 0개로 시작
bool isEmpty() { return size == 0; } //비었나
bool isFull() { return size == MAX_ELEMENT - 1; } // 찼나
HeapNode& getParent(int i) { return node[i / 2]; } //부모주소를 반환
HeapNode& getLeft(int i) { return node[i * 2]; } //왼쪽 자식
HeapNode& getRight(int i) { return node[i * 2 + 1]; } //오른쪽 자식
// 삽입 함수
void insert(int key, int u, int v) { //정점 두개와 가중치 삽입
if (isFull()) return; //꽉차있으면 종료
int i = ++size; //사이즈를 늘리고
while (i != 1 && key < getParent(i).getKey()) { //루트노드가 아니고 키값이 부모노드의 키값보다 작다면
node[i] = getParent(i); //부모노드와 자리바꾸기
i /= 2;
}
node[i].setKey(key, u, v); //삽입
}
// 삭제 함수
HeapNode remove() {
if (isEmpty()) return NULL;
HeapNode root = node[1]; //비어있지 않다면 root에 루트노드 저장
HeapNode last = node[size--]; //사이즈 1 줄이기
int parent = 1;
int child = 2;
while (child <= size) {
if (child < size
&& getLeft(parent).getKey() > getRight(parent).getKey())
child++;
if (last.getKey() <= node[child].getKey()) break;
node[parent] = node[child];
parent = child;
child *= 2;
}
node[parent] = last;
return root;
}
};Kruskal의 최소 비용 신장 트리 프로그램
class WGraphMST : public WGraph {
public:
void Kruskal() { // kruskal의 최소 비용 신장 트리 프로그램
MinHeap heap;
// 1. 오름차순정렬 (heap sort)
for (int i = 0; i < size - 1; i++)
for (int j = i + 1; j < size; j++)
if (hasEdge(i, j))
heap.insert(getEdge(i, j), i, j); // 모든 간선 삽입
VertexSets set(size); // size개의 집합을 만듦
int edgeAccepted = 0; // 선택된 간선의 수
while (edgeAccepted < size - 1) { // 4.(n-1)개의 edge가 삽입될때까지
HeapNode e = heap.remove(); // 2.가장 작은 edge 선택
int uset = set.findSet(e.getV1()); // v1이 속한 집합의 루트 반환
int vset = set.findSet(e.getV2()); // v2가 속한 집합의 루트 반환
if (uset != vset) { // 3.사이클 생기지 않으면 MST삽입
cout << "간선 추가 : " << getVertex(e.getV1()) << " - " << getVertex(e.getV2()) << " (비용 : " << e.getKey() << ")" << endl;
set.unionSets(uset, vset); // 두개의 집합을 합함.
edgeAccepted++;
}
}
}
};Dijkstra알고리즘의 최단 경로 탐색 기능이 추가된 그래프, prim방식처럼 인접을 보고 가중치 제일 낮은 걸로 가기
// Dijkstra알고리즘의 최단 경로 탐색 기능이 추가된 그래프
class WGraphDijkstra : public WGraph {
int path[MAX_VTXS];
int dist[MAX_VTXS]; // 시작노드로부터의 최단경로 거리
bool found[MAX_VTXS]; // 방문한 정점 표시 집합 S -> 집합 포함 시 true
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;
}
return minpos;
}
void printDistance() { //모든 정점들의 dist[] 값 출력
for (int i = 0; i < size; i++) { cout << dist[i] << " "; }
cout << endl;
}
void PrintPath(int start, int end) {
cout << "[최단경로: " << getVertex(start) << "<-" << getVertex(end) << "] " << getVertex(end);
while (path[end] != start) {
cout << "-" << getVertex(path[end]);
end = path[end];
}
cout << "-" << getVertex(path[end]) << endl;
}
// Dijkstra의 최단 경로 알고리즘: start 정점에서 시작함.
void ShortestPath(int start) {
for (int i = 0; i < size; i++) { //초기화: dist[], found[]
dist[i] = getEdge(start, i); //인접행렬 값 반환(간선 가중치)
path[i] = start;
found[i] = false; //처음에 S집합은 비어있음.
}
found[start] = true; // S에 포함
dist[start] = 0; // 최초 거리
for (int i = 0; i < size; i++) {
cout << "Step" << i + 1 << ": ";
printDistance(); // 모든 dist[] 배열값 출력
int u = chooseVertex(); // S에 속하지 않은 비용 가장 작은 정점 반환
found[u] = true; // 집합 S에 u를 포함시킴
for (int w = 0; w < size; w++) {
if (found[w] == false)//S에 속하지 않는 노드 w의 dist값 갱신
if (dist[u] + getEdge(u, w) < dist[w]) {
dist[w] = dist[u] + getEdge(u, w);
path[w] = u;
}
} // u를 거쳐가는 것이 최단 거리이면 dist[] 갱신
}
}
};Dijkstra를 모든 정점에 대해 작동하는 Floyd 알고리즘
class WGraphFloyd : public WGraph
{
int A[MAX_VTXS][MAX_VTXS]; // 최단경로 거리를 2차원배열로
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++) { // 정점 k를 거치는 경우
for (int i = 0; i < size; i++) // 모든 (i,j) 경로 수정
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(); // 각 단계에서의 최단경로 거리 출력 : k번
}
}
void printA() {
cout << "====================================" << endl;
for (int i = 0; i < size; i++) { // 모든 (i,j) 경로 거리 출력
for (int j = 0; j < size; j++) {
if (A[i][j] == INF) cout << " INF ";
else cout << A[i][j] << " ";
}
cout << endl;
}
}
};