2-1. 그래프 기초

1. 그래프 종류

(1) 가중치 그래프(Weighted Graph)

요소들의 연결 관계 뿐 아니라 어떤 연결적 특징이 있는지 가중치를 이용하여 나타냄.

 

(2) 방향 그래프(Directed Graph)

화살표를 이용하여 연결 관계의 방향성을 나타낼 수 있다.

 

2. 위의 방향-가중치 그래프 표현하기

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

간선내에 포인터 타입으로 정점들이 포함되어 있다.

 

(1) 특정 정점들이 연결되어 있는지 체크하기

	// 0번과 3번 정점이 연결되어 있는지 체크하는 방법
	bool connected = false;
	for (Vertex* edge : v[0].edges)
	{
		if(edge == &v[3])
		{
			connected = true;
			break;
		}
	}

위의 반복문의 문법은 배열 v의 edges의 각 요소들을 Vertex 포인터형인 edge에 대입하여 반복한다는 뜻을 지닌다.

 

 

(2) 그래프 수정

정점을 간선 구조체에서 빼내어서 2차 벡터로 따로 관리한다.

정점의 연결 관계를 직접 표현하는 방법이다.

void CreateGraph_2()
{
	vector<vector<int>> adjacent(6);
	// adjacent[n] ; n번째 정점과 연결된 정점의 목록
	adjacent[0] = { 1, 3 };
	adjacent[1] = { 0, 2, 3 };
	adjacent[3] = { 4 };
	adjacent[5] = { 4 };

 

(2-1) 특정 정점들의 연결 상태 체크

	// 0번과 3번 정점이 연결되어 있는지 체크하는 방법
	bool connected = false;
	for (int vertex : adjacent[0])
	{
		if (vertex == 3)
		{
			connected = true;
			break;
		}
	}
	// STL을 사용하는 방법
	bool connected2 = find(adjacent.begin(), adjacent.end(), 3) != adjacent.end();

위의 형태에서는 각 정점들이 연결된 정점의 수가 많아질 수록 배열이 커지기 때문에 찾기 어려워질 수 있다.

이를 보완하기 위해 아래처럼 좀 더 빠르게 값을 찾는 방법을 사용할 수 있다.

 

(3) 2차원 배열

각 배열의 요소들은 연결 여부(true, false ; 연결 시 true값을 가짐)을 뜻하는 불리언 값을 가진다.

void CreateGraph_3()
{
	vector<vector<bool>> adjacent(6, vector<bool>(6, false));
	// adjacent[n] ; n번째 정점과 연결된 정점의 목록
	// adjacent[a][b] ; a에서 b로 연결되어 있다.
	// 메모리 소모가 심하지만 빠른 접근이 가능함
	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;

 

(3-1) 특정 정점들의 연결 상태 체크

	// 0번과 3번 정점이 연결되어 있는지 체크하는 방법
	bool connected = adjacent[0][3];

 

3. 가중치 그래프 구현하기

	vector<vector<int>> adjacent2 =
	{ // -1 ; 연결되어 있지 않음
		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 },
	};

 

(3-1) 특정 정점들의 연결 상태 체크

	// 0번과 3번 정점이 연결되어 있는지 체크하는 방법
	adjacent2[0][3] != -1;