Monday, March 16, 2015

Spanning Trees with kruskal algorithm

Tree :   A tree is a connected graph without cycles.

Properties of Trees:  

  • A graph is a tree if and only if there is one and only one path joining any two of its vertices.
  • A connected graph is a tree if and only if every one of its edges is a bridge.
  • A connected graph is a tree if and only if it has N vertices and N; 1 edges.

Definitions :

  • A sub-graph that spans (reaches out to ) all vertices of a graph is called a spanning sub-graph.
  • A sub-graph that is a tree and that spans (reaches out to ) all vertices of the original graph is called a spanning tree.
  • Among all the spanning trees of a weighted and connected graph, the one (possibly more) with the least total weight is called a minimum spanning tree (MST).

Kruskal's Algorithm :

  • Kruskal Algorithm finds the minimal cost of edges between two vertices and forms the tree.
  • The total weight should be minimized
  • Graph should not be looped.
  • Minimal cost should be chosen initially.
Pseudocode :

1 A = ∅
2 foreach v ∈ G.V:
3   MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A

No comments:

Post a Comment