Question

Spanning Tree / Spanning Forest

“生成树”。从一张图分离出一棵树，包含图上所有点。可能有许多种。

当一张图完全连通，则有生成树。当一张图不连通，则没有生成树，而是许多棵“生成子树”构成的“生成森林”。宛如 DFS tree 与 DFS forest 的关係。

生成树也可以有权重。当图上每条边都有权重时，生成树的权重为树上每条边的权重总和。

Minimum Spanning Tree

“最小生成树”。权重最小的生成树。可能有许多种。

Minimum Spanning Tree: Kruskal's Algorithm

用途

求出无向图的其中一棵最小（大）生成树。若是图不连通，则是求出其中一丛最小（大）生成森林。

想法

一、一个单独的点，可以视作一棵最小生成子树 MSS。

二、两棵 MSS 连结成一棵 MSS，以两棵 MSS 之间权重最小的边进行连结，显然是最好的。

三、三棵 MSS 连结成一棵 MSS，先连结其中两棵连结权重最小的 MSS，才连结第三棵，总是比较好。

由以上三点归纳出：以一张图上权重最小、次小、……的边，连结各棵 MSS，总是比较好。

连结所有 MSS，最后得到最小生成树（森林）。

演算法

一、图上每一个点，各自是一棵最小生成子树 MSS。
二、图上所有边，依照权重大小，由小到大排序。
三、尝试图上所有边，作为最小生成树（森林）的边：
　甲、两端点分别位于两棵 MSS，也就是产生了桥：
　　　用这条边连结两棵 MSS，合併成一棵 MSS。
　　　这条边是最小生成树（森林）上的边。
　乙、两端点皆位于同一棵 MSS，也就是产生了环：
　　　捨弃这条边。

亦可求出最大生成树（森林）：

精髓：不断连结两棵 MSS、合併两个集合。

时间複杂度

一、排序图上所有边。O(ElogE)。

二、连结 MSS，採用“ Disjoint-set Forest ”。O(E*α(E,V))。

总时间複杂度为 O(ElogE)。

如果两点之间有多条边，预先以 Graph Traversal 扫描一次所有边，保留权重最小的边，仍可求得正确答案。两点之间只剩下一条边，边的总数至多 C{V,2} = V*(V-1)/2 条。时间複杂度 O(ElogE) 可以改写成 O(Elog(V^2)) = O(2ElogV) = O(ElogV)。

Minimum Spanning Tree: Prim's Algorithm

用途

求出无向图的其中一棵最小（大）生成树。

演算法

仿效“ Shortest Path: Dijkstra's Algorithm ”。

差异：Dijkstra's Algorithm 屡次找不在树上、离根最近的点，Prim's Algorithm 屡次找不在树上、离树最近的点。

另一个差异：选择特定一点做为起点，得到不同的最短路径树；选择任意一点做为树根，得到相同的最小生成树。

时间複杂度

图的资料结构为 adjacency matrix 的话，便是 O(V^2)；图的资料结构为 adjacency lists 的话，还是 O(V^2)。

如同 Dijkstra's Algorithm，使用 Priority Queue、Fibonacci Heap 可以得到更低的时间複杂度。

Minimum Spanning Tree: Borůvka's Algorithm

用途

求出无向图的其中一棵最小（大）生成树。若是图不连通，则是求出其中一丛最小（大）生成森林。

演算法

一、图上每一个点，各自是一棵最小生成子树 MSS。
二、每棵 MSS 同时找权重最小、索引值最小的联外边，相互连接。
　口、联外边是 MSS 之间的边，不是 MSS 之内的边。
　口、联外边可能重複，无妨。
　口、联外边显然不会形成环。
三、重複步骤二，直到形成最小生成树（森林）。

找权重最小的联外边，以得到最小生成树；当权重一样小，则找索引值最小的联外边，以避免联外边形成环。联外边的索引值，可以改成联外边的两端点索引值。

证明很简单：图上任意一只环，环上权重最大、索引值最大的边，绝不会被选中。过程中无法形成环，只会形成树。每一点都联外，权重又最小，所以是最小生成树。

时间複杂度

一、每回合寻找权重最小、索引值最小的联外边。O(V+E)。

二、连接 MSS。採用“ Disjoint-sets Forest ”，每回合每个点都呼叫了 union 与 find，森林结构维持在最佳状态，union 与 find 的总时间複杂度，从 O(E * α(E,V)) 下降至 O(E)。

