이전 포스팅인 DFS/BFS와 최단 경로에서 다룬 내용도 그래프 알고리즘의 한 유형이다. 문제를 접했을 때 서로 다른 개체가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다.
그래프 알고리즘에 앞서 트리 자료구조에 대해 간략히 짚고 넘어가겠다. 트리는 그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조이다.
| 그래프 | 트리 | |
|---|---|---|
| 방향성 | 방향 그래프 혹은 무방향 그래프 | 방향 그래프 |
| 순환성 | 순환 및 비순환 | 비순환 |
| 루트 노드 | 존재하지 않음 | 존재함 |
| 노드간 관계성 | 부모와 자식 관계 없음 | 부모와 자식 관게 |
| 모델 종류 | 네트워크 모델 | 계층 모델 |
Graph Algorithm
그래프는 주로 두 가지 방식으로 구현한다.
- 인접 행렬 (Adjacency Matrix) : 2차원 배열 사용
- 메모리 공간이 많이 필요하지만 특정 노드 간 간선의 비용을 O(1) 시간으로 즉시 알 수 있음
- 인접 리스트 (Adjacency List) : 리스트 사용
- 간선의 개수인 O(E) 만큼만 메모리 공간이 필요하지만 O(V) 시간 소요
이전 포스팅에서 다익스트라 알고리즘은 인접 리스트를, 플로이드-워셜 알고리즘은 인접 행렬을 이용하여 구현해봤다.
알고리즘 문제를 풀 때에는 메모리와 시간을 항상 염두해두고 풀어야 한다. 최단 경로를 찾아야 하는 문제에서 노드의 개수가 적은 경우에는 플로이드-워셜을, 노드와 간선의 개수가 모두 많은 경우에는 우선순위 큐를 이용하는 다익스트라 알고리즘을 이용하면 유리하다.
Disjoint Set
크루스칼 및 위상 정렬 알고리즘을 공부하기 전에 그래프 알고리즘에서 중요하게 사용되는 disjoint-set에 대해 살펴보자. 수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.
서로소 집합 자료구조는 union과 find 연산으로 조작할 수 있어 union-find 자료구조 라고도 불린다.
- union : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
- find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
트리를 이용해 서로소 집합을 계산하는 알고리즘은 다음과 같은 방식으로 동작한다.
- union 연산을 확인하여 서로 연결된 두 노드 A와 B 확인한다.
1-1. A와 B의 루트 노드 A’와 B’를 찾는다.
1-2. A’를 B’의 부모 노드로 설정한다. (B' → A') - 모든 union 연산을 처리할 때까지 1번 과정을 반복한다.
서로소 집합은 무방향 그래프에서 사이클을 판변할 때 사용할 수 있다. 부모 테이블에는 루트 노드 값이 들어가기 때문에 두 노드씩 비교하면서 루트 노드가 같다면 사이클이 발생한 것으로 간주한다.
Spanning Tree
신장 트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 사실 모든 노드가 서로 연결되어 있고, 사이클을 이루지 않는다는 것이 트리의 성립 조건이기도 하다. 신장 그래프라고 부르지 않고 신장 트리라고 부르는 이유이다.
아래 그래프에서 주황색으로 연결된 부분을 신장 트리라고 부르며, 하나의 그래프에서 이와 같이 여러 개의 신장 트리가 나올 수 있다.
Kruskal Algorithm
이러한 신장 트리 중 최소 비용으로 만들 수 있는 신장 트리를 찾는 것을 최소 비용 신장 트리 알고리즘 이라고 하며 크루스칼 알고리즘이 대표적이다.
- 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
- 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인한다.
2-1. 사이클 발생 X → 최소 신장 트리에 포함 2-2. 사이클 발생 O → 최소 신장 트리에 포함하지 않음 - 모든 간선에 대하여 2번의 과정을 반복한다.
모든 간선에 대해 정렬한 뒤 거리가 짧은 간선부터 집합에 포함시키기 때문에 그리디 알고리즘으로 분류된다. 사이클 발생 여부는 위에서 언급했듯이 find_parent 함수를 이용하면 된다.
Topology Sort
위상 정렬은 정렬 알고리즘의 일종으로 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용할 수 있다. 책에 나온 문장을 그대로 인용하자면 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이라고 한다.
객체 지향 프로그래밍 → 자료구조 → 알고리즘 순서와 같이 교과목 선후수 체계를 떠올리면 이해하기 쉬운데, 위상 정렬 알고리즘은 진입차수를 기준으로 동작한다. 진입차수는 특정 노드로 들어오는 간선의 개수를 뜻한다.
- 진입차수가 0인 노드를 큐에 넣는다.
- 큐가 빌 때까지 아래의 과정을 반복한다.
2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
위상 정렬은 차례대로 모든 노드를 확인하면서 해당 노드에서 출발하는 간선을 제거하기 때문에 O(V + E) 만큼의 시간이 소요된다.
참고
- 이것이 취업을 위한 코딩 테스트다