![[알고리즘] 그래프 이론(Graph Theory) 알고리즘](https://assets.bullet.site/files?id=32d13e36-0d89-80eb-b001-d9a654e148e0&url=attachment:b76adbfc-cd28-461b-a92d-daaf34367de2:image.png)
TABLE OF CONTENTS
그래프 이론 알고리즘이란?
그래프 이론(Graph Theory) 알고리즘
정점(Vertex)과 간선(Edge)으로 이루어진 자료구조인 그래프(Graph) 를 다루는 알고리즘의 집합
ex) SNS 친구 관계, 지도 경로, 전기 회로, 네트워크 통신
그래프 이론 알고리즘 특징
- 다양한 구조 표현: 트리, 네트워크, 관계망 등 복잡한 문제 모델링 가능
- 탐색 + 최적화: 탐색(DFS, BFS)과 최적화(최단 경로, 최소 신장 트리 등) 문제 해결
- 방향성 / 가중치 고려 가능: 방향 그래프, 무방향 그래프, 가중치 그래프 등 다양한 형태
- 활용 범위 넓음: 컴퓨터 네트워크, 데이터 분석, 물류, AI, 게임 등
그래프 이론 알고리즘 실제 적용 사례
- 네트워크 분석: SNS, 인터넷 라우팅
- 지도/길찾기: 최단 경로, 네비게이션
- 물류/교통: 최소 비용, 효율적 경로 탐색
- AI / 게임: 경로 탐색(A*)
- 회로 설계, 조직도, 프로젝트 관리(PERT/CPM)
주요 그래프 이론 알고리즘 종류
알고리즘 | 설명 | 시간 복잡도 | 활용 예시 |
DFS (깊이 우선 탐색) | 한 경로를 끝까지 탐색 후 다른 경로 탐색 | O(V+E) | 경로 찾기, 사이클 탐지 |
BFS (너비 우선 탐색) | 가까운 노드부터 차례로 탐색 | O(V+E) | 최단 경로(가중치 동일 시) |
다익스트라(Dijkstra) | 한 정점에서 다른 정점까지 최단 거리 | O(E log V) | 지도, 네비게이션 |
벨만-포드(Bellman-Ford) | 음수 간선 포함 그래프에서 최단 거리 | O(VE) | 금융/네트워크 비용 분석 |
플로이드-워셜(Floyd-Warshall) | 모든 정점 쌍 최단 거리 | O(V³) | 전체 망 분석 |
크루스칼(Kruskal) | 최소 신장 트리(MST), 간선 기반 | O(E log E) | 네트워크 비용 최소화 |
프림(Prim) | 최소 신장 트리(MST), 정점 기반 | O(E log V) | 전력망, 통신망 설계 |
Made with Bullet