H o m e w o r k 9 Homework 9 Homework9
-
给定一幅加权图 G G G 以及它的最小生成树。从 G G G中删去一条边且 G G G 仍然是连通的，如何在与 E E E成正比的时间内找到新图的最小生成树。
删去一条边有两种情况：
1. 如果删去的边不属于最小生成树 T 0 T_0 T0，那么对图的最小生成树无影响，新图的最小生成树仍是 T 0 T_0 T0
2. 如果删去的边属于最小生成树 T 0 T_0 T0，那么删去一条边 e 0 e_0 e0后相当于 T 0 T_0 T0断开，得到最小生成树的两棵子树 ( T 1 、 T 2 ) ∈ T 0 (T_1、T_2)∈T_0 (T1、T2)∈T0，那么只需要去图 G G G中找到一个边 e 1 ∉ T 0 e_1∉T_0 e1∈/T0，首先找到能够将这两个子树连接起来的所有边，即 e 1 ∈ { ( u , v ) ∣ u ∈ T 1 & v ∈ T 2 } e_1∈\{(u,v)|u∈T_1\&v∈T_2\} e1∈{(u,v)∣u∈T1&v∈T2}，再在这些边中找一个权值最小的边，即 m i n ( e 1 . w e i g h t ) min(e_1.weight) min(e1.weight)，则 { e 1 } + T 0 − { e 0 } = T 1 \{e_1\}+T_0-\{e_0\}=T_1 {e1}+T0−{e0}=T1就是新图的最小生成树，最坏情况下需要遍历图中剩余所有的边，所以时间为 O ( E ) O(E) O(E)。 -
给定一幅加权图 G G G以及它的最小生成树。向 G G G中添加一条边 e e e，如何在与 V V V成正比的时间内找到新图的最小生成树。
添加一条边 e e e，我们首先直接将 e e e加入当前最小生成树 T 0 T_0 T0集合中，此时必然会在 T 0 T_0 T0中产生一个环，假设 e e e连接的顶点为 x , y x,y x,y，则我们接下来要找出这个环，分别从 x , y x,y x,y出发在 T 0 T_0 T0中进行深度优先搜索 D F S DFS DFS，当搜索到同一个结点时所经过的结点就是该环上的结点 ，根据环上的结点对判断边权值，将这个环中最大权值的边 e m e_m em从 T 0 + { e } T_0+\{e\} T0+{e}中删去，由此得到的 T 0 + { e } − { e m } = T 1 T_0+\{e\}-\{e_m\}=T_1 T0+{e}−{em}=T1就是新图的最小生成树，需要的时间取决于换上的结点数，最坏情况下要搜索所有的结点，即时间为 O ( V ) O(V) O(V)。 -
使用 D i j k s t r a Dijkstra Dijkstra算法解决加权有向图中的多起点最短路径问题，其中边的权重均为正：给定一组起点，找到相应的最短路径森林并实现一个方法为用例返回从任意起点到达每个顶点的最短路径。
对于每个终点，由于有多个起点，每个起点到达终点都有一条最短路径，我们需要找到这些最短路径中的最短的一条，则可以将由边 u → v u→v u→v视为 v → u v→u v→u，但权值不变，即将终点视为新的起点，这样只需要对新的起点运行一次 D i j k s t r a Dijkstra Dijkstra算法即可找出该点到所有顶点的最短路径，对应的新的起点到原起点的最短路径集合即为最短路径森林，其中最短的一条即为原起点到每个顶点的最短路径。
-
给定一组边的权重均为正的有向图和两个没有交集的顶点集 S S S和 T T T，找到从 S S S中的任意顶点到达 T T T中的任意顶点的最短路径。要求设计的算法在最坏情况下所需的时间应该与 E log V E\log V ElogV成正比。
使用 D i j k s t r a Dijkstra Dijkstra算法，将 S S S顶点集视作一个开始顶点 S ′ S' S′， T T T顶点集视作一个目的顶点 T ′ T' T′，对于顶点集外部的顶点，所要找的最短路径，即为 S ′ S' S′与顶点集外部顶点和 T ′ T' T′所构成的图中的 S ′ ⇝ T ′ S'\leadsto T' S′⇝T′最短路径。
将 S S S集合中所有与不属于 S S S集合的顶点直接相连所构成的边视为由 S ′ S' S′出发的边，将 T T T集合中所有与不属于 T T T集合的顶点直接相连所构成的边视为到达 T ′ T' T′的边，则只需运行一遍 D i j k s t r a Dijkstra Dijkstra算法即可得到一条最短路径，最短路径中由 S ′ S' S′出发的边在 S S S顶点集中的顶点即为出发点，到达 T ′ T' T′的边在 T T T顶点集中的顶点即为终点，分别替换最短路径中的 S ′ ， T ′ S'，T' S′，T′即为题目要求的最短路径。
设边数为E，顶点数为V，则运行一次 D i j k s t r a Dijkstra Dijkstra算法所需时间为 O ( E lg V ) O(E\lg V) O(ElgV)，找出 S 、 T S、T S、T顶点集中的出发点和目的点需要时间 O ( V ) O(V) O(V)，所以最坏情况下需要 O ( E lg V + V ) O(E\lg V+V) O(ElgV+V)