三、回合数。最差情况：每回合 MSS 两两成对互连，MSS 总数量仅下降一半，共 logV 个回合。平均情况：图上的边呈随机分布，仅 1 至 2 个回合。【待补证明】

最差时间複杂度为 O((V+E) * logV)，可以简单写成 O(ElogV)。平均时间複杂度为 O(V+E)。

Minimum Spanning Tree: Edmonds' Algorithm

用途

求出有向图的其中一棵最小（大）生成树。

有向图上，以权重最小的边，连结两棵有向 MSS，不见得形成有向 MSS。直接套用无向图的演算法，边的方向乱七八糟，无法形成有向生成树。必须设计其他演算法。

想法

生成树的基本概念是：连接图上各点的树。从这个概念下手，并且考虑边的方向性，得到两个粗糙的演算法：

有向图上，每一个点，如果要被连结到，都要至少有一条出边，除了树叶以外。
每一个点，找权重最小的出边，会比较好。

有向图上，每一个点，如果要被连结到，都要刚好有一条入边，除了树根以外。
每一个点，找权重最小的入边，会比较好。

出边有许多条，入边只有一条，从入边下手比较容易。

树根是个例外，树根没有入边。但是我们可以假定我们已经知道最小生成树的树根是哪个点，如此就不必顾虑例外了。设计好演算法之后，用试误法尝试各种树根即可。

Minimum Arborescence

预先指定树根的有向最小生成树。个人感觉这个词彙不太讨喜。

水母【尚无正式名称，因为像水母就把它叫做水母】

运气好的时候，各点的最小入边，刚好形成一棵生成树，而且是最小生成树。

运气普通的时候，各点的最小入边，通常形成许多隻水母。

各点各取一条入边，一旦入边们形成环，此环一定只有出边、没有入边。环与出边，形成一个特别的图：很多棵树，一只环串起了树根。又像是太阳、又像是水母。

把水母改装成最小生成子树

最小生成树不得有环。水母有环，是不合格的。

水母是权重最小的连结方式，最小生成树的权重则略高、等高于水母。使用穷举法，尝试拆除水母的每一条边，并且更改为另一条边，从中找到权重增加最少的边。

一、更改水母环的边：
　甲、新边是由其他水母连入：水母环消失。变成其他水母脚。很好！
　乙、新边是由自身水母环连入：水母环变小。连结权重无故变大，不可取。
　丙、新边是由自身水母脚连入：水母环变大。多了一些点可供联外。
二、更改水母脚的边：
　　水母环不变，连结权重无故变大，不可取。

有好处的只有一甲、一丙。归纳出：只需要更改水母环的边，让水母环消失或者变大，从中选择权重增加最少的拆除方式。

演算法

水母环的入边，全部看过一遍，找到权重增加最少的入边。

已经看过的入边，修改成权重增加量，然后收缩水母环，就不用看第二遍了。

壹、删去所有自环：自己连向自己的边。
贰、图上每一点尝试做为树根。
　一、删去树根的全部入边。也可以将权重设定为无限大。
　二、判断树根能不能连到图上各点。否则生成树不存在。
　三、重複以下步骤，直到形成生成树为止：
　　甲、每一个点，找出权重最小的入边。O(V+E)
　　　　形成一群水母。
　　乙、调整水母环的入边的权重，修改成权重增加量。O(V+E)
　　　　w(a, x) -= w(å, x)，
　　　　x 是水母环上一点。
　　　　åx 是 x 点的最小入边，也是水母环上的边。
　　　　ax 是 x 点的其他入边。
　　丁、收缩水母环，成为一点。O(V+E)

Kruskal's Algorithm 连结多个 MSS。一旦发现造成环的边，就直接捨弃；一旦发现造成桥的边，就一定保留。

Edmonds' Algorithm 连结多隻水母。总是留下造成环的边（形成水母环），并且尝试各种打开环的方式：有时候扩大水母环，有时候两隻水母连结成一隻水母。

时间複杂度

一、每回合找出各点的最小入边。O(V+E)。

二、回合数。最差情况是每回合产生一个水母，水母环只有两点。水母环收缩之后，整张图只减少一个点。图上有 V 个点，最多收缩 V-1 次水母环，总共 V-1 个回合。

三、穷举 V 个点，尝试做为树根。

时间複杂度为 O(VVE)。

演算法

穷举树根，再仿效 Dijkstra's Algorithm，时间複杂度为 O(V^3)。有差异的地方，不影响时间複杂度：

一、缩环最多 V-1 次（两点缩成一点）。缩环得到的新点，最多 V-1 个。总点数最多 2V，仍是 O(V)。

