Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork1.8k
Description
Link:https://cp-algorithms.com/graph/mst_prim.html#sparse-graphs-om-log-n
Edge
in all the other places across document contains the weight and the already-selected node to which it is directed towards. For example: Thei element invector<Edge> min_e(N)
implies that the smallest cost with which it can be connected to an already-selected node is 'w' and that already-selected node is 'to'.
However, in the implementation for sparse graphs, theset<Edge>
contains all edges which connect selected to not-selected nodes, where 'to' now contains a node which is not already selected.
Implying at one place theto
inEdge
refers to selected nodes, whereas in other places it refers to non-selected nodes. While the algorithm still works best, but I think this bit can be clarified.