그래프는 실생활에서 인터넷, 금융, 도로, 신경망, 소셜 네트워크 분석 등 광범위한 분야에서 활용되는 자료구조다. 그래프 이론을 통해서 우리가 알아야할 알고리즘은, 그래프의 기본 연산이라 할 수있는 깊이 우선 탐색(DFS, Depth-First-Search)와 너비 우선 탐색(BFS, Breadth-Fisrt-Search)부터 연결성분, 위상정렬, 최소신장트리(MST, Minimum Spanning Tree), 여러 가중치 그래프 등이 있다.
그래프 용어
그래프를 응용하여 해결하는 알고리즘에 있어서 중요한것은 용어와 그래프의 특징이다. 그 중에 먼저 용어를 알아보자.
정점(Vertex)과 간선(Edge)
그래프는 정점(Vertex)과 간선(Edge)의 집합으로 하나의 간선은 두 개의 정점을 연결한다. 즉 정점은 하나의 노드(node)라고 표현하고, 두개의 노드들을 잇는 선을 간선이라고 일컷는다.
방향 그래프 vs 무방향 그래프
간선에 방향이 있는 그래프를 방향 그래프(Directed Graph)라 하고, 간선에 방향이 없는 그래프를 무방향 그래프(Undiredcted Graph)라고 한다.
그래프 간선 개수
- 간선 최소 개수 :
- 방향 그래프의 완전 그래프 간선 개수
- 무방향 그래프의 완전 그래프 간선 개수
차수 (Degree)
위 그림에서 각 정점은 차수(Degree)를 가지고 있다. 차수는 해당 정점과 인접한 정점의 개수를 뜻한다. 단, 방향 그래프에서는 차수를 진입차수(In-degree)와 진출차수(Out-degree)로 구분된다. 즉 방향 그래프에서 정점 A는 진입 차수 1이고 진출차수는 2다. 반면 무방향 그래프에서 정점 A의 차수는 2다.
싸이클 (Cycle)
싸이클은 말 그대로 순환되는 경로를 말한다. 이 때, 경로란 출발점 u부터 v까지 가는 경로를 일컷는다. 위에서 보여준 예시는 모두 순환되는 그래프의 예이다. 즉, 시작 정점에서 다른 정점으로 이동했을때 결국 시작 정점으로 돌아오는 그래프다. 반면에 싸이클이 없는 그래프는 트리(Tree)라고 한다.
연결성분 (Connected Component)
줄여서 컴포넌트라고 부르곤한다. 컴포넌트는 그래프안의 모든 정점들이 이동가능한 상태를 말한다. 아래 그림에서는 [D][A,C,B]로 두 개의 컴포넌트를 가지고있다.
가중치 (Weighted)
가중치(Weighted) 그래프는 간선에 가중치가 부여된 그래프다. 가중치는 실제 두 정점의 거리가 될 수도있고, 두 정점을 지나는 시간이 될수도 있다. 때로는 음의 가중치도 존재하며 이러한 것들을 다루는 그리디 알고리즘과 DP가 존재한다. (다익스트라, 밸만포드, 플로이드)
부분그래프(Subgraph)
부분그래프(Subgraph)는 주어진 그래프의 정점과 간선의 집합으로 이루어진 그래프다. 위에서 언급한 트리(Tree)와 모든 정점들을 싸이클 없이 연결하는 그래프를 신장 트리 (Spanning Tree)라고 한다. 이는 최소 신장 트리 (MST, Minimum Spanning Tree)로 응용이 되는데, 간단히 싸이클 없이 연결하는 간선 중 가중치를 가장 적게 가지는 그래프를 말한다.
- 모든 정점들을 연결할때의 간선의수(최소 간선 개수)는 V-1개다.
완전그래프 (Complete Graph)
그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프다. 무방향 완전 그래프일경우, 정점의 수가 n일때 간선의 수는 n * (n-1) / 2 다.
희소 그래프와 밀집 그래프 (Sparse Graph & Dense Graph)
밀집 그래프(dense graph)는 간선의 수가 최대 간선의 수에 가까운 그래프이다. 그와 반대로, 간선이 얼마 없는 그래프는 희소 그래프(sparse graph)라고 한다. 밀집과 희소 간의 구별은 다소 모호하므로 문맥에 따라 달라질 수 있다.
- 아래 그래프 구현 방법에서 인접행렬과 인접리스트간 선택 요소가 된다.
그래프 구현
그래프를 구현하는데 있어서 중요한 점은 '정점과 간선 처리를 어떻게 해줄 것인가'이다. 그래프를 구현하는 방법은 세가지가 있다. 그 중 인접 행렬, 인접 리스트 이렇게 두가지가 자주 사용되어진다.
- 인접 행렬(Adjacency Matrix)
- 인접 리스트(Adjacency List)
- 간선 리스트(Edge List)
인접 행렬
인접 행렬은 N개의 정점은 가진 그래프가 각각의 간선이 어디있는지 행렬로 표현하는 방법이다. 보통 정점이 1차원이면 2차원 행렬로 각 정점마다의 간선 정보를 표현할 수 있다. 가령 adj[i][j] 는 i에서 j로 가는 간선 정보를 알려준다.
- 두 노드간의 간선을 직접 조회 할 수 있다.
- 모든 노드간의 연결정보를 표현하기때문에, 공간복잡도 O(V^2)가 소요된다.
따라서 원하는 노드간의 연결정보를 확인하는데 시간이 빠른 반면에 정점이 많고 간선 정보가 적은 그래프에서는 효율성이 떨어진다.
인접 리스트
인접 리스트는 N개의 정점에 대해서 각각 하나의 연결리스트에 연결정보를 담아서 구현하는 방법이다. 이는 인접 행렬에서와 달리 불필요한 정보를 제거하고 실제 존재하는 그래프만을 표현하기위한 방법이다.
- 두 노드간의 간선을 직접 조회할 수 없고 순차 탐색을 해야한다. O(V)의 시간복잡도가 소요된다.
- 인접 행렬과 달리 실제 존재하는 간선 정보만 표현하기때문에 공간복잡도 O(E)가 소요된다.
따라서 모든 간선정보를 탐색하거나 정점이 많고 적은 간선정보에 대해서는 높은 효율을 보이지만, 밀집 그래프같은 경우 효율성이 떨어진다.
간선 리스트
간선 리스트는 위 두가지 방법과 달리 간선을 중심으로 표현하는 방법이다. 직관적으로 간선 정보를 볼 수 있지만 자주 사용되지 않는다.
- 하나의 구조체에 (시작 노드, 도착 노드, 가중치)의 정보를 담아서 저장하는 특징이 있다.
