Koo's.Co

1. 프림 알고리즘(Prim's Algorithm) 프림 알고리즘은 방향이 없는 무방향 그래프에서 비용이 최소가 되는 최소 신장 트리(MST, Minimum Spanning Tree)를 찾기 위한 알고리즘이다. 프림 알고리즘은 그리디 알고리즘이 적용된 방법으로 임의의 노드에서 시작하여 노드를 발견할 때마다 연결된 간선 중 가중치가 가장 작은 노드의 방향으로 순회하는 알고리즘이다. 다음과 같은 그래프가 주어질 때 프림 알고리즘을 이용해 최소 신장 트리를 구하려 한다. 여기서는 1번 노드에서 시작해보자. 최종적으로 다음과 같은 최소 신장 트리를 구할 수 있다. 프림 알고리즘을 이용해 최소 신장 트리를 구하면 어느 위치에서 시작해도 동일한 형태의 최소 신장 트리를 구할 수 있다. 프림 알고리즘은 매번 노드가 ..

1. union-find 알고리즘 union-find 알고리즘은 서로 다른 원소가 하나의 집합에 속하는지 확인하기 위한 알고리즘이다. 서로소 집합(Disjoint-set) 알고리즘으로 서로 다른 두 노드가 같은 그래프에 속하는지 확인하는 것이 목적이다. 그래프에서 cycle을 형성하는지 확인하기 위해 사용 두 원소가 같은 집합에 속하는지 확인하기 위해 사용 2. 동작 방법 위와 같은 그래프가 주어질 때, union-find 알고리즘을 이용해 같은 부분집합에 속하는지 확인하려 한다. 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 union-find 알고리즘에서는 각 노드들의 부모 노드들에 대한 테이블을 생성하는데 스스로를 부모 노드로 초기화시켜준다. 1 2 3 4 5 6 7 8 1 2 1 4 5..