例:在图(a)中给出了一个连通图,求此图的 生成树。 5
例 ：在图(a)中给出了一个连通图, 求此图的 生成树。 (a) 8 7 7 6 5 5 4 4 4
普里姆(Prim)算法 普里姆算法的基本思想 从连通网络N=1E中的某一顶点mA 发,选择与它关联的具有最小权值的边(unν), 将其顶点加入到生成测的顶点集合U中。以后每 一步从一个顶点在U,而另一个顶点不在U中 的各条边中选择权值最小的边,v),把它的顶点 加入到集合U中。如此继续下去,直到网络中的 所有顶点都加入到生成树项点集合U中为止
普里姆(Prim)算法 普里姆算法的基本思想： 从连通网络 N = { V, E }中的某一顶点 u0出 发，选择与它关联的具有最小权值的边(u0 , v)， 将其顶点加入到生成树的顶点集合U中。以后每 一步从一个顶点在U中，而另一个顶点不在U中 的各条边中选择权值最小的边(u, v),把它的顶点 加入到集合U中。如此继续下去，直到网络中的 所有顶点都加入到生成树顶点集合U中为止
用普里姆Pim算法构造最小生成树的 2 4 4 4 5 从节点①开始,选最小权值的边1,节点(①,③)入U 从U中选最小权值边4,且对应节点不在U中,⑥入U 从U中选最小权值边2,且对应节点不在U中,④入U 从U中选最小权值边5,且对应节点不在U中,②入U 从U中选最小权值边3,且对应节点不在U中,⑤入U
用普里姆(Prim)算法构造最小生成树的过程 1 2 3 4 5 6 6 5 5 1 7 3 2 5 4 6 1 2 3 4 5 6 5 1 3 2 4 •从节点①开始，选最小权值的边1，节点（①，③）入U; •从U中选最小权值边4，且对应节点不在U中，⑥入U; •从U中选最小权值边2，且对应节点不在U中，④入U; •从U中选最小权值边5，且对应节点不在U中，②入U; •从U中选最小权值边3，且对应节点不在U中，⑤入U;
根树及其应用 个有向图,略去方向后是树,则称这个 有向图为有向树。如果一棵有向树恰有一个结 点入度为0,其余所有结点入度为1,此有向树 称为根树。在根树中,入度为0的结点称为树根, 出度为0的结点称为树叶,出度不为0的结点称 为分枝点或内点。从此定义可以看出,在根树 中,除了树叶都是分枝点或内点外,树根也是 分枝点
根树及其应用 一个有向图，略去方向后是树，则称这个 有向图为有向树。如果一棵有向树恰有一个结 点入度为0，其余所有结点入度为1，此有向树 称为根树。在根树中，入度为0的结点称为树根， 出度为0的结点称为树叶，出度不为0的结点称 为分枝点或内点。从此定义可以看出，在根树 中，除了树叶都是分枝点或内点外，树根也是 分枝点
例:下图(1)为一棵根树。V为树根,v12,v3vv2 叶,v2,v为内点,v,V2,v为均为分支点由于在根树 有向边的方向均一致,故可省掉其方向,如图(2) (2)
(1) (2) v0 v1 v2 v3 v4 v5 v6 v7 v0 v1 v2 v3 v4 v5 v6 v7 例: 下图(1)为一棵根树。V0为树根, v1 ,v4 , v3 , v6 , v7为树 叶, v2 , v5为内点, v0 , v2 , v5为均为分支点, 由于在根树中 有向边的方向均一致, 故可省掉其方向, 如图(2)