그래프 기초

흔히 쓰이는 그래프 모습이다.

데이터(사물, 개념 등) : 정점

정점을 이어주는 선 : 간선

 

으로 이루어져 있다. 지금 보는 그래프는 방향이 없는 양방향성 그래프이지만,

방향이 있는 그래프는 방향성, 가중치가 부여된 그래프는 가중치 그래프라고 이야기한다. 맞나? 가물가물한데... 

 

• 방향 그래프 : 간선에 방향이 있는 그래프(간선에 화살표가 있으면 방향그래프)
• 무방향 그래프 : 간선에 방향이 없는 그래프
• 연결 그래프 : 두 정점 사이에 경로가 존재하는 그래프
• 완전 그래프 : 한 정점에서 모든 다른 정점과 연결되어 최대의 간선수를 가지는 그래프

 인터넷에 검색해봤다. 역시 프로그래머는 구글링이지!

 

강의에서는 다양한 방법으로 노드 기초 작업을 구현해놓았다.

 

1. 

void CreateGraph_1()
{
	struct Vertex
	{
		vector<Vertex*> edges;
		// 정점을 연결해주는 선.
	};

	vector<Vertex> v;
	v.resize(6); // 정점의 갯수는 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)
	{
		cout << edge << endl;
		if (edge == &v[3])
		{
			connected = true;
			break;
		}
	}

}

내가 알고 있던 기본적인 구조이다.

 

2.

 

void CreateGraph_2()
{

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

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

좀 더 보기 편한 구조인 듯 하다. 

저기 for 문을 보면 처음보는 구조라서 처음엔 의아해 했는데, int vertex에 adjacent[0] 메모리에 있는 값을 하나씩 추출하여 돌아가는 구조이다. 배열을 출력할때, 저런 방법이 있는지 처음 알았는데 참고해야겠다.

 

3. 

 

void CreateGraph_3()
{
	//읽는 방법 : 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;
	
	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},
	};

}

이건 bool값을 이용한 건데 개인적으로 내 취향인 코드이다. 하지만 그래프에 값을 등록하는게 너무 지저분해 보인다는 단점이 있는 거 같다.