그래프 이론 알고리즘 유형별 정리

코딩테스트에서 그래프 문제를 자주 만나볼 수 있습니다. 이때 간선간의 비용이 들기도 하고 아니기도 하고(그럴때는 모두 1) 가장 짧은 거리 가장 긴거리 특정한 조건을 만족하는 수(루트에서 리프까지 같을때 합이 얼마 인것의 개수는?) 되게 여러가지 변형 문제가 있습니다.

1. 서로소 집합

서로소 집합은 공통 원소가 없는 두 집합입니다. 집합 간의 관계를 파악하기 위해서 서로소 집합 알고리즘을 사용할 수 있는데 서로소 집합은 공통 노드를 찾는 연산으로 구성되며 모든 노드는 자신이 속한 집합을 찾기 위해서 루트 노드를 재귀적으로 찾습니다.

서로소 집합 알고리즘은 크루스칼 알고리즘에서도 사용하기때문에 중요합니다.

2. 신장 트리

신장 트리는 하나의 그래프가 있을 때 모든 노드를 포함하는 부분 그래프를 의미. 일반적인 그래프에서 신장트리를 추출하기 위해서 사이클이 발생하지 않을때까지 높은 비용의 간선을 제거하는 식으로 나감

3. 크루스칼 알고리즘

크루스칼 알고리즘은 가능한 최소 비용의 신장 트리를 찾아주는 알고리즘 입니다. 시간 복잡도는 O(ElogE)로 간선을 정렬한 뒤에 간선의 비용이 작은 순서대로 차례대로 최소 신장 트리를 만들어가는 그리디 알고리즘의 일종

4. 위상 정렬 알고리즘 (Topology Sort)

위상 정렬 알고리즘은 방향의 그래프의 모든 노드들을 방향성에 거스르지 않도록 순서대로 나열하는 정렬 기법을 의미

선수과목의 학습 순서 문제등에서 사용. 큐 자료구조를 이용한 위상 정렬의 시간 복잡도는 O(V+E)

서로소 집합 알고리즘과 최소 신장트리 알고리즘은 코테에서 종종 출체되는 알고리즘유형이고 위상 정렬 알고리즘은 난이도가 높은 후반부에서 가끔 출체되는 것이 특징