💡그래프 알고리즘이란,
그래프와 같은 복잡하고 연결성이 높은 자료구조에서
순회 (Graph Traversal), 탐색 및 검색 (Graph Search) 등과 같은 목적으로 사용되는 알고리즘이다.
주로 사용되는 그래프 알고리즘은 크게 5 가지로 정리할 수 있다.
(각 알고리즘 별로 자세한 소개는 정리 후 링크를 추가할 예정이다.)
🔘 최단 경로 Shortest Path
🔘 최소 신장 트리 Minimum Spanning Tree
🔘 위상 정렬 Topological Sort
🔘 서로소 집합 Disjoint Set (Union Find)
🔘 네트워크 플로우 Network Flow
최단 경로 Shortest Path
최단 경로란, 말 그대로 출발 지점에서 도착 지점까지 가는 최단 거리가 되는 경로를 말한다.
유사하게 그래프 최단 경로 알고리즘이란 출발 정점에서 도착 정점까지 가는 최단 경로를 찾는 알고리즘이라고 이해하면 된다.
그러나 그래프 알고리즘에서는 최단 거리를 판단하는 기준이 달라지는 것 뿐이다.
각 간선에 가중치가 부여된 가중치 그래프(Weighted Graph)에서 가중치가 그 예이다. 문제의 조건에 따라 가중치를 최대 또는 최소로 하는 경로가 최단 경로가 되는 것이다.
최단 경로 알고리즘에는 3가지 알고리즘이 대표적이다.
🔘 다익스트라 알고리즘 Dijkstra Algorithm
🔘 프로이드-워셜 알고리즘 Floyd-Warshall Algorithm
🔘 벨만-포드 알고리즘 Bellman-Ford Algorithm
최소 신장 트리 Minimum Spanning Tree
신장 트리(Spanning Tree)란 그래프 내의 모든 정점을 포함하는 트리이다.
모든 정점이 연결되어 있지만 간선은 V-1개의 최소로 연결된 부분 그래프로 순환성이 없다.
하나의 그래프에는 여러 개의 신장 트리가 존재하며, 최소 신장 트리 알고리즘은 이 중에서 가중치가 최소인 신장 트리를 찾는 알고리즘 이다.
최소 신장 트리 알고리즘에는 2가지 알고리즘이 대표적이다.
위상 정렬 Topological Sort
위상 정렬은 방향성이 있는 그래프에서 정점의 간선의 방향에 맞게 나열하는 방식의 정렬이다. 예를 들어, 순서에 맞게 작업을 수행해야 할 때 작업을 순서대로 정렬해주는 알고리즘이다.
그래서 방향성이 있지만 순환성은 없는 Directed Acyclic Graph(DAG)에만 적용이 가능하다. 방향성이 없다면 순서를 알 수 없고, 순환성이 있다면 시작 정점을 정할 수 없기 때문이다.
DFS/BFS 탐색 방식에 따라서 정렬 수행 결과가 달라지기 때문에 유일한 답이 없다.
서로소 집합 Disjoint Set
서로소 집합이란 교집합이 없는 두 집합을 이야기 한다. 서로소가 공약수가 1밖에 없는 두 자연수를 의미한다는 개념에서 이해하면 된다.
서로소 집합 알고리즘은 합집합(Union) 연산과 찾기(Find) 연산을 하기 때문에 합집합 찾기(Union Find)라고도 불린다.
합집합(Union)
: 두 개의 원소가 포함된 집합을 하나의 합집합으로 만든다.찾기(Find)
: 특정 원소가 속한 집합을 찾는다.
네트워크 플로우 Network Flow
-- 정리중 --
