최소 신장 트리(MST)

최소 신장 트리란 그래프에서 모든 정점을 포함하면서 가중치의 합이 최소가 되는 트리를 말한다.

최소 신장 트리를 구하기 위해서는 프림의 알고리즘을 사용하던지 크루스칼의 알고리즘을 사용하면 된다.

일반적으로 프림의 알고리즘이 크루스칼의 알고리즘보다 구현하기 쉬워서 프림의 알고리즘을 많이 사용한다.

 

*프림의 알고리즘*은 한 노드를 딱 정해서 그 노드에서부터 이웃한 노드를 우선순위 큐에 넣고 가장 가까운 노드로 나아가는 방법이다.(나아간 후에는 그 나아간 노드에 있는 이웃한 노드 또한 우선순위 큐에 넣어주는 작업을 수행해야 함. visited배열을 사용해서 이미 방문된 노드는 다시 방문하지 않음.)

 

 

*크루스칼의 알고리즘*은 간선을 우선순위 큐에 모두 넣어놓고 짧은 간선부터 하나씩 빼서 MST를 구성하는데 만약 사이클이 발생하면 그 간선은 사용하지 않고 넘어간다.(Union&&Find를 사용해서 사이클이 발생하는지 판별.)

 

크루스칼 알고리즘은 직접 그려보는 걸 추천한다. 간선의 길이가 작은 순서대로 정렬해 놓고 사이클이 만들어지면 폐기하고 만들어지지 않으면 추가하는 형식이다.

 

그러면 대체 최소 신장 트리는 언제 사용되는가??

전선이나 회로를 최소 비용은 연결할 때 사용되기도 하고 인터넷, 도로 등을 최소 비용으로 구축할 때 사용된다.