카테고리 없음

과제13_가중치 그래프

greentealover1 2023. 5. 29. 00:37

가중치 그래프: 간선에 비용, 가중치가 할당된 그래프를 의미

  • 최소비용 신장트리: 최소한의 비용을 가지는 신장트리(Kruskal 알고리즘, Prim 알고리즘 등을 주로 사용한다.)
더보기
최소비용 신장트리의 생성조건: 반드시 n-1개의 간선을 사용해야한다. 간선의 가중치 합이 최소여야 한다. 사이클이 포함되서는 안된다.

Kruskal의 기본적인 알고리즘:

  1. 그래프 내 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
  2. 가장 가중치가 작은 간선 e를 선택한다.
  3. e를 신장 트리에 삽입한다.이때 사이클이 생길시 삽입하지 않고, 2번으로 돌아간다.사이클이 생기지 않을시, 최소 신장 트리에 삽입한다.
  4. n-1개의 간선이 삽입될 때까지 2~3를 반복한다.
더보기
VertexSets(int n) : nSets(n) {
		for (int i = 0; i < nSets; i++)
			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 감소
}

cf). 위의 멤버메소드들이 kruskal알고리즘 구현에 사용된다

다음은 크루스칼 알고리즘의 구현 예이다. 

이때,minheap을 사용하는 이유는 모든 정점들을 삽입하고 하나씩 꺼내 출력하면 오름차순으로 정렬된 값을 얻을 수 있기 때문

더보기
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;		// 선택된 간선의 수(현재까지 선택된 간선의 수를 0으로 초기화)
		while (edgeAccepted < size - 1) { 	// 4.(n-1)개의 edge가 삽입될때까지
			HeapNode e = heap.remove(); // 2.가장 작은 edge 선택
			//간선e의 양쪽 끝 정점이 속한 정점 집합의 루트를 찾는다.
			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++;//선택된 간선의 수를 증가
			}
		}
	}
};
  • 최단 경로 알고리즘: 두 정점 u, v를 연결하는 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제

일반적으로 최단 경로 알고리즘을 구할 때, dijkstra algorithm 즉 다익스트라 알고리즘이 가장 많이 사용된다.

-다익스트라 알고리즘 정리:

더보기

출발점으로부터 거리가 최소로 알려진 점들의 집합s를 유지함으로써 가장 짧은 거리를 가지는 나머지 점v를 차례로 s에 포함시킨다

즉 시작정점v에서 다른 모든 정점까지 최단 경로를 찾는 알고리즘

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]) {//dist[i]가 최소값보다 작고 아직 방문x이면,
				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++) {//s에 포함되지 않은 모든 정점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[] 갱신
		}
	}
};

이외에도 최단경로를 구하는 알고리즘으로 반복문을 3번 호출해서 사용하는 Floyd 알고리즘도 존재한다.