如何找到连接所选顶点的最小连接器（顶点子集）

Question

假设我有一个无向图，有 10 个顶点和 24 条边相互连接，例如，如果我给出这样的输入（这不是实际的，实际的是 10*10 )

int graph[][] = new int[][]{{0, 0, 0, 0, 0, 0},
                            {0, 0, 2, 0, 6, 0},
                            {0, 2, 0, 3, 8, 5},
                            {0, 0, 3, 0, 0, 7},
                            {0, 6, 8, 0, 0, 9},
                            {0, 0, 5, 7, 9, 0}};

所以我想找到最少的连接器以连接特定的顶点 例如：顶点 0、2、4。目前我应用了 prims 算法，以便通过图形的所有边缘获得最少的连接器，但由于我不希望所有边缘都包含在我的 MST 中，我需要一些帮助来实现这一点。

一开始我不能删除我不想要的边，因为它会断开图形

请帮忙。

Answer 1

所以你有 6 个顶点和 7 个无向加权边：

 1 ←→ 2 (w=2)
 1 ←→ 4 (w=6)
 2 ←→ 3 (w=3)
 2 ←→ 4 (w=8)
 2 ←→ 5 (w=5)
 3 ←→ 5 (w=7)
 4 ←→ 5 (w=9)

您需要连接顶点 0、2 和 4，因此您使用这 3 个顶点构建一个新图，并找到它们之间的最短路径。

 0 ←→ 2 (no edge)
 0 ←→ 4 (no edge)
 2 ←→ 4 (w=8)

这当然不可能，因为没有到顶点 0 的边。

所以让我们试试顶点 1、3 和 5：

 1 ←→ 3 (w=5, 1 ←→ 2 ←→ 3)
 1 ←→ 5 (w=7, 1 ←→ 2 ←→ 5)
 3 ←→ 5 (w=7, 3 ←→ 5)

现在对其应用最小生成树 (MST)：

 1 ←→ 3 ←→ 5 (w=12)

扩展回原始图：

 1 ←→ 2 ←→ 3 ←→ 5 (w=12)

如何找到连接所选顶点的最小连接器（顶点子集）

How to find the minimum connectors to connect selected vertices (subset of vertices)

java

algorithm

graph

minimum-spanning-tree

prims-algorithm