[MST] Prim 알고리즘
- Algorithm
- 2021년 4월 12일
우선순위 큐의 방법을 이용하는 알고리즘으로 vertex를 한개씩 선택하며 최소 비용의 edge를 찾는 방법이다. decrease-key의 개념을 이용하며 decrease-key는 현재 계산된 v노드까지의 거리보다 현재 노드 u부터 v까지의 경로가 더 작다면 값을 갱신해주는 방법을 이용한다. 1. 특징 정점 선택 기반 시작 정점부터 출발하여 해당 노드까지의 최소 비용을 기록하는 배열을 이용하여 구하는 방식 자료구조중 하나인 우선순위 큐를 이용하며, 우선순위 큐를 어떻게 구현했는가가 시간복잡도에 영향 2. Pesudo Code 3. 구현 방법 vertex들의 key값을 Infinity로 초기화 start vertex의 key값을 0으로 초기화 (어떤 vertex를 선택하더라고 MST가 나온다.) 현재 vertex에 인접한 vertex들 중 선택하지 않았고, 가장 vertex의 key값이 작은 vertex을 찾기 (exract-min = 최소값 추출) 현재 vertex를 선택 인접한 vertex중 vertex의 key값보다 간선의 가중치가 더 작다면 key값을 가중치로 갱신 (decrease -key) 인접한 vertex중 선택하지 않았고, 가장 vertex의 key값이 작은 vertex를 기준으로 3번부터 다시 반복 모든 vertex가 선택되었다면 종료 1) 인접 행렬 위에 설명한 3번 방법의 extract-min을 아래와 같이 배열로 구현하며, 매번 V회 반복한다....
Read More[MST] Kruskal 알고리즘
- Algorithm
- 2021년 4월 12일
그래프 중에서 MST (Minumum Spannig Tree) 를 찾는 알고리즘중에 하나로 Union-Find알고리즘을 이용하며, 간선 (edge)의 가중치(weight)를 오름차순으로 정렬하여 가중치가 사이클이 생기지 않는 낮은 간선을 먼저 선택하는 방법이다. 사이클의 여부를 확인할때 union-find 알고리즘을 이용하여 찾는 알고리즘이다. union find 알고리즘 설명 보기 1. 특징 탐욕적인 방법 (Greedy) 간선 선택 기반 알고리즘 간선 선택 단계에서 사이클을 포함하지 않고 최소 비용 간선을 선택 부분 트리집합을 병합하면서 하나의 트리로 확장 희소그래프에 적합 ( V > E ) 정렬 속도가 시간복잡도에 영향 2. Pesudo Code 3. 구현 Note...
Read More