55.52. МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО

 
  THIS SECTION IS UNDER CONSTRUCTION  
 

Алгоритмы для минимального остовного дерева:
	алгоритм Крускала (Kruskal)
	алгоритм Прима (Prim)




Def
===
	Связный подграф графа G явсляющийся деревом и содержащий все его вершины 
	называется покрывающим или остовным деревом (spanning tree).



Def
===
	Минимальное остовное дерево (MST - Minimal spanned tree) - остовное 
	дерево с минимальным весом.



  
  Алгоритм Прима 
 

MST-PRIM(G,w,r)
	Q = V[G]
	for для каждой вершины u принадлежащей Q
	{
		key[u] = infinity
	}
	key[r] = 0
	p[r] = NIL
	while (Q != {0})
	{
		u = EXTRACT_MIN(Q)
		for для каждой вершины v принадлежащей Adj[u]
		{
			if v принадлежит Q и ( w(u,v) < key[v])
			{
				p[v] = u;
				key[v] = w(u,v)
			}
		}
	}