0%
10.3
10.6
- Prim
- 数组实现优先队列：
- 堆实现优先队列-稠密图:
- 堆实现优先队列-稀疏图：
- Kruskal
- Prim适合稠密图，Kruskal适合稀疏图
10.10
- 第一问：不用更新
- 第二问：在原最小生成树上添加e形成一个环，删除环上最大边
- 第三问：不用更新
- 第四问：在原最小生成树上删除e形成两个连通分支。添加连接两个连通分支的权值最小的边
10.13
- 在Kruskal算法基础上改进
- 初始化：S中的边全部加入MST，并对S中关联的点依次加入并查集
- 算法思想：在E-S中依次挑选权重最小且不会产生环的边加入MST
10.14
- 记e两端点是uv，删除所有权值大于等于e的边。
- 从u出发搜索v
- 如果能搜到，说明e是某环上唯一的最重边，不可能在最小生成树上
- 如果搜不到，反设e不在任意最小生成树上，则任意最小生成树加上e都会形成圈，且e是圈上唯一的最重边（否则e和同重的边替换即可得到一个最小生成树）。因此u会搜到v，矛盾。因此e在某个最小生成树上。
10.15
- 错，反例是割边
- 对，环上的唯一最重边不可能属于任何最小生成树。证明用反证法，即假设属于某个MST，则可以把环上那个不在MST的边和最重边替换，还是连通的，且权值更小了。
- 对，可以分为割边和非割边两种情况讨论
- 对，可以分为割边和非割边两种情况讨论
- 错，例如正四面体的平面图，一个三角面的三条边权很大，其他的三条边权很小。
- 错，例如三角形，边权为2，2，3。
- 正确，不同于Dijkstra算法
10.16
- 两个图有着相同的边权大小序
- 因此例如调用Prim算法，结果一样
10.17
- 假设G的MST和H的交中的边e不在T的一个MST上
- 添加e使得H中产生圈
- e是圈上最重的边
- 设e的两端是u、v。在G的MST删除e后，u和v在G的MST的两个不相交点集中。
- 这两个点集和H交后还是两个不相交点集，又因为H的最小生成树上没有e，但包含u和v，因此必然存在一个边e'，连接着这两个不相交点集。
- 根据第三行，e'不比e重。若e'比e轻，则把e替换为e'能得到更小的G的MST。所以e和e'同重
- 把T的MST的e'换成e，得到了T的另一个MST，此时e在该MST上。
- 即G的MST和H的交中的边e必然在T的某个MST上
10.21
- 反例：四边形，按上右下左顺序，边权为1，2，1，2
- 竖直切一刀把其分为左右两个点集，显然算法不正确。
10.23
- 第一问：生成最小生成树铺设管道，在最小造价的节点打井
- 第二问
- 想象有一个水源节点，打井的代价可以开作是从水源节点运水的管道代价。
- 那么问题可以这样转化，新加一个水源节点，连向每个房子。管道造价为原图的打井代价。对新图生成MST。MST上原图有的边对应管道代价，原图没的边对应打井代价。
10.25
- 例如ABC三个点，A为起点，B为终点，AB权重为2，BC权重为-2，AC权重为3
- dijkstra算法算出最短路径是2，但其实是1
10.27
- 设负边为，权重为
- 删除，以、、为起点，调用三次Dijkstra算法，结果为。
- 对于到的最短路径，
10.31
- 最小生成树不变，因为序关系不变
- 最短路径可能变化，例如四条边的权重为1、1、1、4。增加1后，变为2、2、2、5,显然改变了最短路径。
10.33
- 对Dijkstra算法计算路径权值进行修改即可
- 源点：
- 其他点: ，其中，且在最短路径树中
10.34
- 仍然正确
- dijkstra算法在扩充最短路径树时选择的是fringe中的局部最优解，这个解也是全局最优的，因为fringe以外的边必然都是正的，“fringe的最优解”一定比“fring的次优解加上一些正边”要优（路径更短）。
10.36
- 在Dijkstra算法中维护best[]即可
- 初始化，best[s]=1
- 在fringe中求min时，如果发现多个最短路径（u1,u2,uk和v相连）指向了fringe中的同一个点v，则best[v]=best[u1]+...+best[uk]
10.38
- 第一问：把权值大于L的边删去，从s出发dfs搜t即可，线性复杂度。
- 第二问：
- 给每个点定义变量capacity：从s到该点的所有路径上最大边权值的最小值
- 初始化：s的capacity为0,其他点的capacity为无穷。
- 每次选择与最短路径树相邻的且capcity值最小的点，加入最小路径树。第一步把s加入。
- 每次向最短路径树增加一个点u后，更新其邻居v的capacity
- v.capacity=min{v.capacity, max{u.capacity,uv.weight}}
- 返回第三行继续选点加入最小路径树。
- 最终t.capacity就是从s到t的最小油箱容量。
- 复杂度同Dijkstra,O((m+n)log n)
微信支付