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){
endVertex =
Vk
edge = (
Vj
,
Vk
)
minWeight = weight[
Vj
][
Vk
]
V(T) = V(T) or { endVertex }
V(E) = V(E) or { edge }
No comments:
Post a Comment