Content deleted Content added
m Task 18 (cosmetic): eval 11 templates: hyphenate params (4×); del |postscript= (2×); cvt lang vals (6×); |
→Pseudocode: Modify the code so it doesn't fall into an infinite loop if the graph G is not connected |
||
Line 47:
Initialize a forest ''F'' to be a set of one-vertex trees, one for each vertex of the graph.
''completed'
'''while''' not ''completed'' '''do'''
Find the connected components of ''F'' and label each vertex of ''G'' by its component
Initialize the cheapest edge for each component to "None"
Line 56 ⟶ 57:
'''if''' ''uv'' is cheaper than the cheapest edge for the component of ''v'' '''then'''
Set ''uv'' as the cheapest edge for the component of ''v''
''completed'' = '''true'''
'''for each''' component whose cheapest edge is not "None" '''do'''
Add its cheapest edge to ''F''
''completed'' = '''false'''
In the conditional clauses, every edge ''uv'' is considered cheaper than "None". The purpose of the ''completed'' variable is to determine whether the forest ''F'' is yet a spanning forest.
If edges do not have distinct weights, then a consistent tie-breaking rule (e.g. breaking ties by the object identifiers of the edges) can be used.
An optimization (not necessary for the analysis) is to remove from ''G'' each edge that is found to connect two vertices in the same component as each other.
| |||