Homework9Homework 9Homework9

1. 给定一幅加权图GGG 以及它的最小生成树。从GGG中删去一条边且GGG 仍然是连通的，如何在与EEE成正比的时间内找到新图的最小生成树。
      删去一条边有两种情况：
      1. 如果删去的边不属于最小生成树T0T_0T0​，那么对图的最小生成树无影响，新图的最小生成树仍是T0T_0T0​
      2. 如果删去的边属于最小生成树T0T_0T0​，那么删去一条边e0e_0e0​后相当于T0T_0T0​断开，得到最小生成树的两棵子树(T1、T2)∈T0(T_1、T_2)∈T_0(T1​、T2​)∈T0​，那么只需要去图GGG中找到一个边e1∉T0e_1∉T_0e1​∈/​T0​，首先找到能够将这两个子树连接起来的所有边，即e1∈{(u,v)∣u∈T1&v∈T2}e_1∈\{(u,v)|u∈T_1\&v∈T_2\}e1​∈{(u,v)∣u∈T1​&v∈T2​}，再在这些边中找一个权值最小的边，即min(e1.weight)min(e_1.weight)min(e1​.weight)，则{e1}+T0−{e0}=T1\{e_1\}+T_0-\{e_0\}=T_1{e1​}+T0​−{e0​}=T1​就是新图的最小生成树，最坏情况下需要遍历图中剩余所有的边，所以时间为O(E)O(E)O(E)。

2. 给定一幅加权图GGG以及它的最小生成树。向GGG中添加一条边eee，如何在与VVV成正比的时间内找到新图的最小生成树。
      添加一条边eee，我们首先直接将eee加入当前最小生成树T0T_0T0​集合中，此时必然会在T0T_0T0​中产生一个环，假设eee连接的顶点为x,yx,yx,y，则我们接下来要找出这个环，分别从x,yx,yx,y出发在T0T_0T0​中进行深度优先搜索DFSDFSDFS，当搜索到同一个结点时所经过的结点就是该环上的结点 ，根据环上的结点对判断边权值，将这个环中最大权值的边eme_mem​从T0+{e}T_0+\{e\}T0​+{e}中删去，由此得到的T0+{e}−{em}=T1T_0+\{e\}-\{e_m\}=T_1T0​+{e}−{em​}=T1​就是新图的最小生成树，需要的时间取决于换上的结点数，最坏情况下要搜索所有的结点，即时间为O(V)O(V)O(V)。

3. 使用DijkstraDijkstraDijkstra算法解决加权有向图中的多起点最短路径问题，其中边的权重均为正：给定一组起点，找到相应的最短路径森林并实现一个方法为用例返回从任意起点到达每个顶点的最短路径。

      对于每个终点，由于有多个起点，每个起点到达终点都有一条最短路径，我们需要找到这些最短路径中的最短的一条，则可以将由边u→vu→vu→v视为v→uv→uv→u，但权值不变，即将终点视为新的起点，这样只需要对新的起点运行一次DijkstraDijkstraDijkstra算法即可找出该点到所有顶点的最短路径，对应的新的起点到原起点的最短路径集合即为最短路径森林，其中最短的一条即为原起点到每个顶点的最短路径。

4. 给定一组边的权重均为正的有向图和两个没有交集的顶点集SSS和 TTT，找到从SSS中的任意顶点到达TTT中的任意顶点的最短路径。要求设计的算法在最坏情况下所需的时间应该与Elog⁡VE\log VElogV成正比。
      使用DijkstraDijkstraDijkstra算法，将SSS顶点集视作一个开始顶点S′S'S′，TTT顶点集视作一个目的顶点T′T'T′，对于顶点集外部的顶点，所要找的最短路径，即为S′S'S′与顶点集外部顶点和T′T'T′所构成的图中的S′⇝T′S'\leadsto T'S′⇝T′最短路径。
      将SSS集合中所有与不属于SSS集合的顶点直接相连所构成的边视为由S′S'S′出发的边，将TTT集合中所有与不属于TTT集合的顶点直接相连所构成的边视为到达T′T'T′的边，则只需运行一遍DijkstraDijkstraDijkstra算法即可得到一条最短路径，最短路径中由S′S'S′出发的边在SSS顶点集中的顶点即为出发点，到达T′T'T′的边在TTT顶点集中的顶点即为终点，分别替换最短路径中的S′，T′S'，T'S′，T′即为题目要求的最短路径。
      设边数为E，顶点数为V，则运行一次DijkstraDijkstraDijkstra算法所需时间为O(Elg⁡V)O(E\lg V)O(ElgV)，找出S、TS、TS、T顶点集中的出发点和目的点需要时间O(V)O(V)O(V)，所以最坏情况下需要O(Elg⁡V+V)O(E\lg V+V)O(ElgV+V)