그래프 알고리즘 (Graph Algorithms)
그래프 알고리즘(Graph Algorithms)은 노드(Node)와 간선(Edge)으로 이루어진 그래프 구조를 기반으로 한 알고리즘입니다. 그래프는 네트워크와 유사하게 노드들이 연결된 형태를 이루고 있으며, 이를 통해 네트워크 최단 경로, 최소 비용 신장 트리 등을 찾는 것이 주된 목표입니다. 대표적인 그래프 알고리즘으로는 다익스트라 알고리즘(Dijkstra's Algorithm), 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm), 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) 등이 있습니다. 각각의 알고리즘은 문제의 종류와 요구사항에 따라 사용됩니다. 아래에서는 각 알고리즘을 자세히 설명하겠습니다.
1. 다익스트라 알고리즘 (Dijkstra's Algorithm)
다익스트라 알고리즘은 하나의 시작점에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 비음수 가중치를 가진 그래프에서 사용되며, 우선순위 큐를 이용해 각 노드까지의 최단 거리를 반복적으로 갱신합니다.
동작 과정:
- 시작 노드를 설정하고, 그 노드의 거리를 0으로 초기화합니다. 다른 모든 노드의 거리는 무한대로 설정합니다.
- 현재 방문하지 않은 노드 중 가장 작은 거리를 가진 노드를 선택하여 방문합니다.
- 그 노드를 경유하여 인접한 노드들의 거리를 갱신합니다.
- 모든 노드를 방문할 때까지 이 과정을 반복합니다.
시간 복잡도:
다익스트라 알고리즘의 시간 복잡도는 우선순위 큐에 따라 달라지며, 일반적으로 O((V + E) log V)입니다. 여기서 V는 노드의 개수, E는 간선의 개수입니다.
2. 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
플로이드-워셜 알고리즘은 모든 노드 간의 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 음수 가중치를 가진 그래프에서도 동작하며, 그래프의 모든 노드 간의 최단 경로를 찾는 데 사용됩니다.
동작 과정:
- 그래프의 모든 노드 쌍에 대한 초기 거리를 설정합니다. 자신의 노드로 가는 경로는 0, 직접 연결된 노드 간의 거리는 그 간선의 가중치로 설정합니다.
- 다른 모든 노드를 중간 경로로 삼아 각 노드 쌍 사이의 거리를 갱신합니다.
- 이 과정을 모든 노드 쌍에 대해 반복합니다.
시간 복잡도:
플로이드-워셜 알고리즘의 시간 복잡도는 O(V3)입니다. 이는 모든 노드 쌍을 고려하여 세 번 중첩된 반복문을 사용하기 때문입니다.
3. 크루스칼 알고리즘 (Kruskal's Algorithm)
크루스칼 알고리즘은 최소 신장 트리(MST)를 찾기 위한 대표적인 알고리즘 중 하나입니다. 그래프의 모든 간선을 가중치 순으로 정렬한 후, 사이클을 만들지 않도록 간선을 하나씩 선택하여 MST를 구성합니다.
동작 과정:
- 그래프의 모든 간선을 가중치 순으로 정렬합니다.
- 가장 가중치가 작은 간선부터 시작하여, 사이클이 생기지 않으면 해당 간선을 선택합니다.
- 모든 노드를 연결할 때까지 이 과정을 반복합니다.
시간 복잡도:
크루스칼 알고리즘의 시간 복잡도는 O(E log E)이며, 여기서 E는 간선의 개수입니다. 이는 간선들을 정렬하는 데 소요되는 시간에 기반합니다.
4. 프림 알고리즘 (Prim's Algorithm)
프림 알고리즘은 크루스칼 알고리즘과 같이 최소 신장 트리를 찾기 위한 알고리즘이지만, 노드를 중심으로 최소 비용 신장 트리를 확장해 나갑니다. 시작 노드에서 출발하여 연결된 가장 가중치가 작은 간선을 선택하며 트리를 확장합니다.
동작 과정:
- 시작 노드를 선택하고, 트리에 포함되지 않은 노드 중 가장 가까운 노드를 선택하여 트리에 추가합니다.
- 인접한 노드 중 가중치가 가장 작은 간선을 선택하여 트리를 확장합니다.
- 모든 노드가 트리에 포함될 때까지 이 과정을 반복합니다.
시간 복잡도:
프림 알고리즘의 시간 복잡도는 O((V + E) log V)입니다. 여기서 V는 노드의 개수, E는 간선의 개수입니다.