Kruskal

Given a connected and undirected graph, a _spanning tree _of that graph is a subgraph that is a tree and connects all the vertices together.

A _minimum spanning tree (MST) _or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree.

The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.

Workflow of Kurskal method:

1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge.
3. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
4. Repeat step above until there are (V-1) edges in the spanning tree.

After sorting:

Weight   Src    Dest
1         7      6
2         8      2
2         6      5
4         0      1
4         2      5
6         8      6
7         2      3
7         7      8
8         0      7
8         1      2
9         3      4
10        5      4
11        1      7
14        3      5

How to detect cyclical vertex?

There is an algorithm called Union-Find.