85最小生成树 最小生成树的基本概念 1、生成树:是一个极小连通子图,它含有图中全部项点,但 只有n-1条边。 2、最小生成树:如果无向连通图是一个带权图,那么它的所 有生成树中必有一棵边的权值总和为最小的生成树, 称这棵生成树为最小代价生成树,简称最小生成树
6 8.5 最小生成树 1、生成树：是一个极小连通子图，它含有图中全部顶点，但 只有n-1条边。 2、最小生成树：如果无向连通图是一个带权图，那么它的所 有生成树中必有一棵边的权值总和为最小的生成树， 称这棵生成树为最小代价生成树，简称最小生成树。 一、最小生成树的基本概念
3求最小生成树 目标:在网络的多个生成树中,寻找一个各边权值之和 最小的生成树。 即有权图 首先明确: 使用不同的遍历图的方法,可以得到不同的生成树;从 不同的顶点出发,也可能得到不同的生成树。 ·按照生成树的定义,n个顶点的连通网络的生成树肯定 有个顶点和仅仅m-1条边。 构造最小生成树的准则 ◆必须只使用该网络中的边来构造最小生成树 ◆必须使用且仅使用m-1条边来联结网络中的m个顶点 ◆不能使用产生回路的边
7 3.求最小生成树 首先明确： • 使用不同的遍历图的方法，可以得到不同的生成树；从 不同的顶点出发，也可能得到不同的生成树。 • 按照生成树的定义，n 个顶点的连通网络的生成树肯定 有 n 个顶点和仅仅n-1 条边。 即有权图 构造最小生成树的准则 ❖ 必须只使用该网络中的边来构造最小生成树； ❖ 必须使用且仅使用n-1条边来联结网络中的n个顶点； ❖ 不能使用产生回路的边。 目标：在网络的多个生成树中，寻找一个各边权值之和 最小的生成树