关于图ADT的一些算法——最小生成树算法(普利姆/Prim算法)

时间:2022-09-12 11:41:15

关于图ADT的一些算法——最小生成树算法(普利姆/Prim算法)

 

连通的带权无向图

问题:用最小的权值连通所有的点,即从上图删去一些线,使留下的线的权值的总和最小且每个点都连通。

 

第一步:先标记a,待选的有a->i,a->f,a->b,选择最小的a->i;

第二步:添加i,与(a,i)中某个点相连的边做备选,有:a->b,a->f,选择最小的a->f;

第三步:添加f,与(a,i,f)中某个点相连的边做备选,有a->b,f->g,选择最小的f->g;

第四步:添加g,与(a,i,f,g)中某个点相连的边做备选,有a->b,g->e,g->d,选择最小的g->d;

第五步:添加d,与(a,i,f,g,d)中某个点相连的边做备选,有a->b,g->e,d->c,d->h,选择最小的d->h;

第六步:添加h,与(a,i,f,g,d,h)中某个点相连的边做备选,有a->b,g->e,d->c,选择最小的d->c;

第七步:添加c,与(a,i,f,g,d,h,c)中某个点相连的边做备选,有a->b,g->e,c->e,c->b,选择最小的c->e;

第八步:添加e,备选的有a->b,e->b,c->b,选择最小的a->b;

第九步:添加b,所有点都已包括,算法结束。

 

 

参考文献:《Data Abstraction and Problem Solving with C++:Walls and Mirrors,3rd Edition》 Frank M.Carrano &Janet J.Prichard著 《数据结构与C++高级教程》田玉敏译 清华大学出版社