[Algorithm] 그래프

그래프

그래프는 트리보다도 훨씬 더 일반적이고 강력한 자료구조로, 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현하기 위해 사용된다. 사람들 간의 관계, 도로와 도시들 사이의 관계, 네트워크로 연결된 컴퓨터들의 관계와 같은 것들을 연결 구조의 예로 들 수 있을 것이다. 그래프는 이러한 다양한 관계에 대해 표현할 수 있고, 현실세계의 문제를 그래프로 매핑시킨 후에는 여러 그래프 알고리즘들을 이용하여 그 문제들을 해결할 수 있다.

 

그래프는 객체들을 대응시키기 위한 개념인 정점(Vertex) 집합과, 관계들을 대응시키기 위한 개념인 간선(Edge) 집합 G(V, E)의 형태로 정의한다.

일반적으로 정점 집합은 각 정점에 대응되는 번호로 나타내고, 간선 집합은 정점번호 쌍의 집합으로 나타낸다.

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

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

(간선의 경우, 방향성 유무에 따라 (u, v)와 (v, u)를 구분해야할 수도 있다.)

(단지 간선집합과 정접집합으로 표현되기 때문에 같은 그래프여도 여러가 형태로 그려질 수 있다.)

 

그래프 종류

그래프는 표현하고자 하는 대상에 따라 여러 가지 종류로 나뉠 수 있다.

정점이나 간선에 추가적인 속성을 부여할 수도 있고, 제약을 둘 수도 있다.

 

방향 그래프 vs 무향 그래프

무향 그래프(Undirected Graph) or 양방향 그래프는 두 정점 u, v에 대해 u에서 v로의 간선이 있으면 v에서 u로의 간선도 있는 그래프를 의미한다. 페이스북 친구추가와 같이 한쪽에서 다른쪽으로 친구이면 다른쪽에서도 이쪽으로 친구이기 때문에 이는 무향그래프의 예로 들 수 있을 것이다.

 

유향 그래프(Directed Graph) or 방향 그래프는 두 정점 u, v에 대해 u에서 v로의 간선이 방향정보를 갖고있는 그래프를 의미한다. 즉 u->v 가 가능하다고 반드시 v->u가 가능하지는 않은 그래프를 의미한다.

사람과 사람 사이의 호감관계를 그래프로 나타낸다면, 한쪽에서 다른쪽으로는 호감이 있더라도, 다른쪽에서는 그렇지 않을 수 있기 때문에 이 관계를 표현하기 위해 방향그래프를 이용하면 적절할 것이다.

 

가중치 그래프

가중치 그래프(Weighted Graph)는 그래프의 간선에 가중치라는 정보가 추가된 형태의 관계를 나타내는 그래프이다.

보통 이 가중치라는 속성은 두 도시 사이의 거리, 두 사람 사이의 호감도 등 관계와 관련한 정보를 표현하는데 이용된다.

 

 

다중 그래프

다중 그래프(Multigraph)는 두 정점 사이의 두 개 이상의 간선이 있을 수 있는 그래프를 의미한다. 도로망의 경우 같은 두 지점을 잇는 두 개 이상의 도로가 있을 수 있기 때문에 다중 그래프로 표현될 수 있을 것이다.

반대로 두 정점 사이에 최대 한 개의 간선만 있는 그래프는 단순 그래프(Simple Graph)라고 부른다.

 

 

루트 없는 트리

루트 없는 트리(Unrooted Tree)는 연결 관계만 놓고 봤을 때 트리와 같은 무향 그래프를 의미한다.

부모자식 관계는 따로 없지만, 두 정점 사이의 경로가 하나뿐인 그래프를 의미한다.

 

이분 그래프

이분 그래프(Bipartite Graph)는 그래프의 정점들을 두 개의 그룹으로 나누고,

모든 간선들이 서로 다른 두 그룹의 정점들을 연결하는 형태로 표현되는 그래프를 의미한다.

