현실 세계에서 모든 사물은 다른 사물과 연관성을 갖습니다. 사람과 사람 사이도 그렇고, 도시와 도시 사이도 그렇습니다. 이런 객체와 그 연관성에 대한 모델링을 그래프(Graph)라고 합니다. 그래프는 객체의 위치는 따지지 않고 오직 연결 관계 즉 위상(Topology)만 따지는 위상수학의 범주에 속합니다.
그래프는 오직 하나의 부모만을 가질 수 있는 트리의 제한에서 벗어나 일반화된 모형입니다. 트리처럼 뿌리나 단말노드같은 특별한 방향성은 없습니다.
그래프는 현실의 복잡한 객체간의 관계를 컴퓨터로 모델링하여 여러가지 문제를 해결할 수 있는 도구를 제공합니다. 가장 대표적인 응용이 바로 네비게이션에서 빠른 길을 찾는 알고리즘입니다. 지도상의 모든 길은 간선(Edge)로 모델링되며, 길의 교차점은 정점(Vertex)으로 모델링될 수 있습니다.
이렇게 지도상의 모든 길이 그래프로 표현되면 컴퓨터의 빠른 연산 능력과 효율적인 알고리즘을 통해서 아무리 먼 곳이라도 빠른 길을 몇초 안에 찾아낼 수 있습니다.
이런 현실적인 문제를 해결할 수 있는 도구로서 그래프는 매우 중요하며, 반드시 이해하고 넘어가야 합니다.
강의 자료
강의 동영상
20.0 그래프 기본 - 시작 : 그래프는 객체와 그 연관성을 모델링하는 방법으로 현실의 많은 문제를 해결하는 알고리즘의 주요 자료구조입니다. 이 장에서는 그래프의 정의와 용어, 구현 방법, 탐색법 등에 대해 알아 봅니다.
20.1 그래프의 정의 : 그래프는 정점(Vertex)과 간선(Edge)의 집합으로 정의됩니다. 오로지 정점 간의 연결 상태만 따지기 때문에 다양한 형태의 동일한 그래프가 존재할 수 있습니다. 트리와는 달리 두 정점간의 연결 경로가 여러개 존재할 수 있다는 특징도 있습니다.
20.2 그래프의 구현 - 인접 행렬 : 그래프를 구현하는 방법 중 하나인 인접 행렬(Adjacency Matrix)에 대해 알아봅니다. 정점을 X축과 Y축으로 놓고 그 연결 상태를 각 셀에 표현하는 방법입니다.
20.3 그래프의 구현 - 인접 리스트 : 듬성듬성한 그래프를 효율적으로 구현하기 위해서는 간선 자체를 링크로 표현하는 인접 리스트(Adjancency List)로 표현하는 것이 효율적입니다. 인접 리스트의 자료구조와 기본 동작을 구현해 봅니다.
20.4 깊이 우선 탐색 : 탐색은 그래프의 모든 정점을 방문하는 방법을 의미합니다. 그래프는 비선형구조여서 직관으로 탐색 문제를 해결하기는 힘듭니다. 그래프의 모든 정점을 전수 방문하는 방법 중 하나인 깊이 우선 탐색(Depth First Search)에 대해 먼저 알아봅니다.
20.5 너비 우선 탐색 : 너비 우선 탐색(Breadth First Search)은 깊이 우선 탐색과는 대조적으로 깊이 들어가기 전에 자신의 인접 정점을 먼저 방문하는 전략입니다. 스택 대신 큐(Queue)를 쓰는 것만으로 간단하게 구현이 가능합니다.
20.6 이중 연결 : 이중 연결 (Biconnectivity)은 두 정점간의 경로가 두개 이상인 것을 의미합니다. 네트웍이라고 생각하면 한 경로에 장애 발생시 우회로를 이용할 수 있는 안전한 상태와 같습니다. 대조적으로 어떤 정점을 제거할 때 그래프가 둘 이상으로 나뉘는 정점을 단절점(Articulation Point)이라고 합니다. 이 단절점은 네트웍에서 위험 지점을 의미합니다. 단절점을 찾아내는 건 현실에서 매우 중요한 문제로서 앞서 배운 깊이 우선 탐색을 이용하면 쉽게 찾아낼 수 있습니다.
20.9 그래프 기본 - 결론 : 그래프의 기본적인 정의와 용어, 구현 방법, 탐색법 등에 대해 알아 보았습니다. 이후 강좌를 통해 더 현실적인 알고리즘에 대해 접해볼 겁니다.
관련글 |
- C++로 배우는 알고리즘
- 19장 : 레드-블릭 트리 (Red-Black Tree)
- 21장 : 가중 그래프 (Weighted Graph)
댓글 없음:
댓글 쓰기