크루스칼 알고리즘

template <class T>  struct MinimumSpanningTree {
  /*
    T: 가중치의 타입

    n: 노드 개수
    m: 간선 개수
    result : MST 결과 (가중치 합)
  */ 
  struct Edge { 
    int u, v;
    T weight;

    Edge(int u1, int v1, T weight1) : u(u1), v(v1), weight(weight1) {}
    bool operator< (Edge other) const { return weight < other.weight; }
  };

  int n, m;
  vector<int> uf;
  vector<Edge> edges;
  vector<Edge> chosen_edges;

  T result; // MST의 가중치 합
  int cnt; // 뽑은 간선 수

  MinimumSpanningTree(int n1, int m1) : n(n1), m(m1) {
    uf.resize(n + 1, -1);
    result = 0;
    cnt = 0;
  }

  int find(int a) {
    /*
      Union-Find: Find 연산
    */
    if (uf[a] < 0) return a;
    return uf[a] = find(uf[a]);
  }

  int merge(int a, int b) {
    /*
      Union-Find: Union
      합쳐진 경우 true 반환
    */

    a = find(a);
    b = find(b);

    if(a == b) return false;

    uf[b] = a;
    return true;
  }

  void add_edge(int u, int v, T cost) {
    edges.push_back(Edge(u, v, cost));
  }

  void run() {
    sort(edges.begin(), edges.end());

    for(int i = 0; ; i++) {
      if(merge(edges[i].u,  edges[i].v)) {
        result += edges[i].weight;

        chosen_edges.push_back(edges[i]);
        if(++cnt == n - 1) break;
      }
    }
  }
};
shinkeonkim / TIL

[알고리즘] Minimum Spanning Tree, MST (최소 신장 트리) #53

크루스칼 알고리즘
