Content deleted Content added
→Pseudocode: Here's the reason I am removing this 2nd opt as original research, again: I still don't see how it helps. Maintaining components dynamically when each edge is added doesn't help, because we don't need that information until the next interation when we have plenty of time to recompute. And it does hurt, because even with union-find dynamic connectivity is not a constant-time operation. |
→Pseudocode: specify over which edges we're iterating |
||
Line 55:
Find the [[Component_(graph_theory)|connected component]]s of ''F'' and assign to each vertex its component
Initialize the cheapest edge for each component to "None"
'''for each''' edge ''uv'' in ''E'', where ''u'' and ''v'' are in different components of ''F'':
'''if''' ''uv'' is cheaper than the cheapest edge for the component of ''u'' '''then'''
Set ''uv'' as the cheapest edge for the component of ''u''
| |||