[C++ 자/알 Note] 그래프

그래프의 요소

정점(Vertex): 데이터를 표현하는 개념을 의미한다

간선(Edge): 정점들을 연결하는 데 사용한다

 

그래프의 개념

그래프는

사물이나 추상적인 개념 간의 연결관계를 표현한다

 

그래프의 예시

그래프는 소셜 네트워크 관계도, 지하철 노선 등

매우 많이 사용된다 

 

그래프의 종류

1. 가중치 그래프

정점간의 가중치가 있는 경우 사용되는 그래프이다

ex. 지하철 노선도

 

2. 방향 그래프

간선의 방향이 있는 경우 사용되는 그래프이다

ex. 일반 통행이 포함된 도로망, 두 사람 사이의 호감도

 

그래프의 구현 방법

1. 구조체 vector 방식

wrapping 구조체를 이용한 방법이다

void CreateGraph::CreateGraph_1()
{
	struct Vertex
	{
		vector<Vertex*> edges;
		// int data;
	};

	vector<Vertex> v;
	v.resize(6);

	v[0].edges.push_back(&v[1]);
	v[0].edges.push_back(&v[3]);
	v[1].edges.push_back(&v[0]);
	v[1].edges.push_back(&v[2]);
	v[1].edges.push_back(&v[3]);
	v[3].edges.push_back(&v[4]);
	v[5].edges.push_back(&v[4]);

	// Q) 0번 -> 3번 정점이 연결여부
	bool connected = false;
	for (Vertex* edge : v[0].edges)
	{
		if (edge == &v[3])
		{
			connected = true;
			break;
		}
	}
}

 

2. 인접리스트 (2차 vector 방식)

2차 vector를 사용하는 방식으로

메모리를 아낄 수 있지만 탐색 속도는 O(N)이다

void CreateGraph::CreateGraph_2()
{
	vector<vector<int>> adjacent(6);
	adjacent[0] = { 1, 3 };
	adjacent[1] = { 0, 2, 3 };
	adjacent[3] = { 4 };
	adjacent[5] = { 4 };

	// Q) 0번 -> 3번 정점이 연결여부
	// A1
	bool connected = false;
	for (int vertex : adjacent[0])
	{
		if (vertex == 3)
		{
			connected = true;
			break;
		}
	}

	// A2 - STL
	vector<int>& adj = adjacent[0];
	bool connected2 = (std::find(adj.begin(), adj.end(), 3) != adj.end());
}

 

3. 인접행렬 (2차 array 방식)

2차 array를 사용할 수도 있지만

아래의 코드처럼

2차 vector의 원소개수를 미리 초기화해서

2차 vector를 2차 array처럼 사용할 수도 있다

이러한 2차 array 방식은 메모리가 다소 커지지만 탐색 속도는 O(1)이다

void CreateGraph::CreateGraph_3()
{
	// [X][O][X][O][X][X]
	// [O][X][O][O][X][X]
	// [X][X][X][X][X][X]
	// [X][X][X][X][O][X]
	// [X][X][X][X][X][X]
	// [X][X][X][X][O][X]

	vector<vector<bool>> adjacent(6, vector<bool>(6, false));
	adjacent[0][1] = true;
	adjacent[0][3] = true;
	adjacent[1][0] = true;
	adjacent[1][2] = true;
	adjacent[1][3] = true;
	adjacent[3][4] = true;
	adjacent[5][4] = true;

	// Q) 0번 -> 3번 정점이 연결여부
	bool connected = adjacent[0][3];

	// 가중치 그래프 사용하는 경우
	vector<vector<int>> adjacent2 =
	{
		vector<int> { -1, 15, -1, 35, -1, -1 },
		vector<int> { 15, -1, +5, 10, -1, -1 },
		vector<int> { -1, -1, -1, -1, -1, -1 },
		vector<int> { -1, -1, -1, -1, +5, -1 },
		vector<int> { -1, -1, -1, -1, -1, -1 },
		vector<int> { -1, -1, -1, -1, +5, -1 },
	};
}

 

그래프의 구현 방법 - 결론

인접리스트는 연결여부가 드문 경우에 사용하고

인접행렬은 연결여부가 빽빽한 경우이거나

연결여부 탐색을 빨리 찾아야하는 경우에 사용하면 된다

 

코테에서는 인접리스트로 구현하는 것이 일반적이고

연결여부를 빨리 탐색해야하는 특수한 경우에는

인접행렬로 구현하는 것이 추천된다

 

그런데

게임은 상황에 따라 다르겠지만

유저에게 빠르게 탐색 결과가 도출되어야

유저의 불편함을 줄일 수 있기에

메모리를 포기하더라도 인접행렬로 가는 경우가 추천되는 것 같다