Data Structure and Algorithm - Graph - Minimal Spanning Tree - Definition


A (Free) tree T is sample graph such that if u and v are two vertex in T, then there is a unique path from to v. A tree in which a particular vertex is designed as a root called a rooted tree.
If a weight is assigned to the edges in T, T is called a Weighted Tree. If T is a weighted tree, the weight of T denote by W(T), is the sum of the weight of all the edges in T.
A tree T is called a Spanning Tree fo graph G if T is a sub-graph of G such that V(T) = V(G) ( means the number of vertices in T equal to number of vertices in G ), that is all t the vertices of G are in T.

Theorem : A graph G has a spanning if an only if G is connected.
From this theorem it follow in order to determine must be connected.

Let G be a weighted graph. A Minimal Spanning Tree of G is a spanning tree with minimum weight.

Algorithm :


---

V(G) = { V1 , V2 , V3 .... Vn } 

1. Set V(T) = { source } /* initial source with the V1*/    refer to vertex Vk
2. Set E(T) = { empty }  /* initial is null or empty set */ refer to edge (Vj,Vk)
3. for i=1 to n
1. minWeight = infinity /* largest number bigger than every number */
2. for j=1 to n
1. if Vj is in V(T) then
1. for k=1 to n 
1. if(Vk is not in T) && (weight[Vj][Vk] < minWeight){
1. endVertex = Vk
2. edge = (Vj,Vk)
3. minWeight = weight[Vj][Vk] 
3. V(T) = V(T) or { endVertex }
4. V(E) = V(E) or { edge }

---