贪婪算法:Prim算法

2016年01月12日 原创
关键词: C++ 数据结构 算法 贪心策略
摘要 Prim算法是生成最小生成树的一种算法,采用的是贪婪策略。

Prim算法是一个生成最小生成树的算法,在解决最短路径等问题时很好用。Prim算法中维持了一个集合A,这个集合A中的边总是构成一棵树。这棵树从一个任意的根节点r开始,一直长大到覆盖集合V(顶点集合)中的所有节点时为止。算法每一步在连接集合A和A之外的节点的所有边中,选择一条轻量级边(即权重最小的边)加入到A中。因此,当算法终止时,A中的边形成一棵最小生成树。

下图是《算法导论》上的一张Prim算法的执行过程图。

下面是Prim算法的伪代码

MST-PRIM(G,w,r)

1   for each u∈G.V

2     u:key=∞

3     u:π=NIL

4   r:key=0

5   Q=G.V

6   while Q≠∅

7     u=EXTRACT-MIN(Q)

8     for each v∈G.Adj[u]

9     if v∈Q and w(u,v)<v.key

10    v.π=u

11    v.key=w(u,v)

上述伪代码中,连通图G和最小生成树的根节点r作为算法的输入。在算法的执行过程中,所有不在树A中的节点都存放在一个基于key属性的最小优先队列Q中。对于每个节点v,属性v.key保存的是连接v和树中节点的所有边中最小边的权重。我们约定,如果不存在这样的边,则v.key=∞。属性v.π给出的是节点v在树中的父节点。

算法第1~5行将每个节点的key值设置为∞(除根节点r以外,根节点r的key值设置为0,以便使该节点成为第一个被处理的节点),将每个节点的父节点设置为NIL,并对最小优先队列Q进行初始化,使其包含图中所有的节点。算法第7行将找出节点u∈Q,该节点是某条横跨切割(V-Q,Q)的轻量级边的一个端点。接着将节点u从队列Q中删除,并将其加入到集合V-Q中,也就是将边(u,u.π)加入到集合A中。算法第8~11行的for循环将每个与u邻接但却不在树中的节点v的key和π属性进行更新。

Prim算法的运行时间取决于最小优先队列Q的实现方式。如果将Q实现为一个二叉最小优先队列,我们可以使用BUILD-MIN-HEAP来执行算法的第1~5行,时间成本为O(V).while循环中的语句一共要执行|V|次,由于每个EXTRACT-MIN操作需要的时间成本为O(lgV),EXTRACT-MIN操作的总时间为O(VlgV)。由于所有邻接链表的长度之和为2|E|,算法第8~11行的for循环的总执行次数为O(E)。在for循环里面,我们可以在常数时间内完成对一个节点是否属于队列Q的判断,方法就是对每个节点维护一个标志位来指明该节点是否属于Q,并在将节点从Q中删除的时候对该标志位进行更新。算法第11行的赋值操作涉及一个隐含的DECREASE-KEY操作,该操作在二叉最小堆上执行的时间成本为O(lgV)。因此,Prim算法的总时间代价为O(VlgV+ElgV)=O(ElgV)。

下面是Prim算法的c++代码,实现了求出上图所描述的图的最小生成树算法(用邻接链表来表示的图):

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
const int inf = 999999;
const int weightsize = 255;
int weight[weightsize][weightsize];
class Vertex{
public:
    vector<Vertex*> adj;
    bool out;
    int key;
    char name;
    Vertex* parent;
    Vertex(char name) :name(name){
        key = inf;
        out = false;
    }
    void addEdge(Vertex* v, int w=inf) {
        adj.push_back(v);
        weight[name][v->name] = w;
    }
    const bool operator ==(const Vertex* v) {
        return v->name == name;
    }
};
struct cmp{
    bool operator() (const Vertex* a, const Vertex* b) {
        return a->key > b->key;
    }
};

vector<Vertex*> vertexes;
/*
*初始化图
*/
void initGraph() {
    memset(weight, 0, sizeof(weight));
    Vertex* a = new Vertex('a');Vertex* b = new Vertex('b');Vertex* c = new Vertex('c');
    Vertex* d = new Vertex('d');Vertex* e = new Vertex('e');Vertex* f = new Vertex('f');
    Vertex* g = new Vertex('g');Vertex* h = new Vertex('h');Vertex* i = new Vertex('i');
    vertexes.push_back(a); vertexes.push_back(b); vertexes.push_back(c);
    vertexes.push_back(d); vertexes.push_back(e); vertexes.push_back(f);
    vertexes.push_back(g); vertexes.push_back(h); vertexes.push_back(i);
    a->addEdge(b,4); a->addEdge(h,8);
    b->addEdge(a,4); b->addEdge(h,11); b->addEdge(c,8);
    c->addEdge(b,8); c->addEdge(i,2); c->addEdge(f,4); c->addEdge(d,7);
    d->addEdge(c,7); d->addEdge(f,14); d->addEdge(e,9);
    e->addEdge(d,9); e->addEdge(f,10);
    f->addEdge(c,4); f->addEdge(d,14); f->addEdge(e,10); f->addEdge(g,2);
    g->addEdge(h,1); g->addEdge(i,6); g->addEdge(f,2);
    h->addEdge(a,8); h->addEdge(i,7); h->addEdge(g,1);
    i->addEdge(h,7); i->addEdge(g,6); i->addEdge(c,2);
    //将根节点的key值置为0
    a->key = 0;
}
void addToQueue(priority_queue<Vertex*, vector<Vertex*>, cmp> vQueue) {
    
}
void MSTPrim() {
    for (int k = 0; k < 9; k++) {
        priority_queue<Vertex*, vector<Vertex*>, cmp> vQueue;
        for (int i = 0; i < 9; i++) {
            if (!vertexes[i]->out)
                vQueue.push(vertexes[i]);
        }
        Vertex* v = vQueue.top();
        vQueue.pop();
        cout << v->name<<"-"<<v->key << endl;
        v->out = true;
        int j = 0;
        for (vector<Vertex*>::iterator iter = v->adj.begin(); iter != v->adj.end(); iter++,j++) {
            if (!(*iter)->out) {
                if ((*iter)->key > weight[v->name][(*iter)->name]) {
                    (*iter)->key = weight[v->name][(*iter)->name];
                    //(*iter)->parent = v;
                }
            }
        }
    }
}

int main() {
    initGraph();
    MSTPrim();
    return 0;
}

运行结果: