[개념] 그래프 이론 알고리즘

그래프를 활용하여 풀 수 있는 알고리즘 유형에 대해서 정리한 포스팅이다.

그래프 이론 쉽지 않겠는걸?

📌서로소 집합

공통 원소가 없는 두집합

이때 집합 간의 관계를 파악하기 위해 서로소 집합 알고리즘을 사용할 수 있는데 ,

서로소 집합 알고리즘은 union-find연산으로 구성되며,

모든 노드는 자신이 속한 집합을 찾을 때 루트 노드를 재귀적으로 찾는다

---

📌신장 트리

하나의 그래프가 있을 때 모든 노드를 포함하는 부분 그래프를 의미한다.

일반적인 그래프에서 신장 트리를 추출하는 예시는 다음 그림과 같다.

주로 현실세계에서 '모든 섬을 도로를 이용해 연결하는 문제'등에서 사용된다.

---

📌크루스 칼 알고리즘

가능한 최소 비용의 신장 트리를 찾아주는 알고리즘이다.

시간 복잡도는 O(ElogE)

간선을 정렬한 뒤에 간선의 비용이 작은 순서대로 차례대로 최소 신장 트리를 만들어가는 그리디 알고리즘의 일종이다.

---

📌위상 정렬 알고리즘

방향 그래프의 모든 노드들을 방향성에 거스르지 않도록 순서대로 나열하는 정렬 기법을 의미한다.

ex 선수과목을 고려한 학습 순서 설정 문제!!!!!!!!!!

*큐 자료구조를 이용한 위상 정렬의 시간 복잡도는 O(V+E)이다.

---

오케이! 어려운 유형이다 잘 연습해서 숙지하도록 하자!