二、缩环，採用 Disjoint-sets Forest。O(E * α(E,V))。

如同 Dijkstra's Algorithm，使用 Priority Queue、Fibonacci Heap 可以得到更低的时间複杂度。

UVa 11183

Minimum Bottleneck Spanning Tree

Bottleneck

一张图上、一棵生成树上、一条路径上，权重最小的边，称作“瓶颈”。

然而，为了前后文连贯，此处将定义暂时更改为权重最大的边。古早人也是如此定义。

Minimum Bottleneck Spanning Tree

一张图的所有生成树当中，权重最大的边（瓶颈），其权重最小的生成树，称作“最小瓶颈生成树”，可能有许多棵。

以下只讨论无向图。一个简单的方式，是以最小生成树 MST，作为最小瓶颈生成树 MBST。

Kruskal's Algorithm 造就 MST 的最后一条边，就是瓶颈。

证明

既然胆敢宣称 MST 是 MBST，那麽也许 MST 与 MBST 当中有些相近的性质。有时不妨率由旧章，以现有的 MST 性质，推定未知的 MBST 性质。大胆假设、小心求证。

MST 有著一个关键性质：以权重最小的边，连接两棵 MST，可以构成一棵 MST。依样画葫芦，MBST 或许也有著一个关键性质：以权重最小的边，连接两棵 MBST，可以构成一棵 MBST。

此处用中文囉哩囉嗦证明之。若用数学式子，也许只消两行：

甲、连接的边，权重大于等于原本两棵 MBST 的瓶颈权重，则会成为新树的瓶颈。由于选择了权重最小的边当作连接的边，连接的边又是新树的瓶颈，新树的瓶颈权重当然也最小──新树是一棵 MBST。

乙、连接的边，权重小于原本两棵 MBST 的瓶颈权重，则不会成为新树的瓶颈。新树的瓶颈由原本两棵 MBST 的瓶颈二选一，选权重大的那个成为新树的瓶颈。因为原本两棵 MBST 的瓶颈权重已经最小了，新树的瓶颈权重当然也最小──新树是一棵 MBST。

新性质是正确的！由于 MST 和 MDST 都可以用权重最小的边构造而得，因此在每一种 MST 演算法当中，每个步骤的 MST 也随时是 MBST。

儘管 MST 一定是 MBST，但是小心 MBST 不见得是 MST。儘管两棵 MBST 以权重最小的边相连，一定是一棵 MBST，但是一棵 MBST 移除权重最大的边，不见得是两棵 MBST。

演算法

事实上 MBST 有一个 O(V+E) 的演算法。

一、二分搜寻法，搜寻图上所有边的权重，找出 MBST 的瓶颈。
　　二分时，採用 O(N) 的中位数演算法。
二、每枚举一个瓶颈，权重小于等于瓶颈的边，皆可作为生成树。
　甲、扫描一次，找出权重小于等于瓶颈的边。
　乙、Graph Traversal，判断图上各点是否连通。
　　　若连通，则此瓶颈定可形成生成树。反之则无法形成生成树。
　丙、连通的点，合併为一点。以后就不需要重新遍历了。
三、若要构造生成树，在乙步骤，去掉形成环的边（back edge）即可。
　　MST 与 MBST 相异之处就在于：
　　MBST 可以去掉环上任意一条边，MST 必须去掉环上权重最大的边。

Minimum Bottleneck Path

一张无向图上，两点之间的所有路径当中，瓶颈权重最小的一条路径，称作“最小瓶颈路径”，可能有许多条。

最小生成树上的所有路径，都是原图的最小瓶颈路径。证明方式同前，只是把生成树改成了路径。

如果需要所有两点之间的最小瓶颈路径的其中一个瓶颈，则可以使用 DP：从边数为一的最小瓶颈路径开始，逐步推导出更长的最小瓶颈路径。O(V^2) 时间建表、O(1) 时间查询。

亦可利用“ Lowest Common Ancestor ”。O(VlogV) 时间建表、O(logV) 时间查询。

有向图的情况，就请读者自行研究了。最简单的作法是修改最短路径演算法。

UVa 11354 12176 12655

Second-best Minimum Spanning Tree

一张无向图，权重最接近最小生成树的另一棵生成树，称作“次小生成树”。可能与最小生成树权重相等。可能有许多棵。

找到一棵次小生成树，演算法共两种。

