[알고리즘] 최소비용 신장트리, Minimum Spanning Tree

  greedy approach를 신장트리로 시각화할 수 있다. 신장트리는 정점이 서로 연결되어있고 방향이 없는 그래프에서 순환 경로가 없도록 엣지를 제거하되 모든 정점이 그래프에 포함되도록 연결한 부분 그래프이다. 여기서 비용이 최소가 되도록 연결한 그래프(신장트리)를 최소비용 신장트리라고 한다. 글로만 읽으면 무슨 말인지 이해가 잘 안될테니 그림으로 이해해보자. 아래 그림은 신장트리의 한 예를 보여준다.

 

신장트리 예시(오른쪽)

  위 그림의 신장트리가 과연 최소신장트리일까? 오른쪽의 신장트리가 왼쪽의 그래프에서 도출될 수 있는 그래프들 중 비용이 가장 적은 그래프일까? 그렇지 않다. 비용이 더 작은 엣지들을 사용해서도 충분히 모든 정점들을 이으면서 순환 경로가 없도록 그래프를 만들 수 있다는 것을 알 수 있다.

  하지만 이는 위의 그래프가 매우 단순하기 때문에 우리가 한눈에 알 수 있는 것이다. 문제가 더욱 복잡해진다면, 우리는 최소비용신장트리를 만들기위한 알고리즘을 세우고 이에 따라 해답을 찾아야한다. 이 때 사용되는 알고리즘의 수도코드는 아래와 같다.

 

F = ∅;
while (the instance is not solved) {
  select an edge according to some locally optimal consideration; //selection procedure
  
  if (adding the edge to F does not create a cycle) //feasibility check
    add it;
    
  if (T = (V,F) is a spanning tree) //solution check
    the instance is solved;
}

 

① 선택 절차, selection procedure

  : 현재 상태에서 가장 좋다고 생각되는 edge를 선택한다. 즉, locally optimal한 edge를 선택한다.

② 타당성 검증, feasibility check

  :  선택한 edge를 solution set에 넣을지 말지 결정한다.

③ 해답 검증, solution check

  : 새로 얻은 신장트리가 최종 해인지 점검한다. 즉 다른 해답을 더 모을지, 다 모은 것인지 검사한다.

 

  위 알고리즘을 보고나면 한 가지 궁금증이 생길 것이다. 'locally optimal한 edge가 무엇일까?'라는 것이다. 이에 대한 절대적인 정답은 없으며, 따라서 이 optimal의 기준이 무엇이냐에 따라 알고리즘이 달라진다. 예를들면 출발점과 다른 정점이 이루는 edge의 길이가 짧은 것부터 고를 수도 있고, 출발점에서의 거리와는 상관없이 무조건 길이가 짧은 edge들 부터 고를 수도 있다.

  앞으로 알아볼 prim 알고리즘, kruskal 알고리즘 모두 최소 신장트리를 사용하지만 두 알고리즘의 optimal 기준은 서로 다르다. 다음시간에는 먼저 prim 알고리즘에 대해 설명하도록 하겠다!! (마음같아서는 두 알고리즘 모두 이 글에서 다 설명하고싶지만 글이 너어어무 길어질 것 같으니.. 두 알고리즘에 대한 글을 다 작성하고 나면 링크라도 밑에 걸어두도록 하겠다..^^)

 

  기억했음 하는 것 : prim 알고리즘, kruskal 알고리즘 모두 최소신장트리를 사용하고, 그 locally optimal의 기준은 서로 다르다!

 

[알고리즘] 프림 알고리즘, Prim's Algorithm | 설계 및 분석

[알고리즘] 크루스칼 알고리즘, Kruskal's Algorithm | 설계 및 구현코드