Algorithm
그래프 이론과 알고리즘: DFS, BFS, MST, 위상 정렬 등 주요 개념 총정리
n_0_jun
2025. 1. 9. 14:00
반응형
1. 그래프의 표현 방식
1.1 인접 행렬 (Adjacency Matrix)
- 구성 방법: n×n 크기의 2차원 배열로, 노드 간 연결 관계를 저장합니다.
- 예시: 두 노드 A와 B가 연결되어 있으면, A[i][j] = 1로 표시됩니다.
- 장점: 두 노드가 연결되어 있는지 O(1) 시간에 확인 가능합니다.
- 단점: 메모리 낭비가 크며, 희소 그래프에서 비효율적입니다.
- 적용 예시: 밀집된 그래프에서 효율적.
1.2 인접 리스트 (Adjacency List)
- 구성 방법: 각 노드마다 연결된 노드들을 리스트로 저장합니다.
- 장점: 메모리 효율적, 희소 그래프에서 적합.
- 단점: 간선 정보 접근은 O(V + E) 시간이 걸립니다.
- 적용 예시: 소셜 네트워크나 웹 그래프처럼 노드 간 연결이 제한적인 경우.
1.3 인접 배열 (Adjacency Array)
- 구성 방법: 인접 리스트와 유사하지만 배열로 관리하여 더 빠르게 간선 정보를 접근할 수 있습니다.
- 적용 예시: 빠른 간선 정보 접근이 필요할 때.
2. 깊이 우선 탐색 (DFS)와 너비 우선 탐색 (BFS)
2.1 깊이 우선 탐색 (DFS)
- 동작 원리: 한 노드에서 시작하여 연결된 노드를 깊게 탐색하며, 모든 경로를 완전히 방문 후 이전 노드로 돌아갑니다.
- 시간 복잡도: O(V + E)
- 용도: 사이클 탐지, 강한 연결 요소(SCC) 탐색, 위상 정렬 등에 사용.
- 적용 예시: 미로 찾기나 퍼즐 문제에서 유용.
2.2 너비 우선 탐색 (BFS)
- 동작 원리: 시작 노드에서 인접한 모든 노드를 먼저 탐색한 후, 각 노드에서 다시 인접한 노드를 탐색합니다.
- 시간 복잡도: O(V + E)
- 용도: 무가중치 그래프에서 최단 경로 탐색, 연결 요소 탐색 등에 사용.
- 적용 예시: 사회 관계망 분석에서 최단 경로를 찾을 때 유용.
3. 최소 신장 트리 (MST)
3.1 최소 신장 트리의 개념
- 정의: 모든 노드를 연결하는 간선 중에서 가중치의 합이 최소인 트리.
- 성질: 사이클이 없으며, 모든 신장 트리 중에서 간선의 가중치 합이 최소입니다.
3.2 프림 알고리즘 (Prim's Algorithm)
- 동작 원리: 시작 노드에서 출발하여 연결된 간선 중 최소 가중치 간선을 선택해 트리를 확장합니다.
- 복잡도: O(E log V) (힙 사용 시)
- 적용 예시: 전력망 설계 등.
3.3 크루스칼 알고리즘 (Kruskal's Algorithm)
- 동작 원리: 간선을 오름차순으로 정렬하고 사이클이 생기지 않도록 간선을 선택합니다.
- 복잡도: O(E log E)
- 적용 예시: 고속도로 연결 시 최소 비용을 찾는 데 유용.
4. 위상 정렬 (Topological Sort)
- 정의: 방향성 비순환 그래프(DAG)에서 노드의 선행 관계를 지키며 순서를 정하는 알고리즘.
- 알고리즘:
- Kahn’s Algorithm: 진입 차수가 0인 노드를 제거하며 위상 정렬을 수행.
- DFS 기반: DFS를 통해 후위 순서를 기록하고 이를 바탕으로 정렬.
- 적용 예시: 프로젝트 관리에서 작업 순서를 효율적으로 결정하는 데 사용.
5. 최단 경로 알고리즘
5.1 다익스트라 알고리즘 (Dijkstra’s Algorithm)
- 동작 원리: 시작 노드에서 출발해 최소 비용으로 방문할 수 있는 노드를 선택하여 최단 경로를 계산합니다.
- 복잡도: O(E log V)
- 적용 예시: 지도에서 목적지까지의 최단 경로를 찾는 데 사용.
5.2 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
- 동작 원리: 모든 간선을 반복적으로 검사하여 최단 경로를 찾습니다.
- 특징: 음수 가중치 그래프에서도 작동합니다.
- 복잡도: O(V × E)
- 적용 예시: 음수 가중치가 있는 경제 관련 그래프 분석 시 유용.
6. 플로이드-워샬 알고리즘
6.1 기본 개념
- 목표: 모든 정점 쌍 간의 최단 경로를 계산.
- 알고리즘: 경유 정점을 점진적으로 추가하며 각 정점 쌍 간 최단 경로를 업데이트.
6.2 알고리즘 단계
- 초기화: D[i][j] = W[i][j]로 초기화.
- 동적 계획법: D(k)[i][j] = min(D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])
- 시간 복잡도: O(V^3), 공간 복잡도: O(V^2)
6.3 특징
- 음수 가중치 허용.
- 음수 사이클 감지: D[i][i] < 0인 경우 음수 사이클 존재.
반응형