最小生成树（贪心算法）概念一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。连通图有多种连接方式，而其中最小的连通图，就是最小生成树连通图分为：无向、有向无向连通图：所以顶点相连，但各个边都没有方向有向连通图：边有方向1.普利姆算法（Prim）-----最近顶点策略策略：选择图中的一个顶点作为起始点，每一步贪心选择不在当前生成树中的最近顶点加入生成树中，直到所有顶点都加入到树中。算法如下：（1）、假如G为无向连通带权图，每两个相邻节点构成一个带权边，其值设为：权值。即:(所有每相邻的两个节点都有各自的权值，只是权值大小不同)（2）、设集

一、概念最小生成树(MinimumCostSpanningTree)，简称MST。1)给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,就叫最小生成树2)N个顶点，一定有N-1条边3)包含全部顶点4)N-1条边都在图中（好像不能形成闭合回路）求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法二、普里姆算法Prim1)普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图2)普利姆的算法思路如下:        (1)设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点

一、概念最小生成树(MinimumCostSpanningTree)，简称MST。1)给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,就叫最小生成树2)N个顶点，一定有N-1条边3)包含全部顶点4)N-1条边都在图中（好像不能形成闭合回路）求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法二、普里姆算法Prim1)普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图2)普利姆的算法思路如下:        (1)设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点