《数据结构与算法分析：C语言描述》复习——第九章“图论”——Prim算法

2014.07.04 22:42

简介：

　　给定一个无向带权连通图（三个条件），选出n-1条边将这n个顶点连成一棵树，使得这棵树的权值之和最小。

描述：

　　本次使用Prim算法来解决这个问题。Prim算法的思想是两点：BFS与贪婪。

　　我们从一个顶点出发，把这个顶点对应的边加入到优先队列中。既然是优先队列，当然是边的权值短的优先。

　　每一轮我们从优先队列中取出一条边u->v，u已经被访问过（选出的这条边权值必然是目前最短的），如果v未被访问过，那么标记v，并把从v出发的边加入队列。

　　这样从一点出发逐渐散开的搜索形式属于广度优先搜索，而短边优先的策略则属于贪婪。因此Prim算法就是BFS与贪婪算法的结合。

　　说实话，直接看代码实现或许更简单。

实现：

// My implementation for Prim's Algorithm, for minimum spanning tree problem.
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INFINITY = 1000000000;

struct Edge {
    int x;
    int y;
    int cost;
    Edge(int _x = 0, int _y = 0, int _cost = 0): x(_x), y(_y), cost(_cost) {};
};

struct GreaterFunctor {
    bool operator () (const Edge &e1, const Edge &e2) {
        return e1.cost > e2.cost;
    }
};

int primsAlgorithm(const vector<vector<int> > &graph)
{
    // Prim's Algorithm for weighted undirected graph.
    
    int n;
    n = (int)graph.size();
    if (n < 2) {
        return 0;
    }

    int i;
    // Minimal heap, the top is smallest.
    priority_queue<Edge, vector<Edge>, GreaterFunctor> pq;
    vector<bool> visited;
    int visited_count;
    int min_cost;
    
    visited.resize(n, false);
    
    // Start constructing the tree from 0th vertex.
    min_cost = 0;
    visited[0] = true;
    for (i = 1; i < n; ++i) {
        if (graph[0][i] == INFINITY) {
            continue;
        }
        pq.push(Edge(0, i, graph[0][i]));
    }
    visited_count = n - 1;
    
    Edge e;
    while (!pq.empty()) {
        e = pq.top();
        pq.pop();
        if (visited[e.y]) {
            continue;
        }
        min_cost += e.cost;
        visited[e.y] = true;
        --visited_count;
        if (visited_count == 0) {
            break;
        }
        
        for (i = 0; i < n; ++i) {
            if (i == e.y || graph[e.y][i] == INFINITY || visited[i]) {
                continue;
            }
            pq.push(Edge(e.y, i, graph[e.y][i]));
        }
    }
    
    while (!pq.empty()) {
        pq.pop();
    }
    
    return min_cost;
}

int main()
{
    vector<vector<int> > graph;
    int n;
    int nk;
    int i, j;
    int tmp, tmp_dist;
    int min_cost;
    
    while (cin >> n && n > 0) {
        graph.resize(n);
        for (i = 0; i < n; ++i) {
            graph[i].resize(n, INFINITY);
        }
        
        for (i = 0; i < n; ++i) {
            cin >> nk;
            for (j = 0; j < nk; ++j) {
                cin >> tmp >> tmp_dist;
                graph[i][tmp] = graph[tmp][i] = tmp_dist;
            }
        }
        
        min_cost = primsAlgorithm(graph);
        
        cout << "The weighted sum of minimum spanning tree is " << min_cost << "." << endl;
        
        for (i = 0; i < n; ++i) {
            graph[i].clear();
        }
        graph.clear();
    }
    
    return 0;
}