任何人都可以帮助我如何使用 PRIM 算法查找 MST。突出显示 MST 的边缘并写出节点添加到 MST 的顺序。 谢谢
最佳答案
引用The Directed Minimum Spanning Tree Problem :
- Discard the arcs entering the root if any; For each node other than the root, select the entering arc with the smallest cost; Let the selected n-1 arcs be the set S.
- If no cycle formed, G(N,S) is a MST. Otherwise, continue.
- For each cycle formed, contract the nodes in the cycle into a pseudo-node (k), and modify the cost of each arc which enters a node (j) in the cycle from some node (i) outside the cycle according to the following equation.
c(i,k)=c(i,j)-(c(x(j),j)-min_{j}(c(x(j),j)) here c(x(j),j) is the cost of the arc in the cycle which enters j.- For each pseudo-node, select the entering arc which has the smallest modified cost; Replace the arc which enters the same real node in S by the new selected arc.
- Go to step 2 with the contracted graph.
The key idea of the algorithm is to find the replacing arc(s) which has the minimum extra cost to eliminate cycle(s) if any. The given equation exhibits the associated extra cost.
关于algorithm - 使用Prim算法求有向图的MST，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4565662/