대표적인 예로 미팅을 하는 남녀들이 있을 때, 서로가 호감을 갖는지에 대한 관계를 표현한다면,

이분 그래프로 표현할 수 있을 것이다. 

 

DAG

DAG(Directed Acyclic Graph)는 방향 그래프의 한 종류로,

어느 한 점에서 출발하여 자기 자신으로 돌아오는 경로(사이클)이 없는 그래프를 의미한다.

DAG는 보통 여러 작업들 간의 상호 의존관계를 그래프로 표현할 때 많이 이용된다.

 

 

 

그래프 표현 방법

대응

그래프를 표현하기 위해서 사용되는 자료구조는 어떤 형태일까?

페이스북 친구관계도를 그래프로 표현한다고 생각해보자.

계정 집합 : { Bob, Sally, Brenda, Bill, Becky, Ted }
친구 관계 집합 : 
{ 
	{Bob, Sally}, 
	{Bob, Brenda}, 
	{Bob, Bill}, 
	{Sally, Brenda},
	{Brenda, Becky}, 
	{Bill, Brenda}, 
	{Bill, Becky}, 
	{Becky, Ted} 
}

다음과 같은 페이스북 관계 데이터를 그래프로 나타내려면 어떻게 해야할까?

그래프에 정접집합에는 일반적으로 객체가 대응되므로, 계정들을 정점집합에 대응시킬 수 있을 것이다.

그러므로 모든 계정에 고유식별번호를 부여하여 정점들을 표현한다. 간선집합에는 관계가 대응되므로, 친구관계를 간선집합에 대응시킬 수 있다. 부여된 고유식별번호의 쌍으로 간선들을 표현한다.

또한 친구관계는 양방향이기 때문에, 무향그래프로 표현할 수 있을 것이다.

 

0 : Bob
1 : Sally
2 : Brenda
3 : Bill
4 : Becky
5 : Ted

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

E = { {0, 1}, {0, 2}, {0, 3}, {1, 2}, {2, 3}, {2, 4}, {3, 4}, {4, 5} }

 

고유번호를 부여하는 과정이 필요한 이유는 무엇일까??

그래프를 활용하는 여러 알고리즘들은, 많은 정점들과 간선들을 비교해가며 동작하는데, 만약 정점들이 문자열로 표현되어있다면, 그래프 알고리즘의 시간복잡도 또한 문자열의 길이에 비례해서 늘어나게 될 것이다. 그러므로 데이터의 크기가 알고리즘에 영향을 주지 않도록 하기 위해, 고유번호를 통해 먼저 데이터와 정점집합을 한번 분리하여 설계하는 것이 여러모로 효율적이다.

 

그래프 표현방법

 

인접 리스트

인접 리스트(Adjacency List) 표현은 그래프의 각 정점마다, 해당 점점으로부터 이동할 수 있는 다른 정점들의 리스트를 저장하여 그래프를 표현하는 방법이다. 그래프는 각 정점마다 하나의 리스트를 갖는 방식으로 구현한다.

// 정점마다 다른 정점 리스트를 갖는 형태
vector<list<int>> adjlist;

// 동적배열을 리스트로 활용할 수도 있다.
vector<vector<int>> adjlist;

친구관계도를 인접리스트로 표현하면 다음과 같이 저장될 것이다.

// 무향그래프이기 때문에, (u, v)의 간선이 있다면 (v, u)의 간선도 추가해주어야 한다.
vector<vector<int>> adjlist = 
{ 
	{1, 2, 3},	// 0 
	{0, 2}, 	// 1
	{0, 1, 3, 4}, 	// 2
	{0, 2, 4}, 	// 3
	{2, 3, 5} 	// 4
	{4}		// 5
};

만약 친구관계도에 친구들 사이의 친밀도와 같은 가중치가 추가된다면 어떻게 해야할까?

