끵뀐꿩긘의 여러가지

◎프림 알고리즘(Kruskal) 프림 알고리즘은 노드를 중점으로 그리디하게 최소 스패닝 트리(MST)를 찾는 알고리즘이다. 영역을 단계적으로 넓혀간다고 생각하면 이해하기 편하다. ※MST의 정의와 MST를 구하는 다른 방법인 크루스칼 알고리즘에 대한 설명 https://kkwong-guin.tistory.com/61 Java - 크루스칼 알고리즘(Kruskal) ◎최소 스패닝 트리(minimum spanning tree) 스패닝 트리(spannig tree)란 신장 트리라고도 하며, 그래프 내의 모든 정점을 사이클 없이 포함하는 트리를 말한다. 하나의 그래프는 여러 개의 스패닝 트리를 kkwong-guin.tistory.com 1. 임의의 정점을 트리에 추가한다. 2. 임의의 정점에서 인접한 정점 중 최..

◎최소 스패닝 트리(minimum spanning tree) 스패닝 트리(spannig tree)란 신장 트리라고도 하며, 그래프 내의 모든 정점을 사이클 없이 포함하는 트리를 말한다. 하나의 그래프는 여러 개의 스패닝 트리를 가질 수 있으며, 사이클이 생기면 안 되므로 N개의 노드에 대하여 정확하게 N-1개의 엣지(간선)를 가진다. 최소 스패닝 트리(minimum spanning tree)란 MST라고도 하며, 그래프가 가질 수 있는 스패닝 트리중 간선의 가중치 합이 가장 작은 트리를 말한다. 스패닝 트리 또한 하나에 그래프에 여러 개일 수 있다. ◎크루스칼 알고리즘(Kruskal) 크루스칼 알고리즘은 간선을 중점으로 그리디하게 최소 스패닝 트리를 찾는 알고리즘이다. 1. 간선의 가중치 값을 기반으로 ..