프림 알고리즘

프림 알고리즘

선수 지식 안전한 간선 보조정리

안전한 간선 보조정리에 따르면, 어떤 컷을 연결하는 간선 중 최소임이 확실한 간선을 하나씩 추가하면서 최소 신장 트리를 점진적으로 만들어 나갈 수 있습니다.

이를 활용하는 방법 중 하나가 프림 알고리즘입니다:

  • 처음에 신장 트리는 임의의 정점 하나입니다.
  • 최소 신장 트리를 찾을 때까지, 현재 신장 트리의 어떤 정점에서 아직 추가하지 않은 정점으로 나가는 간선 중 가중치가 최소인 간선을 선택합니다. 이 간선을 신장 트리에 추가하고, 신장 트리를 찾을 때까지 이 과정을 처음부터 다시 반복합니다.

이 알고리즘은 다익스트라 알고리즘과 매우 비슷하지만, 다음 정점을 다른 가중치 함수로 선택한다는 점이 다릅니다. 즉, 그 정점까지의 총 거리 대신 그 정점을 잇는 최소 간선의 가중치를 사용합니다.

아주 단순한 $O(nm)$ 구현입니다. 매번 모든 간선을 살펴봅니다:

const int maxn = 1e5, inf = 1e9;
vector from, to, weight;
bool used[maxn]

// считать все рёбра в массивы

used[0] = 1;
for (int i = 0; i < n-1; i++) {
    int opt_w = inf, opt_from, opt_to;
    for (int j = 0; j < m; j++)
        if (opt_w > weight[j] && used[from[j]] && !used[to[j]])
            opt_w = weight[j], opt_from = from[j], opt_to = to[j]
    used[opt_to] = 1;
    cout << opt_from << " " << opt_to << endl;
}

$O(n^2)$ 구현입니다:

const int maxn = 1e5, inf = 1e9;
bool used[maxn];
vector< pair<int, int> > g[maxn];
int min_edge[maxn] = {inf}, best_edge[maxn];
min_edge[0] = 0;

// ...

for (int i = 0; i < n; i++) {
    int v = -1;
    for (int u = 0; u < n; u++)
        if (!used[u] && (v == -1 || min_edge[u] < min_edge[v]))
            v = u;

    used[v] = 1;
    if (v != 0)
        cout << v << " " << best_edge[v] << endl;

    for (auto e : g[v]) {
        int u = e.first, w = e.second;
        if (w < min_edge[u]) {
            min_edge[u] = w;
            best_edge[u] = v;
        }
    }
}

다익스트라 알고리즘에서와 마찬가지로, 최적의 정점을 선형 탐색하지 않고 우선순위 큐로 관리할 수 있습니다. 그러면 $O(m \log n)$ 구현이 됩니다:

set< pair<int, int> > q;
int d[maxn];

while (q.size()) {
    v = q.begin()->second;
    q.erase(q.begin());

    for (auto e : g[v]) {
        int u = e.first, w = e.second;
        if (w < d[u]) {
            q.erase({d[u], u});
            d[u] = w;
            q.insert({d[u], u});
        }
    }
}

$O(n^2)$ 알고리즘도 잊어서는 안 됩니다. 이 알고리즘은 밀집 그래프에서 더 잘 동작합니다.