Content deleted Content added
m Signing comment by 2.219.26.139 - "→Current pseudocode assumes connected graph: " |
|||
Line 147:
Borůvka's algorithm is in many cases presented in a variant, which works for disconnected graphs and generates a minimum spanning forest, by presenting it using the edge contractions. But the pseudocode assumes, that the graph is connected by saying:
<source lang="text" start="0" line>
Input: A connected graph G whose edges have distinct weights
</source>
<source lang="text" start="2" line>
While T has more than one component:
</source>
I believe this should read:
<source lang="text" start="0" line>
Input: A graph G whose edges have distinct weights
</source>
<source lang="text" start="2" line>
While there is an edge between any two components:
</source>
Although it is possible, that the original paper covers only the connected case.
| |||