[C++] 그래프(Graph) 구현

주) 이 포스트는 작성중입니다.

 

C++에서 그래프를 구현하는 방법에는 크게 두가지가 있습니다.

각 방법은 명확한 장단점을 가지고 있으니, 문제를 해결할때 적당한 방식을 선택하여 구현하여야 합니다.

 

첫번째는 행렬을 이용한 구현(인접행렬, Adjacency matrix)이고, 두번째는 리스트(List)를 이용한 구현(인접리스트, Adjacency List)입니다.

 

1. 인접행렬을 사용한 그래프 구현

#include<iostream>
#include<vector>
#define GRAPH_MAX_SIZE 1000 //그래프 최대 사이즈
using namespace std;

int graph[GRAPH_MAX_SIZE][GRAPH_MAX_SIZE]; //그래프 선언
int main()
{
	//다음 예제는 Matrix를 사용하여 그래프를 구현하는 소스임
	int n, m; //n: 정점, m：간선
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			graph[i][j] = -1;
		}
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		//int w;
		cin >> u >> v;
		//cin >> u >> v >> w;
		graph[u][v] = 1; //u -> v 간선 연결
		graph[v][u] = 1; //단방향일 경우 수행하지 않음
		//graph[u][v] = w; //가중치가 있는 경우
	}
	return 0;
}	

2. 인접리스트를 사용한 그래프 구현

#include<iostream>
#include<vector>
#define GRAPH_MAX_SIZE 1000 //그래프 최대 사이즈
using namespace std;

vector<int> graph[GRAPH_MAX_SIZE]; //그래프 선언
//vector<pair<int,int>> graph[n+1]; //가중치가 있을경우
int main()
{
	//다음 예제는 Vector를 Linked List처럼 사용하여 그래프를 구현하는 소스임
	//Vector: 정점, Vector의 element: 연결된 정점
	int n, m; //n: 정점, m：간선
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		//int w; //가중치 변수
		cin >> u >> v;
		//cin>>u>>v>>w;
		graph[u].push_back(v); //u -> v 간선 연결
		graph[v].push_back(u); //단방향일 경우 수행하지 않음
		//graph[u].push_back(v, w); //w의 가중치를 가진 u -> v 간선 연결
	}
    return 0;
}