다음과 같이 간선 구조체를 만들어서 저장하면 된다.

struct Edge
{
	int vertex;
	int weight;
};

// weight은 모두 0
vector<vector<Edge>> adjlist = 
{
	{{1, 0}, {2, 0}, {3, 0}},		// 0 
	{{0, 0}, {2, 0}}, 			// 1
	{{0, 0}, {1, 0}, {3, 0}, {4, 0}}, 	// 2
	{{0, 0}, {2, 0}, {4, 0}}, 		// 3
	{{2, 0}, {3, 0}, {5, 0}} 		// 4
	{{4, 0}}				// 5
};

 

인접행렬

인접리스트 표현의 큰 단점은 두 정점이 주어질 때, 이 정점이 연결되어있는지 알기 위해 연결 리스트를 순회하며 검색해야한다는 점이다. 이와 같은 연산의 속도를 높이기 위해 고안된 표현방식이 인접행렬(Adjacency) 표현방식이다.

인접행렬 표현은 정점 개수를 N 이라고 하였을 때 N x N 크기의 행렬을 생성하여 모든 정점쌍에 대한 2차원 행렬을 생성하고, 한 정점에서 다른 정점으로의 간선 유무를 저장한다.

단순히 간선의 유무만 저장한다면 다음과 같이 표현될 수 있을 것이다.

vector<vector<bool>> adjmatrix = 
{
	0, 1, 1, 1, 0, 0,
	1, 0, 1, 0, 0, 0,
	1, 1, 0, 1, 1, 0,
	1, 0, 1, 0, 1, 0,
	0, 0, 1, 1, 0, 1,
	0, 0, 0, 0, 1, 0
};

만약 가중치 정보가 추가적으로 필요하다면, bool 값 대신 int를 이용하여 (u, v)로의 가중치를 저장할 수 있다.

vector<vector<int>> adjmatrix;

가중치 외에도 추가적인 정보가 필요하다면, 관계와 관련한 구조체를 생성하여 저장하면 될 것이다.

struct Relation
{
	int weight;
	int data;
};
vector<vector<Relation>> adjmatrix;

 

인접행렬 vs 인접리스트

 

인접행렬과 인접리스트는 완전히 정반대의 특성을 가져서, 한 방식의 단점이 바로 다른 방식의 장점이기 때문에, 구현하려는 알고리즘의 종류와, 표현하려는 그래프의 속성에 따라 적절하게 선택하여 사용해야 한다.

인접행렬의 가장 큰 장점은 정점 u, v가 주어졌을 때, 두 정점을 잇는 간선이 있는지를 단 한번의 배열 접근으로 확인할 수 있다는 점이다. 리스트의 경우는 일일이 순회하며 찾아야 한다.

반면 인접행렬 표현은 정점 개수 N에 대해 N x N 크기의 2차원 배열을 사용하기 때문에, 실제 간선의 개수와 상관없이 항상 O(N^2) 크기의 메모리를 차지하게 된다는 문제가 있다. 인접리스트 표현은 V개의 연결 리스트에 실제 간선 수,

E 만큼의 원소가 있으므로, O(N + E)의 공간만을 사용한다.

간선의 개수 E가 V^2과 비슷할 때, 이 그래프를 밀집 그래프(Dense Graph)라고 부르는데, 이 경우 두 표현방식의 메모리 차이는 거의 없을 것이다. 간선 수가 희소한 그래프는 희소 그래프(Sparse Graph)라고 부르고, 이 경우는 메모리 차이는 심할 것이다. 그러므로 그래프의 종류나, 알고리즘의 형태에 따라 적절한 표현방식을 선택해야 할 것이다.

 

암시적 그래프

그래프를 이용한 문제라도 반드시 정적인 그래프를 생성하고 문제를 해결해야만 하는것은 아니다.

입력이 직접적으로 그래프의 형태를 나타내지 않는 경우 그래프의 구조를 쓰지 않고도 문제를 해결할 수 있다.

