Prim的MST算法为什么求最小顶点？

Question

据我了解，Prim 的 MST 算法将遍历图中的所有顶点，选择一条最佳边到达每个顶点。因此，每次迭代都会为每个相邻顶点选择一个最优成本。因此，无论先使用哪个顶点，最终结果应该是相同的，因为甚至在选择下一个顶点之前就已经选择了最优成本。

因此，我不明白为什么算法必须在每次迭代中选择成本最低的顶点。为了让我的描述更清楚，我包含了来自 geeksforgeeks.org:

的示例代码和图表

// A C / C++ program for Prim's Minimum Spanning Tree (MST) algorithm. 
// The program is for adjacency matrix representation of the graph

#include <stdio.h>
#include <limits.h>

// Number of vertices in the graph
#define V 5

// A utility function to find the vertex with minimum key value, from
// the set of vertices not yet included in MST
int minKey(int key[], bool mstSet[])
{
   // Initialize min value
   int min = INT_MAX, min_index;

   for (int v = 0; v < V; v++)
     if (mstSet[v] == false && key[v] < min)
         min = key[v], min_index = v;

   return min_index;
}

// A utility function to print the constructed MST stored in parent[]
int printMST(int parent[], int n, int graph[V][V])
{
   printf("Edge   Weight\n");
   for (int i = 1; i < V; i++)
      printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);
}

// Function to construct and print MST for a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
     int parent[V]; // Array to store constructed MST
     int key[V];   // Key values used to pick minimum weight edge in cut
     bool mstSet[V];  // To represent set of vertices not yet included in MST

     // Initialize all keys as INFINITE
     for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

     // Always include first 1st vertex in MST.
     key[0] = 0;     // Make key 0 so that this vertex is picked as first vertex
     parent[0] = -1; // First node is always root of MST 

     // The MST will have V vertices
     for (int count = 0; count < V-1; count++)
     {
        // Pick thd minimum key vertex from the set of vertices
        // not yet included in MST
        int u = minKey(key, mstSet);

        // Add the picked vertex to the MST Set
        mstSet[u] = true;

        // Update key value and parent index of the adjacent vertices of
        // the picked vertex. Consider only those vertices which are not yet
        // included in MST
        for (int v = 0; v < V; v++)

           // graph[u][v] is non zero only for adjacent vertices of m
           // mstSet[v] is false for vertices not yet included in MST
           // Update the key only if graph[u][v] is smaller than key[v]
          if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])
             parent[v]  = u, key[v] = graph[u][v];
     }

     // print the constructed MST
     printMST(parent, V, graph);
}


// driver program to test above function
int main()
{
   /* Let us create the following graph
          2    3
      (0)--(1)--(2)
       |   / \   |
      6| 8/    |7
       | /     \ |
      (3)-------(4)
            9          */
   int graph[V][V] = {{0, 2, 0, 6, 0},
                      {2, 0, 3, 8, 5},
                      {0, 3, 0, 0, 7},
                      {6, 8, 0, 0, 9},
                      {0, 5, 7, 9, 0},
                     };

    // Print the solution
    primMST(graph);

    return 0;
}

从下面的代码块我们可以看出，每次迭代都会为每个邻居选择最优权重（在这种情况下，只有一条边连接任意两个顶点）：

if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
    parent[v] = u, key[v] = graph[u][v];

我们以顶点7为例，它有3条边。边 6-7 最终将从边 0-7、8-7 和 6-7 中选择，因为它的权重最小，无论我们是否首先评估顶点 0-7、8-7 或 6-7，因为最佳权重 = min（所有相邻边的权重）。因此，每次迭代都选择最小权重的顶点似乎是多余的。

有人可以向我解释一下在以下代码块中为每次迭代选择最小权重顶点的目的是什么吗？

// Pick thd minimum key vertex from the set of vertices
// not yet included in MST
int u = minKey(key, mstSet);

Answer 1

Let's take vertex 7 as example, it has 3 edges. edge 6-7 will eventually be selected from edges 0-7, 8-7 and 6-7 as its weight is minimum, regardless of whether we evaluate vertex 0-7, 8-7 or 6-7 first because the optimum weight = min(weight of all adjacent edges). Hence, it seems redundant to choose the minimum weight vertex every iteration.

看来您混淆了这两个循环的用途。内部循环不 select 任何事情。它只是计算权重。 selection 是外循环。

这样看。想象一下只有一个循环开始，并且我们已经选择了一个随机的起始顶点。现在这个循环需要选择一个边缘。当然，它越过相邻的边缘并拾取最小值。 它如何 并不重要：权重是分配给顶点还是它只是在边缘上循环并选择最好的一个。

然而，当顶点越来越多时，事情就变得复杂了。添加另一个顶点后，您可能会发现一种获取新顶点的更好方法。假设你从顶点 2 开始。你添加顶点 8。现在你可以从 2（权重 8）到 1，从 2（权重 7）到 3，从 8（权重 6）到 6，从 8（权重 7）到 7。然而，一旦你从 8 到 6，你现在有一个更好的方法从 6 到 7，权重仅为 1，而不是权重 7（边缘 8-7）。因此，您需要更新最佳路径的概念。

一种方法是在每次迭代时简单地遍历所有与 已包含在 MST 集合 中的每个顶点相邻的边，并选择最佳边。这引入了两个内部循环来找到最小值：一个遍历 MST 集中的顶点，另一个遍历与每个此类顶点相邻的边。对于具有 n 个顶点和大约 n^2 个边的接近完整的图，您将总共得到 O(n^3)。

所以这个算法的作用是，它只遍历顶点而不是边。每个顶点都保留从当前 MST 集到那里的最简单方法的权重。这允许我们将内部循环一分为二。通过遍历所有 个顶点 找到最佳的下一个顶点。它选择最好的相邻一个，因为非相邻的有无限的权重。这正是令人困惑的行所做的。这是 O(n).

另一个内部循环更新权重。但是，由于更新可能仅由添加新顶点引起，因此只需要考虑与该特定顶点相邻的边！这又是 O(n)（假设一个几乎完整的图表）。因此，您将所有三个循环的复杂性降低到 O(n^2)。

事实上，如果使用邻接矩阵，图是否完整都没有关系。要摆脱 minKey 部分，您需要创建 three 嵌套循环：第一个内部循环将遍历 MST 集中的所有顶点，最里面的循环将遍历其相邻的边缘，包括不存在的边缘。 minKey 技巧只允许有这个：

    // Update key value and parent index of the adjacent vertices of
    // the picked vertex. Consider only those vertices which are not yet
    // included in MST
    for (int v = 0; v < V; v++) // note there is no loop over `u`!

Prim的MST算法为什么求最小顶点？

Why get minimum vertex in Prim's MST algorithm?

c++

minimum-spanning-tree

prims-algorithm