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 :

KRUSKAL(G):
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