数据结构 课件 第七章 图2.ppt

典型用途 3如此进行下去每次往生成树里并入一个顶点和一条边直到n-1次后把所有n 个顶点都并入生成树G的顶点集U中此时U=VT中包含有n-1条边 这样 G就是最后得到的最小生成树 普里姆算法中每次选取的边两端总是一个已连通顶点在U集合内和一个未连通顶点在U集合外故这个边选取后一定能将未连通顶点连通而又保证不会形成环路 如图可以得到不止一个拓扑排序 C1-C2-C3-C4-C5-C7-C9-C10-