所以我在看 Prim 算法的维基百科条目:
1. Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v) and an edge E[v] (the edge providing that cheapest connection). To initialize these values, set all values of C[v] to +∞ (or to any number larger than the maximum edge weight) and set each E[v] to a special flag value indicating that there is no edge connecting v to earlier vertices.
2. Initialize an empty forest F and a set Q of vertices that have not yet been included in F (initially, all vertices).
3. Repeat the following steps until Q is empty:
a. Find and remove a vertex v from Q having the minimum possible value of C[v]
b. Add v to F
c. Loop over the edges vw connecting v to other vertices w. For each such edge, if w still belongs to Q and vw has smaller weight than C[w], perform the following steps:
i. Set C[w] to the cost of edge vw
ii. Set E[w] to point to edge vw.
4. Return F
我的问题是关于步骤 3.b(“将 v 添加到 F”)。 步骤3b是错误的吗?“v”是一个顶点,最小生成树是一组边(不是一组顶点)。
似乎步骤 3b 应该改为“将 E[v] 添加到 F”。
步骤 3b 将顶点 v 添加到 F。步骤 ci 和 cii 然后将边添加到 F