生成树算法程详解
针生成树算法知识点相部分课相关参考书算法程讲解特详文针信息系统项目理师考试生成树算法程进行逐步解析更加促进知识点理解掌握
1概念
连通带权图生成树中权值棵生成树（包含图中顶点树）称作生成树（权值：数结构领域权值树者图中两结点路径值值表明种代价结点达外结点路径长度花费时间付出费等）
2带权连通图生成树算法
（1）普里姆（Prim）算法
设已知G(VE)带权连通图U构造生成树程中已考虑生成树顶点集合顶点V｛012…n1｝ T构造生成树程中已考虑生成树边集合Eij顶点ij间边i∈Uj∈VU
初始时U包含1出发顶点iT空出发顶点i开始查找连接该顶点边中果边Eij具权值生成树应包含Eijj加U中Eij加T中然ij开始查找边Eij外连接ij代价边次重复述程T产生回路直UV止时T求代价生成树边集合
普里姆算法时间复杂度O（n²）适合稠密图（边数远远顶点数图）
（2）克鲁斯卡尔（Kruskal）算法
设T(Vψ)初始状态n顶点边森林顶点V｛012…n1｝Eij顶点ij间边
初始时T包含n顶点边代价递增序次选择Eij加入T重复述程T产生回路直顶点均连接止时T生成树
克鲁斯卡尔算法时间复杂度O(elog2e）较适合稀疏图（边数远远顶点数图）
面分运两种算法例题进行解析
例：图某区通信线路图假设中标注数字代表通信线路长度（单位：千米）现求少架设长线路保持6城市通信联通？
普里姆算法：
1选择A出发顶点查找连接顶点A顶点中权值边顶点A分顶点BCEF连接AB300AC400AE300AF200AF选择AF加入时包含顶点AF图：
2查找连接顶点AF顶点中权值边A连接顶点BCEF连接顶点EAB300AC400AE300FE400ABAE300选择ABAE加入（里选择AE加入）时已包含顶点AFE图：
3选择AE加入查找顶点AFE连接顶点中权值边剩顶点BCD未加入ABC连接EBCD连接时AB300AC400EB300EC400ED200ED选择ED加入时已包含顶点AFED图：
4查找顶点AFED连接顶点中权值边剩顶点BC未加入ABC连接EBC连接DC连接AB300AC400EB300EC400DC300ABEBDC300选择中条加入（里选择EB加入）时已包含顶点AFEDB图：
5查找顶点AFEDB顶点中权值边剩顶点C未加入C分ABDE连接CA400CB400CE400CD300CD选择CD加入图中顶点已加入完毕
生成树已形成图：
权值AF+AE+ED+EB+CD
AF+AB+AE+ED+CD
AF+AB+EB+ED+CD
1300
见图生成树棵述第2步开始选择AB加入选择EB（时掉AE）加入生成树图：
述第2步开始先选择AE加入选择AB（时掉EB）加入生成树图：
克鲁斯卡尔算法：
1顶点间边代价递增序边进行排列AFED200＜ABAEEBCD300＜ACBCFECE400掉图边保留顶点图：
2选择AF加入图：
3选择ED加入图：
4选择AB加入图：
5选择CD加入图：
6选择EB加入时生成树形成图：
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
针生成树算法知识点相部分课相关参考书算法程讲解特详文针信息系统项目理师考试生成树算法程进行逐步解析更加促进知识点理解掌握
1概念
连通带权图生成树中权值棵生成树（包含图中顶点树）称作生成树（权值：数结构领域权值树者图中两结点路径值值表明种代价结点达外结点路径长度花费时间付出费等）
2带权连通图生成树算法
（1）普里姆（Prim）算法
设已知G(VE)带权连通图U构造生成树程中已考虑生成树顶点集合顶点V｛012…n1｝ T构造生成树程中已考虑生成树边集合Eij顶点ij间边i∈Uj∈VU
初始时U包含1出发顶点iT空出发顶点i开始查找连接该顶点边中果边Eij具权值生成树应包含Eijj加U中Eij加T中然ij开始查找边Eij外连接ij代价边次重复述程T产生回路直UV止时T求代价生成树边集合
普里姆算法时间复杂度O（n²）适合稠密图（边数远远顶点数图）
（2）克鲁斯卡尔（Kruskal）算法
设T(Vψ)初始状态n顶点边森林顶点V｛012…n1｝Eij顶点ij间边
初始时T包含n顶点边代价递增序次选择Eij加入T重复述程T产生回路直顶点均连接止时T生成树
克鲁斯卡尔算法时间复杂度O(elog2e）较适合稀疏图（边数远远顶点数图）
面分运两种算法例题进行解析
例：图某区通信线路图假设中标注数字代表通信线路长度（单位：千米）现求少架设长线路保持6城市通信联通？
普里姆算法：
1选择A出发顶点查找连接顶点A顶点中权值边顶点A分顶点BCEF连接AB300AC400AE300AF200AF选择AF加入时包含顶点AF图：
2查找连接顶点AF顶点中权值边A连接顶点BCEF连接顶点EAB300AC400AE300FE400ABAE300选择ABAE加入（里选择AE加入）时已包含顶点AFE图：
3选择AE加入查找顶点AFE连接顶点中权值边剩顶点BCD未加入ABC连接EBCD连接时AB300AC400EB300EC400ED200ED选择ED加入时已包含顶点AFED图：
4查找顶点AFED连接顶点中权值边剩顶点BC未加入ABC连接EBC连接DC连接AB300AC400EB300EC400DC300ABEBDC300选择中条加入（里选择EB加入）时已包含顶点AFEDB图：
5查找顶点AFEDB顶点中权值边剩顶点C未加入C分ABDE连接CA400CB400CE400CD300CD选择CD加入图中顶点已加入完毕
生成树已形成图：
权值AF+AE+ED+EB+CD
AF+AB+AE+ED+CD
AF+AB+EB+ED+CD
1300
见图生成树棵述第2步开始选择AB加入选择EB（时掉AE）加入生成树图：
述第2步开始先选择AE加入选择AB（时掉EB）加入生成树图：
克鲁斯卡尔算法：
1顶点间边代价递增序边进行排列AFED200＜ABAEEBCD300＜ACBCFECE400掉图边保留顶点图：
2选择AF加入图：
3选择ED加入图：
4选择AB加入图：
5选择CD加入图：
6选择EB加入时生成树形成图：
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
