维基百科
生成树, 此條目需要补充更多来源, 2020年3月8日, 请协助補充多方面可靠来源以改善这篇条目, 无法查证的内容可能會因為异议提出而被移除, 致使用者, 请搜索一下条目的标题, 来源搜索, 网页, 新闻, 书籍, 学术, 图像, 以检查网络上是否存在该主题的更多可靠来源, 判定指引, 在图论中, 無向圖, 英語, spanning, tree, 是具有, 的全部顶点, 但边数最少的連通子圖, 格子圖, 英语, grid, graph, 的生成樹, 圖中的藍色粗線, 以v, displaystyle, 表示顶点, . 此條目需要补充更多来源 2020年3月8日 请协助補充多方面可靠来源以改善这篇条目 无法查证的内容可能會因為异议提出而被移除 致使用者 请搜索一下条目的标题 来源搜索 生成树 网页 新闻 书籍 学术 图像 以检查网络上是否存在该主题的更多可靠来源 判定指引 在图论中 無向圖 G 的生成树 英語 Spanning Tree 是具有 G 的全部顶点 但边数最少的連通子圖 1 格子圖 英语 grid graph 的生成樹 圖中的藍色粗線 以V displaystyle V 表示顶点 E displaystyle E 表示边 若图 G V G E G displaystyle G V G E G 和树T V T E T displaystyle T V T E T 有E T E G displaystyle E T subset E G 和V G V T displaystyle V G V T 那么T displaystyle T 是G displaystyle G 的生成树 一个图的生成树可能有多个 最小生成树 编辑带权图的生成树中 总权重最小的称为最小生成树 求取最小生成树的算法 克鲁斯克尔演算法 一种贪心算法 复杂度是 O E log E displaystyle O E log E nbsp 普林姆算法 另一种贪心算法 用二叉堆优化时复杂度是 O E V log V displaystyle O E V log V nbsp 当边数远远大于点数 可近似认为是 O E displaystyle O E nbsp nbsp 这是一篇電腦科學小作品 你可以通过编辑或修订扩充其内容 查论编 第23章 算法导论 第三版 362 ISBN 978 7 111 40701 0 取自 https zh wikipedia org w index php title 生成树 amp oldid 72309322, 维基百科，wiki，书籍，书籍，图书馆，