대표적인 예로 미로찾기가 있다.

물론 미로찾기의 경우에도 각 위치들을 정점으로, 각 위치에 대한 상하좌우로의 관계를 간선으로 대응시킨다면 일반적으로 사용되는 그래프를 생성할 수 있을 것이다. 하지만, 그렇게 하지 않더라도 2차원 배열 형태로 주어진 미로 데이터는 각 위치 (x, y)로부터의 상하좌우 (x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1) 위치를 언제든지 참조할 수 있기 때문에, 굳이 그래프를 이용하지 않아도 그래프처럼 사용할 수 있다. 이런 형태를 암시적 그래프라 부른다.

그래프의 차수

그래프의 차수(Degree)란 어느 한 정점과 연결된 간선의 개수를 의미한다.

그래프의 차수는 입력 차수(Indegree)와 출력 차수(Outdgree)로 나뉘는데 무향그래프에서는 이 둘이 항상 같기 때문에 보통 일반 차수(Degree)로 표현한다. 반면 유향그래프에서는 입력 차수와 출력 차수가 간선의 방향에 따라 달라지기 때문에, 두 차수를 구분하여 표현한다.

 

 

그래프 이론에서 중요한 사실은 그래프의 차수의 총합은 항상 총 간선의 수 * 2 라는 것이다.

이는 어찌보면 당연한 사실인데 두 정점을 잇는 어느 한 간선이 있다면,

무향 그래프에서는 양쪽 정점에 차수가 각각 1로 차수의 총합이 2가 될 것이고,

유향 그래프에서는 한쪽 정점의 입력차수가 1 반대쪽 정점의 출력차수가 1로 차수의 총합이 2가 되기 때문이다.

 

그래프의 차수를 이용한 문제

한 방에 27명의 사람이 있을 때, 모든 사람이 9명의 다른 사람과 악수를 할 수 있는가?

이 문제는 그래프의 차수를 활용하면 쉽게 해결할 수 있다.

사람을 정점에 대응시키고 악수를 간선에 대응시키면 이 문제를 양방향 그래프의 형태로 표현할 수 있다.

한 사람이 9명의 다른 사람들과 악수를 하는 것은 정점으로부터의 차수가 9인 상황과 같다.

모든 사람들이 9명의 다른 사람들과 악수를 한다는 것은 모든 정점의 차수가 9인 상황과 같은데,

이 때 그래프 차수의 총합은 27 * 9= 243이다. 하지만 위에서 언급했던 것처럼, 그래프 차수의 총합은 항상 모든 간선의 수 * 2로 짝수일 수 밖에 없다. 그러므로 27명의 모든 사람들이 다른 9명의 사람들과 악수를 하는 상황은 생길 수 없다.

 

소스코드

그래프의 차수를 세는 알고리즘을 작성해보자.

이는 각 정점에 연결된 간선들을 모두 순회하는 형태로 구현할 수 있다.

다음은 인접행렬로 표현된 무향그래프에서 그래프의 차수를 세는 코드이다.

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Graph/7-Undirected-Graph-Degree.cpp

insooneelife/AlgorithmTutorial

 

 

다음은 인접행렬로 표현된 유향그래프에서 그래프의 차수를 세는 코드이다.

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Graph/8-Directed-Graph-Degree.cpp

insooneelife/AlgorithmTutorial

 

 

그래프 깊이우선탐색

깊이우선탐색은 가장 기본적인 탐색 알고리즘으로 그래프의 정점과 간선을 방문하는데 활용된다.

그래프를 어떻게 표현했느냐에 따라 시간복잡도가 다르게 나타나는데,

정점의 개수를 V, 간선의 개수를 E 라고 했을 때,

인접행렬 그래프의 경우 O(V ^ 2)이고 인접리스트 그래프의 경우 O(V + E) 시간에 동작한다.