一、求出一棵最小生成树。（建议使用 Kruskal's Algorithm）
二、穷举每一条最小生成树上的边 pq：
　甲、从图上删除此边，重新求出一棵最小生成树。（边不必重新排序）
　乙、记下此树。
三、刚刚得到的 V-1 棵树，权重最小者便是次小生成树。

穷举不要的边，删除后再重找。时间複杂度 O(VE*α(E,V))。

一、求出一棵最小生成树。
二、求出树上所有两点 ij 之间，权重最大的边（瓶颈）。记为 E(i,j)。
　　（所有两点间最小瓶颈路径。）
三、穷举每一条不在最小生成树上的边 pq：
　甲、把边 pq 添加到最小生成树上，势必形成环。
　乙、然后拆除边 E(p,q)，势必又形成树，此树权重已然尽量少。
　丙、记下此树。
四、刚刚得到的 E-(V-1) 棵树，权重最小者便是次小生成树。

穷举想要的边，添加后再修正。步骤一与二各有数种演算法，时间複杂度也跟著改变。时间複杂度可达到 O(ElogV)。

UVa 10600 10462 ICPC 5713

Minimum Diameter Spanning Tree

Minimum Diameter Spanning Tree

一张无向图的所有生成树当中，直径最小的生成树，可能有许多棵。

目前尚未有直接的演算法。目前是以绝对中心当作起点的最短路径树 SPT，作为最小直径生成树 MDST。关于绝对中心与最短路径树，可参考“ Central Vertex ”。

证明（Hassin & Tamir, 1995）

证明很简单。在原论文中，证明过程可以写成五行数学式子，閒来无事不妨朝圣一下。以下则是讲得详细一点：

甲、绝对中心的偏心距是最小的，位于 SPT 的直径中央。半径（偏心距）最短，所以直径也是最短。把直径拉成一直线来看，就清楚多了。

d(c, x) = d(c, y)

因为 d(c, x) 会尽量小，所以 2 * d(c, x) = d(c, x) + d(c, y) 也会尽量小。

乙、绝对中心的 SPT 上面随便一条路径，都小于等于直径长度。把路径藉由绝对中心切成两段，就清楚多了。

  d(p, q)
= d(c, p) + d(c, q)
≤ d(c, x) + d(c, y)   切成两条，分别ＰＫ。

  d(i, j)
≤ d(c, i) + d(c, j)   切成两条，分别ＰＫ。
≤ d(c, y) + d(c, y)

最短路径树不见得是最小直径生成树

各位也可以思考一下，为什麽绝对中心的 SPT 才是 MDST，而一般中心的 SPT 并不见得是 MDST。

G:
    0
   /|\
  / | 1
 /  |  \
4---3---2---5

MDST:
    0
    |
    | 1
    |  \
4---3---2---5

SPT, source is 0:
    0
   /|\
  / | 1
 /  |  \
4   3   2---5

SPT, source is 1:
    0
   /|\
  / | 1
 /  |  \
4   3   2---5

SPT, source is 2:
    0
     \
      1
       \
4---3---2---5

SPT, source is 3:
    0
    |\
    | 1
    |
4---3---2---5

SPT, source is 4:
    0
   / \
  /   1
 /
4---3---2---5

SPT, source is 5:
    0
     \
      1
       \
4---3---2---5

可以看到 MDST 的直径长度是 3，而 SPT 的直径长度都是 4 和 5。
也就是说，一般中心的 SPT 不一定就是 MDST。

UVa 10805 Timus 1569 Sphere PT07C

Minimum Diameter Minimum Cost Spanning Tree

最小直径最小成本生成树。从所有最小生成树当中，找到直径最小者，是 NP-complete 问题。

至于从所有最小直径生成树中，找到权重最小者，我尚未找到相关文献。

其他 Spanning Tree

经典生成树问题

Minimum (Cost) Spanning Tree [P]
权重最小的生成树。

Minimum Bottleneck Spanning Tree [P]
权重最大的边，使其权重最小的生成树。
【注：此处 Bottleneck 定义为权重最大的边。】

Minimum Diameter Spanning Tree [P]
直径最短的生成树。

Maximum Leaf Spanning Tree [NP-hard]
叶子最多的生成树。

Minimum Degree Spanning Tree [NP-hard]
度数最多的点，使其度数最少的生成树。

Minimum Routing (Cost) Spanning Tree [NP-hard]
所有两点之间路径，权重总和最小的生成树。

Minimum Ratio Spanning Tree [NP-hard]
有两种权重，分开计算。两种权重比值最小的生成树。

Minimum Edge-disjoint Spanning Trees [P]
边不重叠，权重最小的 k 棵生成树们。

