www.ibooksharing.com
www.csBook-jack.blogspot.com
* programming in C++ , C , Java , HTML , Objective-C , Unix , Javascript , Xcode , iOS , Development , Computer Science and More *
Pages
▼
Friday, March 2, 2012
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 }
Set V(T) = { source } /* initial source with the V1*/ refer to vertex Vk
Set E(T) = { empty } /* initial is null or empty set */ refer to edge (Vj,Vk)
for i=1 to n
minWeight = infinity /* largest number bigger than every number */
for j=1 to n
if Vj is in V(T) then
for k=1 to n
if(Vk is not in T) && (weight[Vj][Vk] < minWeight){
No comments:
Post a Comment