|
This is a
little different algorithm and a minor diversion of the shortest path algorithm
you can say. In shortest path algorithm, we find the shortest path from
all the vertices to a particular starting vertex. Here, its the shortest
path between each vertex to every other vertex in the graph. Follow the
example given below to understand better.
|
The
least weighing edge is either AD or BC. Well, you can choose any of them.
I choose AD. Add the edge AD to your Spanning Tree.
Now, find
the adjacent edges to A and D. |
| AB
- 2 |
Least
weighing |
| AD - 1 |
Already
in the tree |
| DB - 2 |
Least weighing |
| DE - 3 |
> value |
| DA - 1 |
Already
in the tree |
|
I
add AB to the spanning tree.
So, you have
edges (AD) and (AB) in the tree after this step.
Now, find
the adjacent edges to B. |
| BA - 2 |
Already
in the tree |
| BD - 2 |
>
value |
| BC
- 1 |
Least
weighing |
| BE - 3 |
>
value |
| DB
- 2 |
>
value |
| DE
- 3 |
>
value |
|
Edges
which exist in the tree and form loops are discarded and ones with > value
are considered every time you find the least.
Now, BC is added
to the tree.
Now, find
the adjacent edges to C. |
| CB - 1 |
Already
in the tree |
| CE - 4 |
>
value |
| CF
- 2 |
Least
weighing |
| BD
- 2 |
Forming
a loop |
| BE
- 3 |
>
value |
| DB
- 2 |
Forming
a loop |
| DE
- 3 |
>
value |
|
So,
CF is added to the tree.
Find the adjacent
edges to F. |
| FC
- 2 |
Already
in the tree |
| FE - 3 |
least
weighing |
| CE
- 4 |
>
value |
| BE
- 3 |
least
weighing |
| DE
- 3 |
least
weighing |
|
I add BE to the tree.
Find the adjacent edges to E. |
| EB
- 3 |
Already
in the tree |
| EC
- 4 |
Forming
a loop |
| ED
- 3 |
Forming
a loop |
| EF
- 3 |
Forming
a loop |
| FE
- 3 |
Forming
a loop |
| CE
- 4 |
Forming
a loop |
| DE
- 3 |
Forming
a loop |
|
It means there no more
edges left and that the tree is complete. |
|
The resultant Spanning
Tree with no loops giving you the shortest distance between any two vertices.
|
 |
The algorithm is very comprehensive and
here it is....
Algorithm:-
Step-1: Take
the least weighing edge of the graph and add it to the minimum Spanning
Tree
Step-2: Find
the adjacent edges for the vertices in the spanning tree
Step-3: Find
the least among all those edges
Step-4: Add
that edge to the spanning tree if its not forming a loop in the tree and
that its not already there in the tree.
Step-5: Stop
if all vertices in the Graph have been covered by the Tree else go to step-2
C implementation:-
Please download
the C implementation.
Note:-
You might have
observed and off course it is true to certain extent that depending upon
which vertex you choose when more than one least weighing edges are there
at a stage, your tree may vary.
Related Operations:
Concept --
non-directed, directed and weighted
Adjacency
matrix of a Graph
Linked representation
of a Graph
Traversals
– Depth First & Breadth first Search
Transitive
closure/ Warshall’s algorithm
Shortest
Path Algorithm
Spanning
Tree Algorithm |
|
