그래프 구현

첫 번째 일반 그래프 구현

정점의 구조체에 간선이 같이 들어있는 구조이다.

정점과 간선을 따로 구분 하는 것이 관리하기 좋아 정점과 간선을 분리하는 그래프를 만들어 보자.

 

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

void CreateGraph_1()
{
	struct Vertex
	{
		// 간선 (연결된 정점들의 주소로 표현하였음.)
		vector<Vertex*> edges;
		// int data;
	};

	// 그래프 v를 선언하고 정점 6개를 만든다.
	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]);

	// 질문) 0번 -> 3번 정점이 연결되어 있는가?
	bool connected = false;
	for (Vertex* edge : v[0].edges)
	{
		if (edge == &v[3])
		{
			connected = true;
			break;
		}
	}
}


int main(void)
{
	CreateGraph_1();
	CreateGraph_2();
	CreateGraph_3();
	CreateGraph_4();




	return 0;
}

 

두 번째 간선과 정점을 분리한 그래프 구현

간선을 따로 분리하여 관리하는 그래프. 해당 그래프는 간선이 많아지면 연결을 여부를 찾을 시 간선이 n개면 최대 n번 순차탐색하는 단점이 있다.

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



void CreateGraph_2()
{
	struct Vertex
	{	
		// int data;
	};

	// 그래프 v를 선언하고 정점 6개를 만든다.
	vector<Vertex> v;
	v.resize(6);

	// 연결된 목록을 따로 관리해보자.
	vector<vector<int>> adjacent(6);

	// 각 정점들의 간선을 배열의 요소로 표현
	// adjacent[n] -> n번째 정점과 연결된 정점 목록
	adjacent[0] = { 1, 3};
	adjacent[1] = {0,2,3};
	adjacent[3] = {4};
	adjacent[5] = {4};

	// 간선이 적으면 괜찮다. 많으면 너무 하드 코딩이라 어렵다.
	// 또한, 연결을 찾을 때 한 정점에 간선이 n개면 최대 n번 탐색한다는 단점

	// 질문) 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());

}



int main(void)
{
	CreateGraph_1();
	CreateGraph_2();
	CreateGraph_3();
	CreateGraph_4();




	return 0;
}

 

세 번째 간선과 정점을 분리하고 메모리를 더 사용하여 탐색 속도를 올린 그래프 구현

간선 표현을 위한 2차원 배열을 size를 정해서 전부 true, false 를 정하여 할당한다. 메모리를 더 사용하는 단점이 있지만 배열의 [from][to] 임의 접근 방식을 사용하여 1번에 탐색 가능하다는 장점이 있다.

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



void CreateGraph_3()
{
	struct Vertex
	{
		// int data;
	};

	// 그래프 v를 선언하고 정점 6개를 만든다.
	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]
	// 2차원 행렬로 간선 표현

	// 읽는 방법 : 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;
	

	// 간선이 적으면 괜찮다. 많으면 너무 하드 코딩이라 어렵다.
	// 또한, 연결을 찾을 때 한 정점에 간선이 n개면 최대 n번 탐색한다는 단점

	// 질문) 0번 -> 3번 정점이 연결되어 있는가?
	bool connected = adjacent[0][3];
	// true 면 바로 끝....
	
}


int main(void)
{
	CreateGraph_1();
	CreateGraph_2();
	CreateGraph_3();
	CreateGraph_4();

	return 0;
}
```

 

네 번째 간선과 정점을 분리하고 메모리를 더 사용하여 탐색 속도를 올린 후 가중치를 넣는 그래프 구현

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



void CreateGraph_4()
{
	struct Vertex
	{
		// int data;
	};

	// 그래프 v를 선언하고 정점 6개를 만든다.
	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]
	// 2차원 행렬로 간선 표현

	// 읽는 방법 : adjacent[from][to]
	// 행렬을 이용한 그래프 2차원 배열
	// 메모리 소모 심함. 빠른 접근 가능
	// (간선이 많이 필요할 알고리즘에 이점이 있다.)
	vector<vector<int>> adjacent =
	{
		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,+5,-1,-1},
		vector<int> {-1, -1, -1,-1,-1,-1},
		vector<int> {-1, -1, -1,+5,-1,-1},
	};


	// 간선이 적으면 괜찮다. 많으면 너무 하드 코딩이라 어렵다.
	// 또한, 연결을 찾을 때 한 정점에 간선이 n개면 최대 n번 탐색한다는 단점

	// 질문) 0번 -> 3번 정점이 연결되어 있는가?
	if (adjacent[0][3] != -1)
	{
		// 간선이 있으므로 해당 간선의 가중치를 넘겨준다.
		int value = adjacent[0][3];
	}

}

int main(void)
{
	CreateGraph_1();
	CreateGraph_2();
	CreateGraph_3();
	CreateGraph_4();




	return 0;
}