그래프에서 깊이우선탐색은 연결 요소 찾기, 연결여부 찾기, 위상정렬, 오일러 경로 찾기, 그래프 구조 분석, 강결합요소 찾기 등 굉장히 다양하게 활용된다.

이름에서 유추할 수 있듯이 깊이우선탐색은 어느 정점에 관계없이 더 이상 탐색할 수 엎을 때까지 깊게 탐색해나가고, 막히는 지점부터 퇴각하다가 탐색이 가능한 정점이 있다면 다시 끝까지 탐색해나가는 형태로 동작한다.

다음과 같은 그래프에서 0번 노드를 시작으로 깊이우선 탐색을 수행한다고 해보자.

 

0번 정점 시작으로 탐색이 가능한 동안 계속 간선을 거쳐가다가 11번 정점에 도달했을 때,

이미 탐색했던 정점인 7번 정점을 방문하면 그때부터 퇴각을 하기 시작한다.

퇴각을 하다가 아직 방문할 수 있는 정점이 남아있는 7번 정점에 도달했을 때부터 다시 탐색을 시작한다.

그리고 2번 정점까지 탐색 후 다시 퇴각을 진행하게 될 것이다.

 

2번 정점과 4번 정점을 각각 방문 후 퇴각하였다면, 3번 정점에서는 이제 5번 정점으로 이동하게 될 것이다.

그리고 7번 정점을 만난 후부터 다시 퇴각한다.

 

퇴각을 반복하다가 8번 정점을 방문했을 때, 아직 방문하지 않은 1번 정점을 다시 방문한다.

 

최종적으로는 다음과 같이 모든 정점을 방문하게 된다.

연결 간선이 없는 12번 정점은 마지막까지 방문되지 않았음을 확인할 수 있다.

 

인접행렬 깊이우선탐색

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Graph/1-DFS-adjmatrix.cpp

insooneelife/AlgorithmTutorial

 

인접리스트 깊이우선탐색

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Graph/2-DFS-adjlist.cpp

insooneelife/AlgorithmTutorial

 

연결된 노드 개수 세기

깊이우선탐색을 활용한 또 예제로 어떤 특정 정점으로부터 연결된 노드들의 개수를 세는 알고리즘이 있다.

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Graph/3-DFS-count.cpp

insooneelife/AlgorithmTutorial

 

연결 요소 찾기

깊이우선탐색을 활용하면 그래프가 몇 개의 연결 요소로 구성되어 있는지 구분할 수 있다.

다음 그래프는 총 5개의 연결요소로 구분되어 있다.

이 그래프에서 각 연결요소들에 고유 인덱스를 부여하고, 모든 정점들에 대해 어떤 연결요소에 속해있는지를 알아내려면 어떻게 해야할까? 깊이우선탐색을 활용한다면 쉽게 이 문제를 해결할 수 있다. 방문 배열을 공유하도록 하면서 모든 정점에 대해 깊이우선탐색을 수행한다면 이미 탐색된 연결요소의 경우 방문배열에 기록되어 있을 것이기 때문에 자연스럽게 구분이 가능하다.

예를 들어 0번 노드에서 DFS를 수행하고 난 후에는 0번으로부터 연결된 모든 정점들은 방문 기록이 된 상태일 것이다. 여기에서 4번 정점을 시작 정점으로 다시 DFS 탐색을 시작시킬 때, 이미 방문 기록이 된 상태이기 때문에 바로 빠져나오게 될 것이다. 이처럼 바로 빠져나온 경우는 연결요소로 포함시키지 않는 것이다.

 

그러므로 모든 정점에 대해 DFS를 수행하되, 바로 빠져나오지 않은 경우들만 인덱싱한다면 최종적으로 다음과 같은 결과가 나올것이다.

 

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Graph/4-DFS-connected-components.cpp

insooneelife/AlgorithmTutorial

 

 

그래프 너비우선탐색