Minimum Congestion Spanning Trees [P]
重叠的边将额外增加权重，权重最小的 k 棵生成树们。

Minimum k-Spanning Tree [NP-hard]
权重最小的生成子树，刚好是 k 个点。

Steiner Tree [NP-hard]
权重最小的生成子树，包含给定的 k 个点。

DFS Tree [P]
使用 Depth-first Search 找到的无向（有向）生成树。

BFS Tree [P]
使用 Breadth-first Search 找到的无向（有向）生成树。

Shortest Path Tree [P]
树根到树上各点都是最短路径的无向（有向）生成树。

Minimum Cut Tree [P]
任意两点间路径的瓶颈，形成两点间最小割的无向生成树。

Dominator Tree [P]
树根到树上各点的支配点，形成的有向生成树。

Minimum Ratio Spanning Tree

最小（大）比率生成树。NP-complete。

演算法类似于最小比率环，时间複杂度等同于求 O(logR) 次最小生成树。

一、设定一比率 r 后，把原图转换成新图，除法转换成差值。
二、新图上一棵权重为零的生成树，就是原图上一棵比率为 r 的生成树。
　　新图上一只零环，就是原图上一只比率为 r 的环。
三、当新图上有一棵负权重的生成树，表示这棵树比率比 r 小：
　甲、比率设更小，设成 r'之后，
　　　这棵树就可以变成零权重生成树，就是原图上比率为 r'的生成树。
　　　找到了一棵比率更小的生成树。
　乙、至于要找一棵负权重的生成树，直接找最小生成树就行了。

ICPC 3465 4326

Minimum Steiner Tree

一张无向图，给定 k 个点，用图上的边连接这 k 个点，使得 k 个点相互连通，并且尽量减少这些边的权重总和。为了减少权重，这些边不需形成环，只需形成树，称作 Steiner Tree，Steiner 是人名。

注意到 Steiner Tree 并不是生成树，只不过是概念近似于最小生成树。

求出权重最小的 Steiner Tree 是 NP-complete 问题。

特殊情况：
当 k = 1 时，Minimum Steiner Tree 就是一个点。
当 k = 2 时，Minimum Steiner Tree 就是此两点间最短路径。
当 k = V 时，Minimum Steiner Tree 就是最小生成树。

http://www.prefield.com/algorithm/dp/steiner_tree.html

ICPC 3271

Degree-Constrained Minimum Spanning Tree

每个点限制连接边数上限的最小生成树。NP-complete。

当上限规定为两条边，就是 Hamilton Path。

UVa 10605

Spanning Forest Decomposition

Spanning Forest Decomposition，无权重的图。

一张图分解成数丛生成森林，採用的分解方式是：屡次从剩下的图分离出生成森林。分解结果可能有许多种。

无权重图的情况下，直觉的方式是寻找 O(V) 次生成森林，寻找一丛生成森林需时 O(V+E)，总时间複杂度为 O(VE)。较佳的方式是 Maximum Cardinality Search，总时间複杂度为 O(V+E)。

可以用来快速找到 k-connected subgraph。

Enumerate Spanning Trees

时间複杂度 O(V+E+N)，其中 N 是生成树数目。

http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-50.pdf

Count Spanning Trees

Matrix Tree Theorem

Laplacian matrix 的任意一个 cofactor，其绝对值大小，就是各种生成树的总数目。

cofactor 就是随便砍掉某一行与某一列，剩下来的矩阵，然后加上係数+1 或-1。

http://en.wikipedia.org/wiki/Kirchhoff's_theorem

证明会用到一个性质:
给定一个无向图，两点之间最多只有一边。
如果原图是树，Laplacian matrix 随便砍掉一横行之后，绝对值都是 1。
如果原图不连通，Laplacian matrix 随便砍掉一横行之后，绝对值都是 0。
－
Laplacian matrix 可以写成 F * transpose(F) 的形式，F 是 incidence matrix。
把 F 的随便一个横行给砍了，变成 E，
然后用 Bxxx-Cxxx 展开 E * transpose(E)，
展开之后会变成两两(V-1)x(V-1) 方阵相乘，然后相加。
所有 E 取 V-1 的各种可能都会被展开出来。(还没証，不要问，很可怕)
每一种可能就代表 V-1 条边，有可能成为生成树，有可能不行。
－
两个(V-1)x(V-1) 方阵，乘出来，刚好就是 V 个点的 Laplacian matrix 砍掉某一横行。
如果是生成树的话就会是 1，所以统统加一加，就是生成树数目。