知识卡片
生成树最小化总权而非边数
连通无向图的生成树包含全部V个顶点、无环且有V−1条边。所有生成树边数相同,最小生成树进一步使边权总和最小;钉子细绳游戏如果只要求细绳数量最少,还没有表达加权目标。
图不连通时没有覆盖全部顶点的单棵生成树,可按连通分量讨论生成森林。边权可以为负,不像Dijkstra那样要求非负;有相同权值时最优树也可能不唯一。
最小总边权不保证从某个根到每一点的距离都最小,更不满足每点访问一次并回原点的回路目标。
305说明不同起点或平权选择可能得到不同最小生成树,但它们的总权必须相同;不连通图无覆盖全图的单棵生成树。概念上可求起点分量的树或各分量森林,本书mst源码对不可达点仍有旧候选复用问题,不能无条件声称它正确返回森林。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 生成树最小化总权而非边数
- · 问与答
原书出处 · 2 处
- · 查看原书依据
最小代价连接V中所有顶点所用边E的最小集合。集合T中的边能形成一棵树,这是因为每个顶点(除了第一个顶点,即根结点)都能向上找到它的一个父结点。
- · 查看原书依据
非连接图计算最小生成树,将会出现什么问题? 答:回想一下,一个连接图就是图中的每个顶点都能够通过一些路径抵达。如果试图为一个非连接图计算最小生成树,那么只能得到一个从起始点开始的所有连接点的最小生成树。
参考来源
- 位置:《算法精解:C语言描述》第16章《最小生成树的描述》(spine1409;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1375.html;u292-ch16-003)。
- 结论依据:292全文连接/最小代价定义实读,树的V−1性质与前章已读树定义对应;条件明确补全连通性。
- 原始内容:最小代价连接V中所有顶点所用边E的最小集合。集合T中的边能形成一棵树,这是因为每个顶点(除了第一个顶点,即根结点)都能向上找到它的一个父结点。
- 位置:《算法精解:C语言描述》第16章《问与答》(spine1419;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1385.html;u305-ch16-003)。
- 结论依据:305说明不同起点或平权选择可能得到不同最小生成树,但它们的总权必须相同;不连通图无覆盖全图的单棵生成树。概念上可求起点分量的树或各分量森林,本书mst源码对不可达点仍有旧候选复用问题,不能无条件声称它正确返回森林。
- 原始内容:非连接图计算最小生成树,将会出现什么问题? 答:回想一下,一个连接图就是图中的每个顶点都能够通过一些路径抵达。如果试图为一个非连接图计算最小生成树,那么只能得到一个从起始点开始的所有连接点的最小生成树。