너비우선탐색은 정점과 간선들을 방문하는 또 다른 기본 그래프 탐색 알고리즘이다.

깊이우선탐색과 마찬가지로 그래프를 어떻게 표현했느냐에 따라 시간복잡도가 달라진다.

인접행렬 그래프 O(V ^ 2)

인접리스트 그래프 O(V + E)

너비우선탐색은 이름에서 유추할 수 있듯이 모든 정점들로부터 인접하고, 아직 방문되지 않은 정점들을 방문하는 탐색방법이다. 그 과정이 넓게 퍼지는 형태이기 때문에 너비우선탐색으로 불린다.

너비우선탐색은 보통 최단경로를 찾는 문제로 자주 활용된다. 물론 여기서 얘기하는 최단경로란 가중치가 없는 그래프에서의 최단경로를 의미하고 경로의 길이는 간선의 개수를 나타낸다.

 

다음과 같은 그래프에서 0번 정점을 시작점으로 너비우선탐색을 수행해보자.

 

먼저 가장 인접한 정점인 7, 9, 11을 방문한다.

 

 

그 후 다음으로 인접한 정점들인 3, 6, 8, 10을 방문한다.

 

 

마지막으로 인접한 정점들을 방문한다.

 

 

인접행렬 너비우선탐색

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Graph/5-BFS-adjmatrix.cpp

insooneelife/AlgorithmTutorial

 

인접리스트 너비우선탐색

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Graph/6-BFS-adjlist.cpp

insooneelife/AlgorithmTutorial

 

너비우선탐색의 최단거리

그래프의 구조와 관련된 문제를 해결하기 위해 DFS를 사용하는 것과 달리, BFS는 대게 하나의 용도로 사용된다. 바로 그래프에서의 최단 경로 문제를 푸는 것이다. 두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾는 문제로, 그래프 이론의 가장 고전적인 문제이다. 이는 가중치가 없는 그래프에서의 최단 경로 문제로 이 때의 경로의 길이는 경로에 포함된 간선의 개수로 정의된다. (단, 가중치가 있는 그래프의 경우 BFS를 이용하여 최단거리를 구할 수 없다.)

 

너비우선탐색에서 최초로 탐색하는 정점까지의 경로가 어떻게 최단경로가 되는 것일까?

이는 귀류법을 이용하여 증명할 수 있다.

먼저 너비우선탐색을 통해 여태까지 탐색한 정점(BFS 스패닝 트리)들과 아직 탐색되지 않은 정점들로 그래프를 구분한다. 회색 정점들은 BFS를 통해 이미 방문한 정점들이고, 밝은 색 정점들은 아직 방문하지 않은 정점들이다.

여기에서 u를 도착점으로 하는 최단경로가 BFS를 통해 방문한 정점으로부터 방문되는 것이 아니라,

아직 탐색되지 않은 정점으로부터 방문된다고 가정하고, 그 때 최단경로가 만들어짐을 보이면 BFS를 통해 처음 방문한 정점이 항상 최단경로라는 만들어진다는 사실을 부정할 수 있다. 그림에서 파란색 간선은 BFS 스패닝 트리로부터의 간선이고, 빨간색 간선은 방문되지 않은 정점들로부터의 간선을 의미한다. 

하지만, 빨간색 간선의 가장 시작 정점인 Q는 결국 스패닝 트리 내부의 정점 P로부터 방문된 정점인데, Q 정점이 큐에 추가될 때 이미 파란색 간선을 통해 U 정점도 큐에 추가되게 된다. 그러므로 아직 방문되지 않은 정점으로부터의 어떤 경로가 U로 도착하는 상황은 발생할 수 없다.

 

 

 

암시적 그래프의 상태공간탐색

https://algorfati.tistory.com/132

상태 공간 탐색

 

명시적 그래프의 상태공간탐색

그래프 모델링

 

 

이미지 출처 (https://github.com/williamfiset/Algorithms)