给定一个无向加权图 G = (V, E) 和一个整数 s，该整数将顶点集 V = [0, 1, ..., |V|-1] 划分为一组 必需 的顶点 R = [0, 1, ..., s-1] 和一组 Steiner 顶点 S = [s, s+1, ..., |V|-1]，通用 Steiner 树问题是找到 Steiner 顶点的子集 S' ⊆ S 和最小权重的生成树 T = (R ⋃ S', E) 的问题。树 T 的权重就是其边权重的总和。
这个通用 Steiner 树问题是更为人所知的 最小生成树问题 (MST) 的泛化。
与具有多项式解决方案的 MST（例如，O(E log V) Kruskal's/Prim's 算法）不同，这个通用 Steiner-Tree 问题是一个 NP-hard 组合优化问题。
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
这个一般的 Steiner-Tree 问题有几个其他的变体，例如，Euclidean-Steiner-Tree 和 Metric-Steiner-Tree 问题。
在Euclidean-Steiner-Tree 问题中，有 V 个不同的点（集合 R）在一个欧几里得（Euclidean, 二维）平面上，任务是找到一个（可能为空的附加）Steiner 点集 S（可以在二维平面的任何地方）和一个生成树 T = (R ⋃ S, E)，使得 T 的权重最小。任何两点的权重就是这两点的欧几里得距离。
在Metric-Steiner-Tree 问题中，它类似于Euclidean-Steiner-Tree，但这次附加的 Steiner 点是作为一组 S 提前给出的。任何两点的权重必须满足度量空间的属性。
Euclidean-Steiner-Tree，Metric-Steiner-Tree，以及在这个网站上可视化的一般 Steiner-Tree，都是 NP-hard 优化问题。
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
在这里查看所选 Steiner-Tree 算法的可视化。
最初，输入图中的所有顶点和边都用标准黑色轮廓着色。随着可视化的进行，颜色浅蓝色将被用来表示一组必需的顶点R，颜色橙色将被用来显示当前正在使用的 Steiner 顶点。
在所选 Steiner-Tree 算法的最后，我们展示最佳生成树 = Steiner 树T。
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
有两种不同的方式来指定输入图：
- 编辑图：您可以将当前显示的无向加权图编辑为任何其他无向加权图。
- 示例图：您可以从无向加权图的示例列表中选择，以便您开始。
有一天，我们将提供一种简单的方式来重新标记任何当前加载的图中的顶点，以便所需顶点集R始终以[0, 1, ..., s-1]编号（因此其余的是潜在的斯坦纳顶点S）。
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
一般Steiner-Tree问题有3种特殊情况，它们的解决方案是多项式的：
- s = 2，这意味着只需要顶点R = [0, 1]，我们可以简单地运行 O((V+E) log V) 迪杰斯特拉算法来找到连接源顶点0和目标顶点1（或反之）的最短路径生成树。这个生成树也将是所需的Steiner Tree。
- s = |V|，这意味着所有的|V|顶点，即R = [0, 1, ..., |V|-1]都是必需的，我们可以简单地运行 O(E log V) Kruskal或Prim算法来找到整个图的完整最小生成树 (MST)。这个MST也将是所需的Steiner Tree。
- 如果G是一棵树：详细信息待补充。
But when s = [3, 4, ..., |V|-2], we have no choice but to run exponential algorithms as these cases fall into general cases of the NP-hard general Steiner-Tree problem.
One possible way is to try all possible subsets of the |V|-s vertices that can be part of the optimal Steiner Tree. Each time, we combine vertices in R = [0, 1, ..., s-1] with the currently chosen subset of potential Steiner vertices, run an O(E) Kruskal's algorithm (without re-sorting the edge list by weight anymore) for each of the 2|V|-s possible subsets, and report the best Steiner Tree. This is an exponential algorithm and this visualization page shows this algorithm.
有一种更优化的指数算法，叫做 Dreyfus-Wagner 动态规划 (DP) 算法，它避免了子问题的重复计算。
遗憾的是，这部分还没有被数字化/可视化，正在进行中。
请查看CS4234的讲义以获取详细信息。
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
编辑图表
图示
Exact
Approximation