Minimum spanning tree and prim's algorithm to find minimum spanning tree.
Spanning tree of a graph is just a sub graph that contains all the vertices and is a tree.A graph may have many spanning trees.Any undirected graph has a minimum spanning tree forest.
Minimum Spanning tree
A minimum spanning tree is then a spanning tree with weight less than or equal to the weight less than or equal to the weight of every other spanning tree.
Minimum spanning tree would be in the design of a network.That is useful for finding airline routes.
Prim's Algorithm
That is greedy algorithm to find minimum spanning tree. Begin with some vertex v in a given graph G=(V,E) defining the initial set of vertices.Then in each iteration we choose a minimum weight edge(u,v) connecting a vertex v in the set A to the vertex u outside of set A.Then vertex u is brought in to A.This process is repeated until a spanning tree is formed.
- Initialize Minimum spanning tree with randomly chosen vertex.
- Find all the edges that connect the tree.Select minimum edge and add it to the tree.
- Repeat step until the minimum spanning tree is formed.
Algorithm
Step 1: Select a starting vertex .
Step 2: Repeat step 3 and 4 until there are fringe vertices.
Step 3: Select an edge e connecting the tree vertex and fringe.
Step 4: Add the selected edge and the vertex to the minimum spanning tree T.
Step 5 : Exit.
Example
Find minimum spanning tree using prim's algorithm of graph G.
Solution
Take node A
Adjacent edge of node A is
AB
Add edge AB in spanning tree
Next adjacent edge is BC
Next adjacent edge is CD
Add edge CD in spanning tree
Discard edge DA because that create cycle and in spanning tree cycle is not allowed.
Cost of spanning tree is =2+1+3=6
0 Comments