Kruskal, Prim, Dijkstra 알고리즘 | 자료구조실습 12주차 과제

* 성신여대 22-2학기 자료구조실습 수업시간에 배운 내용을 토대로 요약 정리한 글입니다

 

그래프의 개념과 최소비용 알고리즘 세가지에 대해 알아보자

 

 

1. 그래프 표현 방법

 

그래프의 형태

 

그래프는 방향과 가중치로 구분해볼 수 있다

 

 

그리고 그래프의 연결은 인접 행렬과 인접 리스트를 통해 나타낼 수 있다

 

 

인접 행렬

 

방향 그래프의 경우,

  : 행에 있는 노드(행렬에서 왼쪽 0열에 있는 노드)가 열에 있는 노드를 가리키면 가중치를 표시한다

무방향 그래프의 경우,

  : 서로 연결되면 가중치를 표시한다

 

가중치가 없는 그래프의 경우, 

  : 연결되면 1로 표시하고 연결되지 않으면 0으로 표시한다

가중치가 있는 그래프의 경우, 

  : 연결되면 가중치 값을 표시하고 연결되지 않으면 0으로 표시한다

 

(* 가중치는 0이 아니라고 가정)

 

 

 

인접 리스트

 

방향이 없는 그래프의 경우,

  : 해당 노드와 연결된 정점들을 리스트와 연결한다 (순서는 상관없음, 아래의 그림에서는 오름차순으로 나타냄)

방향이 있는 그래프의 경우,

  : 해당 노드와 연결된 정점을 연결하는데, 방향을 구분해준다. (인덱스노드가 직접 가리키는 정점만 리스트에 연결)

 

(가중치는 아래에서 설명!)

 

 

* 가중치의 경우 따로 pair<int, int>를 설정해주어 값을 표현해준다.

 

 

코드

아래와 같이 구현해보았다.

 

1. 가중치 없는 방향/무방향 그래프 구현 (인접 행렬 이용)

 

#include <iostream>
using namespace std;

#define MAX_INDEX 1000

class Graph {
private:
	int vertices; // 정점 개수
	bool adj[MAX_INDEX][MAX_INDEX] = { 0, }; // 인접 행렬
public:
	Graph(int _vertices) {
		vertices = _vertices;
	}

	void setUndirectEdges(char _a, char _b) { // 무방향 그래프 연결
		_a -= 'a';
		_b -= 'a';
		adj[_a][_b] = 1;
		adj[_b][_a] = 1;
	}

	void setDirectEdges(char _a, char _b) { // 방향 그래프 연결
		_a -= 'a';
		_b -= 'a';
		adj[_a][_b] = 1;
	}

	void printGraph() { // 그래프의 정보(인접 리스트) 출력
		for (int i = 0; i < vertices; i++) {
			cout << static_cast<char>('a' + i) << ' ';
			for (int j = 0; j < vertices; j++) {
				cout << adj[i][j] << ' ';
			}
			cout << '\n';
		}
	}

	int getVertices() {
		return vertices;
	}
};

int main() {
	Graph MyGraph(5);
	MyGraph.setDirectEdges('a', 'c');
	MyGraph.setDirectEdges('a', 'd');
	MyGraph.setDirectEdges('b', 'a');
	MyGraph.setDirectEdges('b', 'd');
	MyGraph.setDirectEdges('b', 'e');
	MyGraph.setDirectEdges('c', 'e');
	MyGraph.setDirectEdges('d', 'a');
	MyGraph.setDirectEdges('d', 'c');
	MyGraph.setDirectEdges('e', 'b');

	cout << MyGraph.getVertices() << '\n';
	MyGraph.printGraph();

	return 0;
}

 

결과

 

 

 

2. 가중치 있는 방향/무방향 그래프 구현 (인접 리스트 이용)

 

#include <iostream>
#include <vector>
using namespace std;

#define MAX_INDEX 1000

class Graph {
private:
	int vertices; // 정점 개수
	vector<pair<int, int>> adj[MAX_INDEX]; // 인접 리스트 (+ 가중치)
public:
	Graph(int _vertices) {
		vertices = _vertices;
	}

	void setUndirectEdges(char _a, char _b, int _weight) { // 무방향 그래프 연결
		_a -= 'a';
		_b -= 'a';
		adj[_a].push_back(make_pair(_b, _weight));
		adj[_b].push_back(make_pair(_a, _weight));
	}

	void setDirectEdges(char _a, char _b, int _weight) { // 방향 그래프 연결
		_a -= 'a';
		_b -= 'a';
		adj[_a].push_back(make_pair(_b, _weight));
	}

	void printGraph() { // 그래프의 정보(인접 리스트) 출력
		for (int i = 0; i < vertices; i++) {
			cout << static_cast<char>('a' + i) << " | ";
			for (int j = 0; j < adj[i].size(); j++) {
				cout << static_cast<char>('a' + adj[i][j].first) << "(" << adj[i][j].second << ") ";
			}
			cout << '\n';
		}
	}

	int getVertices() {
		return vertices;
	}
};

int main() {
	Graph MyGraph(5);
	MyGraph.setUndirectEdges('a', 'b', 5);
	MyGraph.setUndirectEdges('a', 'c', 3);
	MyGraph.setUndirectEdges('a', 'd', 2);
	MyGraph.setUndirectEdges('b', 'd', 4);
	MyGraph.setUndirectEdges('b', 'e', 6);
	MyGraph.setUndirectEdges('c', 'd', 7);
	MyGraph.setUndirectEdges('c', 'e', 2);

	cout << MyGraph.getVertices() << '\n';
	MyGraph.printGraph();

	return 0;
}

 

 

 

** 보통은 인접 리스트가 더 많이 사용된다고 함.

인접 행렬의 단점: 메모리 차지를 많이 하고, 대각선의 값은 무조건 0이 되어 메모리 낭비도 일어난다.

 

 

2. Kruskal 알고리즘

개념

 

1. 모든 그래프의 간선을 가중치에 따라 오름차순으로 정렬한 후

2. 가중치가 가장 작은 간선 e를 뽑는다

3. 사이클이 생기지 않는다면 e를 선택하고 삽입한다

4. 모든 정점이 삽입될 때까지 2~3을 반복한다

 

 

 

 

3. Prim 알고리즘

개념

 

1. 우선 초기 시작 정점 v을 정한다

2. v와 인접한 정점 중에 간선의 가중치가 가장 작은 정점을 v로 재설정하고 삽입한다. 단, 사이클이 생기면 안 된다

3. 모든 정점이 삽입될 때까지 2를 반복한다

 

 

 

 

 

4. Dijkstra 알고리즘

개념

 

* 다익스트라는 최소비용 계산 시 유용하게 사용되는 알고리즘이다

 

거리 정보를 담는 배열과 정점의 방문 여부를 담는 배열을 생각하고 시작하자

 

1. 시작 노드와 인접한 정점들과의 거리를 업데이트 시켜준 후 시작 노드의 방문 여부를 true로 체크한다

2. 방문한 정점과 인접한 정점 중에 비용이 가장 적게 드는 정점을 선택하고 해당 정점의 방문 여부를 true로 체크한다

3. 2번에 의해 갱신될 수 있는 거리들을 업데이트한다

4. 2 ~ 3을 반복한다

 

 

* 만약, 가장 적게 드는 비용이 중복될 경우, 아무거나 선택해도 된다.

 

 

코드

 

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[그리디] 다익스트라 알고리즘

 

코드를 직접 구현하기 어려워서 해당 블로그의 코드를 참고하였다

 

 

#include <iostream>
#include <vector>
#define INF 1e9 // 무한을 의미하는 값으로 10억 설정
using namespace std;

// 노드 개수: n, 간선 개수: m, 시작 노드 번호: start
int n, m, start;

// 노드 개수는 최대 100,000개라고 가정
// pair: 인접 노드 번호, 가중치
vector<pair<int, int>> graph[100001];

bool visited[100001]; // 방문한 적이 있는지 체크
int d[100'001]; // 최단 거리 테이블

// 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드의 번호 리턴
int getSmallestNode() {
	int min = INF;
	int idx = 0;

	for (int i = 0; i <= n; i++) {
		if ((d[i] < min) && !visited[i]) {
			min = d[i];
			idx = i;
		}
	}

	return idx;
}

// 다익스트라 알고리즘
void dijkstra(int start) {
	// 시작 노드에 대한 초기화
	d[start] = 0;
	visited[start] = true;

	// 시작 노드의 인접 노드들은
	// 시작 노드까지의 거리로 테이블 초기화
	for (int j = 0; j < graph[start].size(); j++) {
		d[graph[start][j].first] = graph[start][j].second;
	}

	// 시작 노드를 제외한 전체 n-1 개의 노드에 대해 반복
	for (int i = 0; i < n - 1; i++) {
		// 현재 최단 거리가 가장 짧은 노드를 선택해서 방문 처리
		int now = getSmallestNode();
		visited[now] = true;

		// 현재 노드와 연결된 다른 노드 확인
		for (int j = 0; j < graph[now].size(); j++) {
			int cost = d[now] + graph[now][j].second;

			// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
			if (cost < d[graph[now][j].first]) {
				d[graph[now][j].first] = cost;
			}
		}
	}
}

int main() {
	// 노드 개수, 간선 개수, 시작 노드의 번호 
	cin >> n >> m >> start;

	// 모든 간선 정보 입력 받기
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
		graph[a].push_back({ b, c });
	}

	// 최단 거리 테이블을 모두 무한으로 초기화
	fill_n(d, 100'001, INF);

	// 다익스트라 알고리즘 수행
	dijkstra(start);

	// 시작 노드에서 다른 모든 노드로 가는 최단 거리 출력
	for (int i = 1; i <= n; i++) {
		if (d[i] == INF) // 도달할 수 없는 경우
			cout << "INF" << '\n';
		else // 도달할 수 있는 경우 거리 출력
			cout << d[i] << '\n';
	}

	return 0;
}