לדלג לתוכן

מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Kruskal/פסוודו-קוד

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
# Takes a connected undirected graph (G) and a cost table (Edge-Costs)
# Returns a set of edges E' such that (V(G), E') is 
#	a MST (minimum spanning tree).
MST-Kruskal(G, Edge-Costs)
1	V = V(G)
2	E = E(G)
3	Sets = Make-Array( Length(V) )
4	E' = {}

5	for v in V
6		Sets[v] = Make-Set()

	# Sort the edges by increasing cost, using the
	#	cost-table Edge-Costs.
7	Sort(E) 

8	for (u, v) in E
9		if Find-Set(u) != Find-Set(v)
10			E' = E'  {(u, v)}
11			Union(Sets[u], Sets[v])

12	return E'