[자료구조] 그래프와 다익스트라(dijkstra) 알고리즘

본 글은 <C++로 쉽게 풀어쓴 자료구조>및 학교 강의를 참고하여 작성되었다.

 

그래프 표현 방법

그래프는 간단하게 세 종류로 나눌 수 있다. 무방향 그래프, 방향 그래프, 가중치 그래프가 그것이다. 무방향 그래프는 방향이 표시되지 않은 그래프, 즉 양방향으로 갈 수 있는 그래프를 말하고, 방향 그래프는 말그대로 방향이 있는 그래프이다. 마지막으로 가중치 그래프는 두 정점 간의 연결 유무뿐 아니라 연결 강도까지 나타내는 그래프로, 본 글에서 중점적으로 다루게 될 그래프이다. 간단한 예시로 전국 각지의 도시 간 도로를 연결하는 간선을 떠올려볼 수 있다. 이 경우 간선의 가중치는 도로를 이동하는 거리나 비용 등을 나타낼 수 있겠다.

 

그래프를 표현하는 방법은 크게 두 가지로,  인접행렬 또는 인접리스트를 사용할 수 있지만, 간선마다 다른 가중치를 가져야 하는 그래프라면 인접행렬로 나타내는 것이 직관적이고 보기 좋을 것이다.

무방향 그래프의 인접행렬과 인접리스트

가중치가 있는 그래프의 인접행렬. INF는 간선이 존재하지 않음을 의미하는데 보통 매우 큰 숫자를 사용.

 

이 글에서 살펴볼 것은 아래쪽이다.

코드를 중심으로 살펴보자.

#include <iostream>
#include <fstream>
#include <queue>
#include <list> 
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <limits>
using namespace std;

// STL을 사용하지 않을 경우
#define MAX_VTXS 100
#define INF 9999

// 가중치를 고려하지 않는 Graph 클래스이다.
class AdjMatGraph {
protected:
	int    size;	// 정점의 개수, 정점의 이름, 인접행렬(간선)
	char   vertices[MAX_VTXS];
	int    adj[MAX_VTXS][MAX_VTXS];
public:
	AdjMatGraph() { reset(); }
	char getVertex(int i) { return vertices[i]; }
	int  getEdge(int i, int j) { return adj[i][j]; }
	void setEdge(int i, int j, int val) { adj[i][j] = val; }
	bool isEmpty() { return size == 0; }
	bool isFull() { return size >= MAX_VTXS; }

	void reset() { // 그래프를 초기화한다.
		size = 0;
		for (int i = 0; i < MAX_VTXS; ++i)
			for (int j = 0; j < MAX_VTXS; ++j)
				setEdge(i, j, 0);
	}
	void insertVertex(char name) {	// 정점 삽입 함수
		if (!isFull()) vertices[size++] = name;
		else cout << "ERROR : 그래프 정점 개수 초과" << endl;
	}
	void insertEdge(int u, int v) {	// 간선 삽입 함수(가중치를 고려 않으므로 항상 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;
		}
	}
};

// 위의 클래스를 상속받아 가중치를 고려하는 그래프를 만든다.
// 가중치 그래프만 사용한다면 굳이 두 그래프를 쪼갤 필요는 없지만
// 본 교재에서는 각각의 기능을 하는 객체를 따로 구현하였다.
class WGraph : public AdjMatGraph {
public:
	void insertEdge(int u, int v, int weight) {	// 가중치 간선 삽입
		if (weight > INF) weight = INF;
		setEdge(u, v, weight);
	}
	bool hasEdge(int i, int j) { return (getEdge(i, j) < INF); }
	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();
	}
};

 

 

다익스트라 알고리즘

 

class WGraphDijkstra : public WGraph {
	int path[MAX_VTXS];
	int dist[MAX_VTXS];
	bool found[MAX_VTXS];
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() {.
		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;
	}
	void ShortestPath(int s) { 
		for (int i = 0; i < size; i++) {
			dist[i] = getEdge(s, i);
			path[i] = s;			
			found[i] = false;
		}
		found[s] = true;
		dist[s] = 0;
		for (int i = 0; i < size; i++) {
			cout << "Step" << i + 1 << ": ";
			printDistance();
			int u = chooseVertex();
			found[u] = true;
			for (int w = 0; w < size; w++) {
				if (found[w] == false)
					if (dist[u] + getEdge(u, w) < dist[w]) {
						dist[w] = dist[u] + getEdge(u, w);
						path[w] = u;
					}
			}       
		}
	}
	
};

int main() {
	
	WGraphDijkstra g;
	string fn = "graph_sp.txt";
	g.load(fn);
	cout << "Dijkstra의 최단경로 탐색을 위한 그래프 : " << fn << endl << endl;
	g.display();
	g.ShortestPath(0);

	return 0;
}

 

 

이번 숙제는 다음 내용을 포함합니다.

1. 그래프 표현 방법(코드 중심)으로 설명합니다. 

2. 다익스트라 알고리즘을 설명하고, 코드를 구현합니다. 

3. (옵션) 백준 알고리즘 다음 문제를 풀어봅니다.

- 1753 최단경로

- 1238 파티

- 1504 특정 최단 경로

- 1177 최소비용 구하기

4. (옵션) BFS 관련 문제를 풀어 봅니다.