算法导论 23.2 Prim算法

一，Prim算法的思想

        Prim算法和Kruskal算法一样对安全边的选择规则作出了细化，Prim每一步在连接集合A和A之外的结点的所有边中选择一条轻量边的结点信息加入A中，直到A中的结点覆盖所有结点。

二，Prim算法介绍

        准备阶段：一张赋值无向连通图，集合A用于存放最小生成树的各结点信息，每个结点有两个属性：key表示该结点的所有前驱结点到它的最短距离，π表示到它距离最短的前驱结点，我们还需要一个初始为所有结点的队列Q

        算法过程：每次从队列Q中提取key值最小的结点加入集合A，遍历他的邻结点，如果邻结点在队列Q中且w(u,v)<v.key，那么更新结点的信息，直到所有结点从队列Q中取出，最后根据根结点及其他结点的π值，形成最小生成树

三，Prim算法伪代码

MST_PRIM(G,w,r)

1. for each u∈G.V

2.     u.key=∞

3.     u.π=NULL

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)

第1-3行中，将每个结点的key和π进行初始化；第4-5行中，根结点的key初始化为0，队列Q初始化为所有存放所有结点的集合；第6-11行中，如果队列中还有结点，那么我们用EXTRACT_MIN从队列中找到key值最小的结点u（在第一次循环中，提取的就是根结点r），然后将对u的邻结点v进行遍历，如果v是队列Q中的结点并且u到v的权重比v的key值小，那么我们需要更新v的信息，将v的π设为u并且让v的key值等于u到v的权重

以书上的例子为例，图a中，我们将结点a作为根结点；图b中，第一轮中，队列包含了所有结点，我们选出key值最小的，也就是根结点a，他的邻结点有b和h，b和h都还在队列里且w(a,b)<b.key，w(a,h)<h.key，所以我们更新b、h的key和π值为4和a，8和a，这轮结束后，队列Q中还剩余除了a的其他结点，b和h都已经更新完毕；图b中，我们继续提取队列中key值最小结点，即b，找到b的两个邻结点c和h，c和h均在队列Q中，由于w(b,h)=11>h.key=8，所以不更新h，而w(b,c)=8<c.key=∞，所以更新c的key和π值为8和b，这轮结束后，队列Q中已经去掉了a和b两个结点，a、b、c、h也已更新完毕；在图c中，提取c或h（这里我们提取了c），他的邻结点d、i、f均进行更新；在图d中，提取i，他的邻结点h、g也都需要更新；图e-i中，依据上述规律每次选择队列Q中key值最小的并对其邻结点进行更新，最后所有结点都移出队列Q，且所有结点都有key和π值，那么我们有了根结点a以及每个结点的前驱结点，一张完整的最小生成树就形成了。

四，Prim算法的复杂度

时间复杂度：初始化的复杂度为O(V)，EXTRACT_MIN操作的时间为O(lgV)，while循环V次，因此EXTRACT_MIN的总时间为O(VlgV)，for循环执行的时间为O(E)，第11行的赋值操作隐含了一个时间为O(lgV)的操作，因此Prime的总时间为O(VlgV+ElgV)=O(ElgV)

五，Prim算法的代码

Tree * PRIM_ALGO(Graph * graph, Node * startNode)
{Tree *T=new Tree();//创建最小生成树startNode->setKey(0);vector<Node *> Q= graph->getNodeList();//Q为未被选出的结点集合while(Q.size()!=0){Node *u = EXTRACT_MIN(Q, startNode);//选出最小边末结点ufor (int i = 0; i<graph->getEdgeList().size(); i++){if (graph->getEdgeList()[i]->getStartNode() == u->getPrevNode() && graph->getEdgeList()[i]->getEndNode() == u){T->pushEdge(graph->getEdgeList()[i]);}}for (int j = 0; j < u->getAdjNodeList().size(); j++){Node *v = u->getAdjNodeList()[j];if (ifnodebelongstoq(v, Q) == true && getnodesweight(graph, u, v)<v->getKey()){v->setPrevNode(u);v->setKey(getnodesweight(graph, u, v));}}}return T;
}

Node * EXTRACT_MIN(vector<Node *> &Q, Node * startNode)
{Node *minnode=NULL;//最小邻边的邻接点int weight = 99999;//最小邻边的值int minnodenum = 0;for (int i = 0; i<Q.size(); i++)//选出最小边及末结点{if (Q[i]->getKey()<weight){weight = Q[i]->getKey();minnode = Q[i];minnodenum = i;}}for (int r = minnodenum; r<Q.size() - 1; r++)//从要弹出的结点开始集体向前移一格，然后弹出最后一个{Q[r] = Q[r + 1];}Q.pop_back();return minnode;
}