[Graph] Chapter 01. 그래프

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/a371f42dd4ae7aea9e445bcca06d4ebff3d9e1de

그래프 구현 · developeSHG/Data_Structure-Algorithm@a371f42

 

 

---

 

 

그래프의 개념

[현실 세계의 사물이나 추상적인 개념 간]의 [연결 관계]를 표현

정점(Vertex) : 데이터로르 표현 (사물, 개념 등)

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

 

 

위 사진의 그래프를 3가지 방법으로 만들어보자.

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;

void 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;
		}
	}
}

// 1번은 단점이 정점에서 포인터로 관리를 하는 점과
// 실제 데이터와 연결 여부 즉 간선의 여부를 분리해서 관리하는게 유용한데
// 1번은 정점 자체에 간선에 대한 정보가 포함되어있어서 띠로 관리하도록 수정해보자.
void CreateGraph_2()
{
	struct Vertex
	{
		// int data;
	};

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

	// 연결된 목록을 따로 관리
	// adjacent[n] -> n번째 정점과 연결된 정점 목록
	vector<vector<int>> adjacent(6);
	adjacent[0] = { 1, 3 };
	adjacent[1] = { 0, 2, 3 };
	adjacent[3] = { 4 };
	adjacent[5] = { 4 };

	// Q) 0번 -> 3번 정점이 연결되어 있나요?
	bool connected = false;
	for (int vertex : adjacent[0])
	{
		if (vertex == 3)
		{
			connected = true;
			break;
		}
	}

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

// 위 2번 방법이 최선일지 생각해보자.
// - 지하철 노선도 -> 서로 드문 드문 연결 (양옆, 환승역이라면 조금 더 ++)
// - 페이스북 친구 -> 서로 빽빽하게 연결
// 만약 정점이 100개인 상태로, 0번이 1~99번과 연결되어 있다할 때,
// 0번이랑 99번 정점이 연결되어 있는지 체크한다면
// 순차적으로 순회해서 99번의 비교를 통해 찾을 수 밖에 없다는 조건이 생겨서 아쉽다.
// 그래서 드문드문 지하철 노선도처럼 연결되어 있다고 가정하면 필요한 애들만 쓰는 2번 방법이 괜찮지만,
// 서로 빽뺵하게 연결된 페이스북 친구 관계에서는 행렬같은 형식으로 2차 배열을 이용하는 게 낫다.
// 메로리를 소비해서 성능 향상을 얻는 것.
void CreateGraph_3()
{
	struct Vertex
	{
		// int data;
	};

	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]

	// 읽는 방법 : adjacent[from][to]
	// 행렬을 이용한 그래프 표현 (2차원 배열)
	// 메모리 소모가 심하지만, 빠른 접근이 가능하다
	// (간선이 많은 경우 이점이 있다)
	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];
	
	// 가중치에 대해 표현 (연결되어 있지 않은 경우 -1)
	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 },
	};
}

int main()
{
	CreateGraph_1();
	CreateGraph_2();
	CreateGraph_3();
}