06 - 3. 다익스트라 최단 경로 알고리즘
그래프에서 단일 시작 최단 경로 문제는 구글 지도 또는 네비게이션 등에서 경로를 탐색할 때 사용된다. 다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변경한 형태이다. 두 알고리즘의 차이점은 다음과 같다. - 프림 알고리즘은 경계로부터 최소 거리를 정점의 거리 값으로 설정하지만, 다익스트라 알고리즘은 시작 정점으로부터 각 정점까지의 전체 거리를 사용한다. - 다익스트라 알고리즘은 목적 정점이 나타나면 종료하지만, 프림 알고리즘은 모든 정점을 방문해야 종료된다. 다익스트라 알고리즘 과정 1. 시작 정점을 제외한 모든 정점의 거리 값을 무한대로 초기화하고 모든 거리 값을 최소 힙 H에 추가한다. 2. 최소 힙 H로부터 꺼낸 하나의 정점을..
06 - 2. 프림의 MST 알고리즘
프림 알고리즘은 BFS의 동작 방식과 유사하다. 먼저 시작 정점을 이용하여 경계를 구성하고, 현재 경계에 인접한 정점을 반복적으로 탐색한다. 이때 경계를 관통하는 엣지 중에서 가장 가중치가 작은 엣지를 선택하고, 이 엣지에 연결된 정점을 방문한다. 프림 알고리즘의 동작 프림 알고리즘을 구현하려면 그래프의 각 정점에 경계로부터의 거리 정보를 기록해야 한다. 동작 순서는 다음과 같다. 1. 모든 정점의 거리 값을 무한대로 초기화한다. 단, 시작 정점에서 자기 자신까지의 거리는 0이다. 그 다음 모든 거리 값을 최소 힙 H에 추가한다. 2. 최소 힙 H로부터 정점을 하나 꺼낸다. 이 정점을 U라고 하면, 정점 U는 경계에서 가장 가까이 있는 정점이 된다. 이 정점을 MST에 추가하고, 이 정점을 포함하도록 경..
06 - 1. 그래프 순회, 탐색 (DFS, BFS)
그래프는 범용적인 특징을 가지고 있어서 많은 응용 프로그램에서 사용된다. 그래프를 통해 유한 상태 기계(finite state machine, automata)를 모델링 하거나, 도로 네트워크에서 교통 흐름을 연구하기도 한다. 이번 장에서는 가중치가 양수인 주로 방향 가중 그래프에 대해 다룰 것이다. 그래프 순회 문제 그래프 G = 가 주어질 때 특정 정점 s로부터 시작하여 모든 정점 v ∈ V를 방문하는 문제로, 그래프에서 특정 정점을 찾기 위한 용도로 사용될 수도 있기 때문에 그래프 탐색 문제라고도 부른다. 대표적인 탐색 방법은 다음 두가지가 있다. - 너비 우선 탐색(BFS, Breadth First Search) 시작 정점을 경계에 추가하고 현재 경계에 인접한 정점을 반복적으로 탐색한다. BFS는..
05 - 2. MST와 Disjoint-Set, 크루스칼 알고리즘, 그래프 컬러링
1. MST (Minimum Spanning Tree, 최소 신장 트리)와 Disjoint-Set - 정점(Vertex)의 집합 V와 가중치를 갖는 엣지(Edge)의 집합 E로 구성된 그래프 G = 가 주어졌을 때, 모든 정점을 연결하고 연결된 엣지의 가중치의 합이 최소인 트리 T (실생활의 예로 상수도관 네트워크 또는 도로 네트워크의 설계 등에 쓰임) Disjoint-Set 또는 Union-Find 자료구조 (서로소 집합 자료구조) *서로소 집합이란? 공통 원소가 없는 두 집합, 교집합이 공집합인 집합 디스조인트-셋 자료 구조는 트리 형태의 원소로 구성된 포레스트(forest)이다. 각각의 원소는 숫자 ID에 의해 표현되고, 랭크(Rank)와 부모에 대한 포인터를 가진다. 디스조인트-셋 자료구조는 다음..