Algorithm/Graph
[Graph] Dijkstra algorithm (다익스트라 알고리즘)
다익스트라 알고리즘은 그래프 문제에서 최단 경로를 찾는 알고리즘이다. 정점 사이의 거리가 일정하지 않을 때 정점 A에서 정점 B로 가는 최단 거리를 찾는 방법이다. 정점사이의 최단거리를 갱신하며 더 짧은 것으로 저장하는 방식이다.자세한 내용은 여기를 클릭! (출처 : 위키백과) 개요 a와 b 사이의 최단 경로를 찾는 데이크스트라의 알고리즘이다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다. 프림 알고리즘과 유사하게 초기 거리를 무한대로 설정하고, 새로운 경로가 기존값보다 짧으면 갱신한다. 구현 위 이미지와 동일한 정점과, 거리를 가진 그래프에 대해 1번 정..
[Graph] Prim Algorithm (프림 알고리즘)
프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 O(ElogV)의 시간복잡도를 가진다. 자세한 내용은 여기를 클릭! (출처 : 위키백과) 개요 프림 알고리즘은 아래의 순서대로 작동한다: 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다. 그래프의 모든 변이 들어 있는 집합을 만든다. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다. 알..
[Graph] Kruskal’s algorithm (크루스칼 알고리즘)
크러스컬 알고리즘(Kruskal’s algorithm)은 최소 비용 신장 부분 트리(MST)를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 O(ElogV) 의 시간복잡도를 가진다. 자세한 내용은 여기를 클릭! (출처 : 위키백과) 개요 크러스컬 알고리즘은 아래의 순서대로 작동한다. 그래프의 각 꼭짓점이 각각 하나의 나무(자료구조의 tree)가 되도록 하는 숲 F 을 만든다. 모든 변을 원소로 갖는 집합 S 를 만든다. S가 비어있지 않는 동안 가장 작은 가중치의 변을 S 에서 하나 빼낸다. 그 변이 어떤 두 개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다. 그렇지 않다면 그 변은 버린다. 알고리즘이 종료됐을 때 숲 F는 하나의 최소 비용 신장 부분 그래..
[Graph] BFS (너비 우선 탐색)
너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식이다. 그래프를 탐색하는 방법에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)로 크게 2가지가 있다. 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형식의 자료구조인 큐를 활용한다. BFS는 시작 정점 기준 거리가 가까운 곳부터 먼곳으로 탐색을 진행하기 때문에, 특정정점까지 가는 최단거리를 구하는데 용이하며, BFS 탐색이 종료된 경우 직전에 방문한 정점이 시점과 가장 먼 정점이라는 것을 알 수 있다. 개요 시작정점 v를 결정하여 방문한다. 정점 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있..
[Graph] DFS (깊이 우선 탐색)
완전 탐색 방법으로 가장 깊은 바닥까지 갔다가, 해당 경로가 종료될 경우 마지막 갈림길로 돌아가 탐색을 반복한다. 이때, 마지막 갈림길로 돌아가는 행위를 위해 스택이 필요하다. 비선형 구조인 그래프를 빠짐없이 검색하는 방법(완전탐색). 깊이 우선 탐색과 너비 우선 탐색이 있다. 시작 정점의 한방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 막다른 길이면, 이전 갈림길로 돌아가 탐색을 진행한다. 마지막 갈림길로 돌아가는 행위를 하기 위해 후입 선출 구조인 스택을 사용한다. 개요 시작정점 v를 결정하여 방문한다. 정점 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있다면, 정점 w를 스택에 push하고 정점 w를 방문한다. 그리고 w를 v로 하여 다시 위 순서를 반복한다. 방문하지 않은 정점..