数据结构与算法6.ppt

6.4.1 最小生成树 6.4.2 最短路径 6.4 应用实例 1. Prim算法 对于有n个顶点的图G=(V, E)Prim算法从空树T开始按照以下规则将n个顶点和n-1条边依次添加到树中形成最小生成树 从某一顶点v0'开始将该顶点作为树的根结点加入到T中使得T中的数据元素集合D={v0'}数据元素关系集合R={} 对于一个顶点在集合D中另一个顶点在集合V-D中的那些边找出权最小的一条边将该边在