MST를 알아볼까요?

MST?

  • MST는 Minimum Spanning Tree 의 줄임말입니다. 신장트리, 즉 Spanning Tree는 무향 연결 그래프에서 간선을 부분적으로 뽑아서 그래프의 정점과 갯수가 같은 트리를 뜻합니다. 그렇다면 Minimum이 붙은 신장트리는 간선의 Cost 의 합이 최소 인 스패닝 트리인건 알 수 있겠죠?
  • MST를 구현하는 방법에는 다음 3가지 방법이 있습니다.
    • 프림 알고리즘
    • 솔린 알고리즘
    • 크루스칼 알고리즘
  • 여기에서는 가장 많이 쓰이고, 비교적 빠른 크루스칼 알고리즘으로 구현하는 방법을 써보도록 하겠습니다!

크루스칼 알고리즘이란

  • 그리디한 방법을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하여, 최적의 답을 구하는 것이다.
  • 여기서 쓰이는 그리디한 방법은, 간선의 Cost가 적은 것부터 선택하여 간선이 이미 그래프 내에 포함되어 있는지 확인 을 해준다.
  • 만약, 선택한 2개의 노드가 간선에 포함이 되어있다면 (사이클을 형성한다면) , 선택을 하지 않고 다음 간선을 확인하게 된다.

그래프 내에 포함되어 있는지 확인?

  • 그래프 내에 노드가 포함되어 있어서 사이클을 형성한다는 뜻은, 2개의 노드를 추가하지 않아도 이미 2개의 노드는 연결이 되어있다는 뜻이다. 다시 말해, 쓸데없는 간선을 추가하는데 비용을 쓰지 않겠다는 뜻이다.

  • 자, 그러면 사이클을 형성하는지 알아보는 방법은 2가지가 있다.

    • Union Find
      • 선택된 a, b 노드의 최상위 부모노드가 같은지 확인하면서 Merge를 한다.
      • 부모노드가 같다는 뜻은, 두개의 노드가 같은 그래프에 속한 다는 것이고 사이클이 형성된다는 뜻이다.
      • BFS 방법보다 매우 빠른 속도를 보이고, 거의 대부분 이것만 쓴다고 해도 무방하다.
    •  DFS
      • 선택된 a, b 노드에서 a로 부터 그래프를 출발하여 b를 만나게 된다면 사이클이 형성된다는 뜻이다.
      • 매번 추가를 할 때마다 DFS를 한다면, 그만큼 시간이 걸리므로 추천하지는 않는다.
      • 그러나, 매번 DFS를 할때마다 Memorization을 진행해준다면 더 빠르게 최상위 부모노드를 찾을 수 있다.

MST with Union Find

그래프

KakaoTalk_20201022_002503723

코드

결과

KakaoTalk_20201022_002530982

rufrhkl

PLUS TIP!

  • 만약 파이썬을 사용해본 적이 있다면, 리스트와 튜플의 편함을 알고 있을 것이다. C++의 vector와는 다르게 pair를 사용할 필요도 없거니와 내가 원하는대로 원소를 증가시킬 수 있기 때문이다.
  • 그러한 튜플이 C++에도 존재한다는 것이다!!!!!! * ㅡ *
  • 백문불여일견 코드를 보면 설명없어도 이해가 갈 것이다.
  • pair를 쓰기 지친 당신에게 뜌쁠을 선물해드리겠습니다! 빠셍!