Kruskal 算法? Prim 算法?算法的正确性 Kruscal Kruscal 算法算法?基本思想:考虑图中权值最小的边。如果加入这条边不会导致回路,则加入;否则考虑下一条边,直到包含了所有的顶点?实现: ?初始时,设置生成树为( V,Φ),如果 V有n 个顶点,则初始的生成树为具有 n个连通分量的树。?按权值的大小逐个考虑所有的边,如果该边的加入能连接两个连通分量,则加入。当生成树只有一个连通分量时,算法结束。 124356 616 55563 42 1、初始连通分量: {1},{2},{3},{4},{5},{6} 2、反复执行添加、放弃动作。边动作连通分量(1,3) 添加{1,3},{4},{5},{6},{2} (4,6) 添加{1,3},{4, 6},{2},{5} (2,5) 添加{1,3},{4, 6},{2,5} (3,6) 添加{1,3,4, 6},{2,5} (1,4) 放弃因构成回路(3,4) 放弃因构成回路(2,3) 添加{1,3,4,5,6,2} 最小代价生成树 124356 153 42算法难点及解决方案算法难点及解决方案?如何从所有边中选择代价最小的边: ?用一个优先级队列来实现。将所有的边放入一个优先级队列,边的优先级就是它的权值。权值越小,优先级越高。?如何判断加入一条边后会不会形成回路: ?用并查集来实现。将一个连通分量表示为并查集中的一个子集,检查一条边加入后会不会形成回路可以通过对边的两个端点分别执行 Find 操作。如果两个 Find 的结果相同,则表示两个端点已连通,加入这条边会形成回路, 否则将这条边加入生成树。添加边的操作就是一个 Union 操作,将两个端点所属的子集归并起来,表示其中的所有顶点都已连通。
全文预览
