이즈미르의 프로그래밍

이번에는 그래프의 최소 신장 트리(minimum spanning tree)를 알아보자. 최소 신장 트리가 무엇일까? 먼저 그래프는 익히 알고 있을 것이다. 그래프는 노드와 간선으로 구성된다. 지하철 노선도로 비유하자면 지하철 역이 노드이고 지하철 역과 역을 잇는 선이 간선이 될 것이다. 지하철 역처럼 노드는 무엇인가를 나타내기 위해 사용하고 간선은 노드와 노드의 관계를 나타낸다. (어느 역과 어느 역이 연결되어 있는지 등) 간선은 보통 비용을 포함하고 있다. 비용의 종류는 그래프의 용도에 따라 다양하게 결정된다. 거리가 될 수도 있고 금전적인 진짜 비용이 될 수도 있다. 여기서 노드들과 노드들을 제각기 잇는 간선이 있을 때 모든 노드들을 최소의 비용을 들여 연결한 그래프 모습을 최소 신장 트리라고 한다...