알고리즘/그래프
2020. 5. 5.
최소 스패닝 트리
우선 '최소 스패닝 트리'가 무엇을 뜻하는 단어인지 먼저 알아봅시다. 우선 '트리'란, 사이클을 갖지 않는 연결 그래프를 뜻합니다. 정점이 \(V\)개인 트리는 \(V-1\)개의 간선으로 모두 연결되어 있게 됩니다. '그래프의 스패닝 트리'는, 그래프에서 일부의 간선을 선택해 만든 트리를 뜻합니다. 따라서 이 연결 그래프는 다음과 같은 스패닝 트리를 가질 수 있게 됩니다. 물론 위 2가지의 형태가 아닌 다른 형태의 스패닝 트리도 존재합니다. '그래프의 최소 스패닝 트리'는, 가중치가 있는 연결 그래프에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 말합니다. 따라서 이 연결 그래프의 최소 스패닝 트리는 이런 형태가 됩니다. 가중치의 합은 17로, 가중치의 합이 이보다 작은 스패닝 트리는 만들 수 없습니..
