Prims algorithm for sparse graphs needs some more elaboration #1426
Comments
|
I'm a little confused on the issue right now, though I'm not that familiar with the article. As a rule, any contribution is welcome. We don't really assign stuff as we don't have dedicated enough members nor do we know the expertise of the individual. If you believe that there could be some clarifying text, feel free to write it and submit a pull request. That will be taken more seriously and have a more thorough review. |
|
Ah, that works! Thanks.
…On Tue, 18 Feb 2025, 08:00 Michael Hayter, ***@***.***> wrote:
I'm a little confused on the issue right now, though I'm not that familiar
with the article.
As a rule, any contribution is welcome. We don't really assign stuff as we
don't have dedicated enough members nor do we know the expertise of the
individual.
If you believe that there could be some clarifying text, feel free to
write it and submit a pull request.
That will be taken more seriously and have a more thorough review.
—
Reply to this email directly, view it on GitHub
<#1426 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/BCJ42KIL74EIIZFKLH4A4RD2QKLMTAVCNFSM6AAAAABXHPDI7CVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDMNRUGQ3DONBSGM>
.
You are receiving this because you authored the thread.Message ID:
***@***.***>
[image: mhayter]*mhayter* left a comment
(cp-algorithms/cp-algorithms#1426)
<#1426 (comment)>
I'm a little confused on the issue right now, though I'm not that familiar
with the article.
As a rule, any contribution is welcome. We don't really assign stuff as we
don't have dedicated enough members nor do we know the expertise of the
individual.
If you believe that there could be some clarifying text, feel free to
write it and submit a pull request.
That will be taken more seriously and have a more thorough review.
—
Reply to this email directly, view it on GitHub
<#1426 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/BCJ42KIL74EIIZFKLH4A4RD2QKLMTAVCNFSM6AAAAABXHPDI7CVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDMNRUGQ3DONBSGM>
.
You are receiving this because you authored the thread.Message ID:
***@***.***>
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Link: https://cp-algorithms.com/graph/mst_prim.html#sparse-graphs-om-log-n
Edgein all the other places across document contains the weight and the already-selected node to which it is directed towards. For example: The i 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, the
set<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 the
toinEdgerefers 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.The text was updated successfully, but these errors were encountered: