java - 如何找到连接选定顶点(顶点子集)的最小连接器

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)