그래프 추상 데이타 타입
가령 여러 지점과 그 지점들을 잊는 길들 처럼 현실 세계의 많은 문제들은 그래프 라는 개념을 통해 해결될 수 있습니다.
그래프 G 는 2개의 집합 V와 E로 구성됩니다. V는 공집합이 아닌 정점(Vertice) 들의 유한 집합이며, G는 정점 쌍들의 집합으로 이러한 쌍을 간선 이라 합니다. V(G) 와 E(G)는 각 각 정점과 간선들의 집합을 의미합니다. 그래프는 정점에서 특정 정점으로 가는데에 방향의 개념이 존재하는 경우와 존재하지 않는 경우로 나눌 수 있으며, 이렇게 정점에서 정점으로 이동시 방향이 있는 경우를 방향 그래프(directed graph) 라고 하며, 방향이 없는 경우 무방향 그래프(undirected graph) 라고 합니다.
여기서 정점에 연결된 간선의 수를 차수 라고 하며, Euler는 각 정점의 차수가 짝수 인 경우에만 임의의 정점에서 출발하여 각 간선을 단 한 번씩만 거치고 출발한 정점으로 되돌아오는 길이 있음을 보였으며, 이를 오일러 행로(Eulerian Walk) 라 부릅니다.
그래프 표현법
무방향 그래프의 간선 (u, v)
방향 그래프의 간선 <u, v>
그래프의 기본 연산
깊이 우선 탐색(DFS)
위처럼 인접 리스트 표현법의 경우 간선의 횟수 만큼만 탐색이 진행되므로, O(e) 의 복잡도를 가진다.
하지만 인접 매트릭스 표현으로 표현한 경우 각 정점마다 다른 정점들과 비교해야 하므로 O(n^2) 의 복잡도를 가진다.
너비 우선 탐색(BFS)
시간 복잡도: O(n^2)
신장 트리(spanning tree)
신장 트리란 G의 간선들로만 구성되고 G의 모든 정점을 포함하는 트리를 말합니다.
신장 트리를 만들기 위해서는 DFS 혹은 BFS를 모두 이용할 수 있으며, DFS를 이용하여 만들어진 신장트리를 깊이 우선 신장 트리(depth first spanning tree) 라 하고, BFS를 이용하여 만들어진 신장 트리를 너비 우선 신장 트리(breath first spanning tree) 라 부릅니다.
최소 비용 신장 트리
가중치가 부여된 무방향 그래프의 신장 트리의 비용은 신장 트리를 구성하는 간선들의 비용의 합이 됩니다. 여기서 최소 비용 신장 트리 란 최저의 비용을 갖는 신장트리를 의미합니다.
이 경우 다음의 조건을 만족해야 합니다.
- 그래프 내에 있는 간선만을 사용해야 한다.
- 정확히 n-1개의 간선만을 사용해야 한다.
- 사이클을 생성하는 간선은 사용하면 안된다.
Kruskal 알고리즘
Prim 알고리즘
최단 경로와 이행적 폐쇄
현대의 많은 지도 시스템들은 임의의 두 특정 지점 사이의 경로를 탐색하는 많은 시스템 중의 일부입니다. 경로 탐색 시스템은 일반적으로 주나 전국의 도로 시스템을 표현하기 위하여 그래프를 이용합니다. 이러한 문제에서 도시 A에서 도시 B로 가려는 운전자는 다음과 같은 사항들이 궁금할 것입니다.
- A로 부터 B로 가는 길이 있는가?
- A로부터 B로 가는 길이 2갱 이상이라면, 어느 길이 최단으로 가는 길인가?
Dijkstra 알고리즘, 하나의 출발점에서 모든 목표점: 음이 아닌 간선 비용의 경우
다이크스트라 알고리즘
Comments