一,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;
}
更多推荐
算法,导论,Prim
发布评论