1. 그래프 기초

그래프란?

• 그래프는 현실 세계의 사물이나 추상적인 개념 간 연결 관계를 표현함
• 정점 : 각각의 데이터를 표현
• 간선 : 정점들을 연결하는 선
• 그래프는 연결 개수에 제한이 없다. (연결리스트의 노드와 비교했을 때)
• 도로, 소셜 네트워크 등 활용 범위가 무궁무진함

 

가중치 그래프란?

• 연결관계 뿐만 아니라 가중치를 주어 이동 간 비용을 표시

 

방향 그래프란?

• 말 그대로 방향이 있는 그래프다.
• 두 사람 사이의 호감도 같은 것

 

 

---

그래프의 구현 방법 1

void CreateGraph_1()
{
	struct Vertex
	{
		vector<Vertex*> edges;
	};

	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]);

	bool connected = false;

	for (Vertex* edge : v[0].edges)
	{
		if (edge == &v[3])
		{
			connected = true;
			break;
		}
	}
}

• Vertex는 멤버로 Vertex 포인터의 배열(edge)을 가지고 있다.
• v는 Vertex의 배열로 v의 인덱스에 접근해서 Vertex의 edge 안에 연결된 정점을 넣는다
• 탐색할 때는 해당 인덱스의 Vertex가 가진 edge안에 찾고자 하는 정점이 있는지 비교한다.

 

 

 

 

 

 

---

그래프 구현 방법 2

void CreateGraph_2()
{
	struct Vertex
	{
	};

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

	vector<vector<int>> adjacent(6);

	adjacent[0] = { 1, 3 };
	adjacent[1] = { 0, 2, 3 };
	adjacent[3] = { 4 };
	adjacent[5] = { 4 };

	bool connected = false;
	for (int vertex : adjacent[0])
	{
		if (vertex == 3)
		{
			connected = true;
			break;
		}
	}
}

• int의 2차원 배열을 통해서 0번째에는 정점을 넣고 그 멤버로 연결된 정점의 목록을 넣는다.
• 검색할 때는 해당 정점의 인덱스를 넣고 for문을 통해 찾을 수 있다.

 

 

 

 

 

 

---

그래프 구현 방법 3

void CreateGraph_3()
{
	struct Vertex
	{
	};

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

	//연결된 목록 관리
	//[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;

	bool connected = false;
	if (adjacent[1][3])
		connected = true;


	vector<vector<int>> adjacent2(6, vector<int>(6, -1));

	adjacent2[0][1] = 15;
	adjacent2[0][3] = 35;
	adjacent2[1][0] = 15;
	adjacent2[1][2] = 5;
	adjacent2[1][3] = 10;
	adjacent2[3][4] = 5;
	adjacent2[5][4] = 5;


}

• 메모리를 포기하고 성능을 선택하는 방법
• 가능한 경우의 수에 대해 모든 메모리를 소비하지만
• 해당 간선과 연결여부를 확인하는데 O(1) 시간이 소요된다.