알고리즘 공부[1] 그래프 (C++)

안녕하세요. 오늘은 그래프에 관하여 알아보겠습니다.

그래프는 여러 알고리즘 문제에서 등장하며, 관련된 알고리즘 또한 많기 때문에 잘 알고 있는 것이 중요하다고 생각합니다.

Contents

그래프

그래프의 종류

그래프의 경로

그래프의 표현

그래프

---

그래프는 vertex(정점)들의 집합 V와 edge(간선)들의 집합인 E로 구성된 자료구조입니다.

그렇다면 우리는 그래프를 간략하게

로 표현할 수가 있죠.

이러한 표현에서 눈치를 채신 분들도 있겠지만!

그래프를 정의하는데 있어서 간선의 길이 그리고 정점의 위치는 신경쓰지 않습니다.

정점이 어디에 있든, 간선이 길이와 상관 없이 각 정점과 정점을 이어주는 간선의 유무로만 그래프를 정의합니다.

그래프의 종류

---

그래프의 종류에는 여러가지가 있습니다. 아래 나타난 것 말고도 여러 기준에 따라 그래프는 분류되어집니다.

여기서는 보통 많이 나오는 그래프의 종류만 나열해 보겠습니다.

A. Directed graph

그래프의 간선이 방향성을 가지는 것을 말합니다.

보통 이런 그래프는 정점간의 의존성을 나타내는 데에 많이 쓰입니다.

예를 들어, A시험을 통과해야 B시험을 보고, B시험을 통과해야 C시험을 보는 경우

A->B->C 와 같은 모양의 그래프가 그려지겠죠!

B. Undirected graph

간선의 방향이 없는 그래프를 말합니다.

C. weighted graph

간선에 가중치가 부여된 그래프를 말합니다. 

예를 들어 A마을과 B마을, B마을과 C마을 등 마을간의 길을 간선으로 표현하여 그래프를 만든다고 합시다.

이 때 마을간의 거리 또한 간선에 표시를 하고 싶어질 때가 있을 겁니다.

그런 경우 간선에 가중치를 부여하여 거리를 표시 할 수 있습니다. 이러한 그래프를 weighted graph라고 합니다.

D. DAG(Directed acyclic Graph)

방향성이 있는 directed 그래프 중 싸이클이 없는 그래프를 말합니다.

이런 그래프는 각 요소들의 일정 순서가 있는 경우 각 요소들을 그래프로 만들 때 많이 사용됩니다.

추후 다룰 포스트에서 DAG와 위상 정렬의 개념을 볼 때 다시 보게 될 것입니다.

그래프의 경로

---

경로라는 것은 서로 연결된 간선 혹은 정점을 순서대로 나열 한 것입니다. 

트리를 traverse할 때 방문한 노드를 나열 한 것과 같은 이치죠.

일반적으로 그래프의 경로는 simple path(단순 경로)를 지칭하며 단순경로란 정점을 단 한번만 지나는 경로를 말합니다.

일반적으로 알고리즘 문제를 해결하는데 있어서 문제 상황이 그래프로 인식이 된다면, 해답은 최적인 경로를 찾는 것이 될 것입니다.

그래프의 표현

---

그럼 우리는 그래프라는 자료구조를 어떻게 표현 할 수 있을까요? 언듯 보기에는 트리와 같이 구성하면 될 것 같습니다.

하지만 그래프는 트리와는 다르게 삽입, 삭제가 없죠! 다소 정적인 구조로 표현이 가능합니다.

A. 인접 리스트 표현 방식

그래프의 각 정점마다 정점으로부터 나가는 간선들(혹은 간선이 도달하게 되는 또 다른 정점)을 저장하는 방식입니다.

예를 들어보죠!

아래와 같은 그래프가 있다고 합시다.

위의 그래프는 Directed graph의 한 예입니다. (사실 위 그래프는 DAG또한 됩니다.)

여기서 우리는 a, b, ... , h까지의 알파벳이 달린 정점을 편의상 0번, 1번, ... , 8번 정점이라고 합시다.

인접 리스트라는 것은 한 정점으로 부터 나가는 간선들(혹은 간선이 도달하는 정점)을 저장한다고 했습니다.

0번(a)의 경우 7번(h)을 저장하면 되고,  8번(i)의 경우 1번(b), 3번(d), 5번(f)를 저장하면 되는 것이죠.

C++의 경우는 다음과 같은 자료형을 통해 그래프 표현이 가능하게 됩니다.

vector< list<int> > adjacent_list;

여기서 adjacent_list[i]는 i번 정점에 연결되어 있는 간선(혹은 정점)들이 저장된 list를 말합니다.

ex) adjacent_list[8] = {1, 3, 5};

만약 여러분이 가중치 그래프(weighted graph)를 저 방식을 통해 구현하려면 어떻게 해야 할까요?

간선과 함께 weight를 저장하면 되므로

vector< list< pair<int, int> > > adjacent_list;

와 같이 선언 해 주면 pair를 이용하여 weight를 같이 저장 할 수 있습니다.

 장점 

필요한 만큼 메모리를 할당해서 사용할 수 있습니다.

(인접 행렬 표현 방식의 단점을 보면 이해가 되실 것입니다.)

 단점 

인접리스트 표현 방식의 단점은 두 정점의 연결여부를 바로 확인 할 수 없다는 것입니다.

두 정점간의 연결 여부를 확인하기 위해서는 list를 모두 돌아서 일일이 확인해야 합니다.

B. 인접 행렬 표현 방식

그래프의 각 정점 간의 연결을 행렬을 통해 저장하는 방식입니다. 그래프 G(V, E)에 대하여 행렬의 크기는 |V| x |V|가 됩니다.

위에 예시로 가져온 그래프를 인접 행렬로 표현하려고 해봅시다.

행렬 M에 대하여 M(i, j)를 i번 정점에서 j번 정점으로 가는 간선의 유무라고 정의합시다.

i번에서 j번으로 가는 간선이 있다면 1, 없다면 0을 저장하여 행렬을 나타내 보겠습니다.

이렇게 만든 행렬을 인접 행렬이라고 부릅니다.

C++에서는 다음과 같은 자료형으로 이 인접행렬을 통한 표현이 가능합니다.

vector< vector<bool> > adjacent_matrix;

물론 그냥 2차원 배열로도 당연히 가능합니다.

가중치 그래프(weighted graph)에 대해서 또 한번 생각을 해봅시다. 

인접행렬 표현 방식으로 그래프를 저장 할 경우, weight는 행렬에 직접 저장해 놓으면 됩니다.

앞의 리스트 처럼 pair를 통해 저장 할 필요도 없으며,

vector< vector<int> > adjacent_matrix;

선언을 통해 weight를 간단히 나타낼 수 있습니다.

 장점 

인접리스트 표현 방식의 단점인 두 정점간의 연결여부 확인이 인접행렬에서는 행렬의 원소 확인으로 바로 가능 합니다.

 단점 

인접 표현 방식의 단점은 위와 같이 0이 많은 sparse한 경우에도 불구하고 고정적으로 |V| x |V|만큼의 공간을 써야한다는 점입니다.

정점의 수가 많으면 많을수록 공간 할당은 매우 커지고, sparse한 경우라면 매우 손해를 보게 됩니다.

이번 글에서는 그래프의 개념과 관련된 전반적인 내용을 살펴 보았습니다.

질문이 있으시거나, 잘못된 부분을 발견하셨다면 언제든지 댓글 남겨주시면 응답하겠습니다.

다음 글에서는 그래프와 관련되어 자주 등장하는 주제인 DFS(Depth-First search)에 대해서 알아보겠습니다.

감사합니다.