前提
【1】网的最小生成树&＃xff0c;涉及到生成树了那么就会有最小的权值在里面了
【2】对于一个图来说生成树是由多个的&＃xff0c;并不是唯一的
【3】&＃xff1a;广度优先算法的遍历是可以得到生成树的&＃xff0c;深度优先算法也是可以得到生成树的
任意的一个联通网&＃xff0c;如果我们想构建最小生成树&＃xff0c;假设我们把所有节点分成两个集合&＃xff0c;我们知道&＃xff0c;建成的最小生成树的节点之间一定是联通的
思路&＃xff1a;
以某一个点出发来逐渐的扩大&＃xff0c;扩大的思路&＃xff0c;就是两个集合中间最小的一条边一定是最小生成树的一条边
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有