아무 말

들어가며.. 그래프 이론에서의 가장 기본적인 부분으로, 많은 그래프 알고리즘에는 그래프 탐색이 이용된다. 본문에서는 BFS와 DFS에 대해 다룬다. 그래프 탐색의 시간복잡도 그래프 탐색은 말 그대로 그래프를 탐색하는 것이다. 모든 정점과 간선을 확인해야 한다. 따라서 어떤 방법으로 탐색을 하던 간에 알고리즘의 시간복잡도는 \(\Omega(|V+E|)\)이다. 그리고 본문에서 다루게될 DFS와 BFS는 인접 리스트를 이용할 때 \(\Theta(|V+E|)\)의 시간복잡도를 가진다. DFS DFS(depth first search, 깊이 우선 탐색)은 현재 방문할 수 있는 vertex 중에서 depth가 큰 vertex부터 방문하는 방법이다. 다만, 이는 검색 트리에서의 이야기이고 본문에서 다룰 그래프에서의..

들어가며.. 다익스트라 알고리즘(Dijkstra's algorithm)을 이용하면 \(O(|E|+|V| \log(|V|))\)에 단일 출발지 최단 경로를 구할 수 있습니다. 만약, 간선의 가중치가 0 혹인 1 뿐이라면 더 빠르게 작동시킬 수 있을까요? 0 - 1 너비 우선 탐색 0 - 1 너비 우선 탐색은 다익스트라 알고리즘과 완전히 같은 아이디어로 작동합니다.(사실 0 - 1 너비 우선 탐색은 다익스트라 알고리즘을 최적화 한 것입니다.) 그저 가중치가 0 혹은 1 밖에 없는지라 priority queue를 사용하지 않을 수 있다는 것이 차별점이라 할 수 있겠습니다. 다익스트라에서 priority queue는 현재 queue에 들어있는 정점 중 시작 점으로 부터 가장 가까운(=현재 구한 최단 경로가 가장..

Introduction 트리를 분할하는 방법으로는 대표적으로 Centroid Decomposition과 Heavy-Light Decomposition이 있다. Centroid Decomposition의 경우, 주로 트리에서 분할정복을 위해 이용되며, Heavy-Light Decomposition은 우리가 다루기 더 쉬운 형태인 선형 배열의 형태로 트리를 바꾸어 문제를 해결하기 위하여 사용한다. 이번 포스팅에서는 Heavy-Light Decomposition을 다룬다. Heavy-Light Decomposition Heavy-Light Decomposition(HLD)는 트리의 정점을 여러 경로의 집합으로 나누는 방법이다. HLD를 수행하기 위해서 일단 임의의 정점의 트리의 루트로 잡는다. 이후, 루트에서..

서론 그래프에서의 동형사상을 찾는 문제는 NP이다. 다만, 트리에서의 동형사상은 다항시간에 판정할 수 있다. 이번 포스팅에서는 두 rooted 트리에서의 동형사상을 찾는 알고리즘인 AHU Algorithm [Aho, Hopcroft and Ullman]과 unrooted tree의 동형사상을 찾는 방법을 다룰 것이다. 1. 동형인지 여부를 판정할 트리가 rooted tree 일 때 - AHU algorithm AHU algorithm에서는 트리를 몇 개의 튜플로 해싱하여 두 트리가 같은지 비교한다. 이때, depth 별로 tuple을 하나씩 형성해주어야 한다. 이 tuple을 이루는 항은 AHU algorithm에서는 각 depth별 vertex의 degree들이다. 또, tuple은 항상 정렬된 상태로..

위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기서 만약 그래프가 순환을 가진다면 선형 나열은 불가능하다. 아래와 같은 알고리즘은 하나의 방향 비순환 그래프를 위상 정렬 한다. 위상 정렬(G) 1 각 정점 v에 대해 종료 시간 v.f를 계산하기 위해 DFS(G)를 호출한다. 2 각 정점이 종료될 때마다 연결 리스트의 맨 앞에 삽입한다. 3 return 정점의 연결 리스트 중요한것은 위상 정렬한 순서대로 일을 수행할 때 일을 수행하지 못하는 일이 나오지 않는다는 것이다. 미리 어떠한 행동 A를 해야 B를 할 수 있다면 A를 하고 B를 해야한다는 것이다. 위 방식으로 위상 정렬을 할 때 시간복잡도는..