최대 비용을 가지는 신장 트리를 만드는 방법?
1. 문제 7044번: Bad Cowtractors (acmicpc.net) 7044번: Bad Cowtractors Bessie has been hired to build a cheap internet network among Farmer John's N (2
1. 문제 7044번: Bad Cowtractors (acmicpc.net) 7044번: Bad Cowtractors Bessie has been hired to build a cheap internet network among Farmer John's N (2
1. 개요 가중치가 있는 무방향 그래프에서 최소 신장 트리를 찾는 대표적인 알고리즘 중 하나이다. 크루스칼 알고리즘이 간선들을 선택해가면서 최소 신장 트리를 구성하는 반면에 프림 알고리즘은 정점을 선택하고, 인접한 정점 중에서 최소 비용을 가지는 간선을 하나씩 선택해가면서 최소 신장 트리를 구성하는 일종의 그리디 알고리즘이다. 다익스트라 알고리즘과 사실상 동일한 알고리즘이다. 참고로 다익스트라 알고리즘은 음수 가중치에서는 동작하지 않지만, 프림 알고리즘은 음수 가중치에서도 동작한다고 한다 2. 알고리즘 2-1) 임의의 정점을 하나 선택해서 최초의 트리를 구성 2-2) 선택한 정점과 트리에 포함된 정점들과 인접한 정점중 최소 비용의 간선이 존재하는 정점을 선택한다 2-3) 모든 정점이 선택될 때까지 위 과..
1. 신장트리(spanning tree) n개의 정점으로 이루어진 "무방향 그래프"에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 하나의 그래프가 있을때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이때, 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이다. 그래서 이러한 그래프를 신장 트리라고 부른다. 위와 같은 그래프에서 신장 트리는 여러개 찾을 수 있다. 예를 들어 아래와 같은 그래프는 하나의 신장 트리이다. 하지만 다음 그림과 같은 그래프들은 신장 트리가 아니다. 구체적으로 다음은 노드 1을 포함하고 있지 않다 다음은 노드 4-6-7에서 사이클이 발생하므로 신장트리가 아니다. 2. 최소 신장 트리(Minimum spanning tree)..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck