[최소 스패닝 트리] 프림 알고리즘

 

최소 스패닝 트리 : 간선의 가중치가 있는 그래프의 부분 그래프 중,

사이클이 없으며 가중치의 합이 최소인 부분 그래프

최소 스패닝트리를 만드는데에는 크루스칼이 더 많이 쓰이지만 나는 Priority_queue를 사용하는 프림 알고리즘이 익숙하다.

사이클 체크를 해줄필요도 없이 임의의 노드로 부터 출발하여 그 노드와 인접한 모든 노드를 Priority_queue에 넣어주어서 가장 가까운 위치에 있는 노드를 방문해주면 끝난다.

구현도 간단하고 이름도 이뻐서 애용중,,,

크루스칼과 시간 복잡도도 거의 비슷해서 초록 책에서도 취향대로 가라고 한다.

while(!pq.empty()){
    long double dist=pq.top().first;
    int dest=pq.top().second;
    pq.pop();
    if(vis[dest])continue;
    vis[dest]=1;
    ans+=dist;
    for(auto i:adj[dest]){
      // 이미 방문하지 않은 노드만 추가시켜서 시간 단축시키기!
      if(vis[i.second]==0) pq.push(i);
    }
  }