第十三章 最小生成树.ppt

数据结构
第十三章最小生成树
第13章最小生成树
生成树与最小生成树
Kruskal算法
Prim算法
算法的正确性
生成树
生成树是无向连通图的极小连通子图。包含图的所有n 个结点,但只含图的n-1 条边。在生成树中添加一条边之后,必定会形成回路或环。
最小生成树
定义:加权无向图的所有生成树中边的权值(代价)之和最小的树。
Kruscal 算法
基本思想:考虑图中权值最小的边。如果加入这条边不会导致回路,则加入;否则考虑下一条边,直到包含了所有的顶点
实现:
初始时,设置生成树为(V,Φ),如果V有n个顶点,则初始的生成树为具有n个连通分量的树。
按权值的大小逐个考虑所有的边,如果该边的加入能连接两个连通分量,则加入。当生成树只有一个连通分量时,算法结束。
算法难点及解决方案
如何从所有边中选择代价最小的边:用一个优先级队列来实现。将所有的边放入一个优先级队列,边的优先级就是它的权值。权值越小,优先级越高。
如何判断加入一条边后会不会形成回路:用并查集来实现。将一个连通分量表示为并查集中的一个子集,检查一条边加入后会不会形成回路可以通过对边的两个端点分别执行Find操作。如果两个Find的结果相同,则表示两个端点已连通,加入这条边会形成回路,否则将这条边加入生成树。添加边的操作就是一个Union操作,将两个端点所属的子集归并起来,表示其中的所有顶点都已连通。
定义优先级队列中的元素类型
struct edge {
int beg, end;
TypeOfEdge w;
bool operator<(const edge &rp) const
{return w < ;}
};
kruskal算法的实现
template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::kruskal( ) const
{ int epted = 0,u, v;
edgeNode *p;
edge e;
DisjointSet ds( Vers );
priorityQueue<edge> pq;

//生成优先级队列
for (int i = 0; i< Vers; ++i) {
for (p = verList[i].head; p != NULL; p = p->next)
if (i < p->end) { = i;
= p->end;
= p->weight;
(e); }
}