그래프 알고리즘
그래프 알고리즘은 정점과 간선의 연결 관계로 표현된 문제를 탐색·최적화하는 알고리즘 계열 그래프 알고리즘의 그래프 문제 전반 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는 정점·...
| 분류 | 알고리즘 · 그래프 알고리즘 · 그래프 문제 전반 |
|---|---|
| 문제 | 정점과 간선의 연결 관계로 표현된 문제를 탐색·최적화하는 알고리즘 계열 |
| 입력 | 정점·간선·방향성·가중치 모델을 먼저 명시한다 |
| 핵심 단계 | 인접 리스트나 행렬로 그래프를 표현한 뒤 정점 방문, 최단 경로, 연결 요소, 신장 트리, 흐름 또는 매칭을 계산한다 |
| 시간 복잡도 | 방법에 따라 다름 |
| 공간·구현 | 시간은 보통 정점 수 V·간선 수 E로 표현하며 알고리즘마다 상이 |
| 관련 분야 | 그래프, 자료구조 |
| 참고 문헌 | MIT Algorithms |
그래프 알고리즘은 정점과 간선의 연결 관계로 표현된 문제를 탐색·최적화하는 알고리즘 계열 그래프 알고리즘의 그래프 문제 전반 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는 정점·간선·방향성·가중치 모델을 먼저 명시한다.[1]
핵심 절차는 인접 리스트나 행렬로 그래프를 표현한 뒤 정점 방문, 최단 경로, 연결 요소, 신장 트리, 흐름 또는 매칭을 계산한다. 간선 가중치와 방향성에 따라 적절한 절차가 달라진다. 구현에서는 각 정점 또는 간선에 기록된 상태가 어떤 의미를 갖는지 불변식을 정의하고, 탐색·갱신 과정에서 해당 상태를 일관되게 유지해야 한다.
계산 비용은 시간은 보통 정점 수 V·간선 수 E로 표현하며 알고리즘마다 상이 정점 수를 V, 간선 수를 E라고 나타낼 때 방법에 따라 다름의 시간 특성을 가진다. 저장 공간은 그래프의 표현 방식, 큐·스택·우선순위 큐 및 결과 배열의 선택에 영향을 받으므로 실제 적용 시 구현 구조를 함께 분석한다.
네트워크 라우팅, 의존성 분석, 지도 탐색과 관계 데이터 처리에서 사용한다. 너비 우선 탐색과 깊이 우선 탐색은 다양한 그래프 알고리즘의 기본 순회 기법이다. 대표적인 변형 알고리즘 및 자료구조의 선택은 결과의 최적성, 음수 가중치나 사이클의 허용 여부, 희소·밀집 그래프 여부에 따라 달라진다. 동점 처리와 비연결 그래프 등의 경계 사례까지 정의해야 구현 결과가 명확해진다.[2]