[C++/이론] 그래프 개론

개요

그래프(Graph)는 '정점(vertex, node)'과 '간선(edge, adjacent, link)'의 집합으로 이루어진 자료구조입니다.

어떻게 보면, 하나의 노드를 가리키는 '연결리스트' 다수의 노드를 한 방향으로 가리키는 '트리'의 확장된 버전으로

이해할 수 있습니다.

 

(문서를 찾다보면 정점 = Node = Vertex 등 용어가 혼용되고, 간선 = edge = adjacent = link 용어가 혼용됩니다. 다 알아두시길 바랍니다.)

이런 식으로 노드와 노드는 간선으로 연결됩니다.

트리, 연결리스트에 비해 현실 상황을 잘 재현하는 자료구조라고 여겨집니다.

 

 

어떻게 보면 지하철 노선도와 같은 형태를 띠고 있으며

이렇게 정보를 가지고 있는 '노드'를 간선으로 직관적으로 연결하고 '복잡한 관계'에 대해서 나타낼 수 있습니다.

 

그래프는 수학자 오일러가 'Konigsberg의 다리' 문제를 해결하기 위해 처음 사용하였으며, 궁금하시면 한 번 찾아보시길 바랍니다.

 

정의

그래프는 수학적으로

G = (V, E) 로 정의됩니다.

V는 정점(Vertex)의 집합

E는 간선(Edge)의 집합입니다.

 

위 그림을 수학적으로 나타내면 다음과 같이 나타낼 수 있습니다.

 

G = (V, E)

V = {0 ,1 ,2 , 3, 4}

E = {(0,1), (0, 4), (1, 2), (1,3), (1,4), (2,3), (3, 4)}

 

무방향 그래프와 방향 그래프

간선에는 '방향성'이 존재하는 그래프가 있고 아닌 그래프도 있습니다.

'방향성'이 존재하면 간선이 가리키는 노드로만 이동할 수 있습니다.

방향 그래프

 

 

'방향성'이 존재하지 않는 경우 향상 간선이 양 쪽 노드를 가리킨다고 간주합니다.

그러므로 간선만 연결되어 있다면 연결된 노드를 자유롭게 이동할 수 있습니다.

무방향 그래프

그래프의 구현 (C++)

그래프를 구현하는 방법에는 '인접 행렬'과 '인접 리스트' 기법이 있으며,

어떤 그래프를 사용하냐에 따라 처리 시간이 달라지므로 둘 다 익히고

적재적소에 사용할 수 있어야 합니다.

 

1. 인접 행렬 (adjacency matrix)

행렬을 통해서 연결을 나타내는 방법입니다.

행렬의 가로, 세로는 각각 해당 노드를 뜻하며

(x, y) 의 값이 1이면 간선이 연결됨을

(x, y) 의 값이 0이면 간선이 연결되지 않음을 뜻합니다.

 

무방향 그래프의 경우 행렬이 항상 '대칭 행렬'의 모습을 보입니다.

//정점이 5개인 인접행렬
int vertex = 5;

int adjacent[5][5] =
{
	0,1,1,0,0,
	0,0,1,0,1,
	0,0,0,1,0,
	0,0,0,0,1,
	0,0,0,0,0
};

위 그림의 행렬을 간단하게 표현한 것 입니다.

adjacent는 int가 아닌 간단하게 bool 자료형을 써도 좋습니다.

 

class Graph
{
public:
	Graph(int v)
		: _vertex(v)
	{
		_adjacent = vector<vector<bool>>(_vertex, vector<bool>(_vertex, false));
	}

	void CreateEdge(int from, int to)
	{
		//무방향 그래프임을 가정
		_adjacent[from][to] = true;
		_adjacent[to][from] = true;
	}

private:
	int _vertex;
	vector<vector<bool>> _adjacent;
};

클래스로 만들면 위와같이 만들 수 있습니다.

 

2. 인접 리스트 (adjacency list)

연결 리스트를 통해 나타낸 것 입니다.

이런 식으로 각각의 정점을 연결리스트의 'head'로 두고

연결관계를 연결리스트 기법으로 추가하는 것입니다.

 

그러나 연결리스트 자체 오버헤드가 있는 편이기에

보통 인접 리스트의 경우에도 '동적 배열'이나 'vector 자료구조'로 구현하

vector 자료구조를 사용해서 구현하는 것을 선호합니다.

 

vector<bool> vertex[5];

int main()
{
	vertex[1].push_back(2);
	vertex[1].push_back(3);

	vertex[2].push_back(1);
	vertex[2].push_back(3);

	vertex[3].push_back(1);
	vertex[3].push_back(2);
	vertex[3].push_back(4);
	
	vertex[4].push_back(3);
}

이런 식으로 vector를 이용하면 간단하게 push_back을 사용하여 '인접 리스트'를 구현할 수 있습니다.

'인접 행렬'과 같이 class로 구현하는 것은 직접 해보시길 바랍니다.

 

마치며

그래프의 경우 현실세계의 복잡한 데이터를 우수하게 재현할 수 있어서, 필수적으로 알아야하는 구조입니다.

그런데, 그래프의 경우 구조가 복잡하여 탐색하는 것 조차 어렵습니다.

 

연결 리스트의 경우 단방향으로 가기만하면 되고

트리 구조만 하더라도 전체를 탐색하려면 전위 순회, 중위 순회, 후위 순회 등.. 비교적 복잡한 방식을 사용해야 합니다.

그러면 그래프의 탐색과 순회는 어떻게 할 수 있을까요?

다음 포스팅에 다뤄보겠습니다.