최소스패닝트리

최소 스패닝 트리란 무엇일까요? 그래프가 트리형태 인것을 의미합니다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 입니다. 여기서 최소 스패닝 트리는 스패닝 트리중에서 선택한 간선의 가중치의 합이 최소인 트리를 의미합니다. 대표적으로 MST를 구현하는 방법으로 프림, 크루스칼이 있습니다. 여기서 사이클을 제작하지 않는 범위에서 구현해야 합니다. 왜냐하면, 트리는 사이클이 존재하지 않기 때문입니다. 1)프림 초록색점은 선택한 노드 흰색은 선택하지 않은 노드 입니다. 선택과 선택하지 않은 노드 사이의 간선에서 가중치 값이 가장 작은 값을 갖는 2를 추가합니다. 간선2를 선택하게 됩니다. 선택한 노드와 선택하지 않은 노드 사이에 간선들은 3, 1, 3, 4 가 됩니다. 간선 1이 선택됩니다. 노드 5는 이..