Question

2. Calculate the time complexity of applying Kruskal's algorithm in the given graph. Do you observe something specific in this graph? According to your observation generalize the time complexity considering there are V vertices in the graph. [3] (CO2] 5 6 6 8 9 9 5 7 8 8

Answer 1

Kruskal's algorithm is used to find the minimum spanning tree in a given graph,a minimum spanning tree has V-. number of edges where V is the number of edges in the given graph.
Steps of performing it are:
1. All edges need to be sorted in ascending order as per their weight.
2. The least weighted edge is picked and is checked with to see if it forms a cycle.
   If yes, discrad it, else include it
3. Repeat Step 2 until there's no vertice left to be included and V-1 edges have already been included. This takes place with the find minimm and the union operations.

The given graph conatins 6 vertices and 6 edges. So the minimm spanning tree would cntain the 6 vertices and 6-1=5 edges.

Arranging the edges in ascending order, we get

Weight   Source   Destination
    4        7         6
    5        9                 7
    6                4                 9
    7                5          6
    8               6          8
    9               4          5

Picking one edge after the other to check append to the minimum spanning tree if it doesnot form a cycle.

1. 4, include (7-6)
2. 5, include(9-7)
3. 6, include(4-9)
4. 7, include(5-6)
5. 8, include(6-8)
Stop, since all vertices have been covered. and 5 edges have already been included in the spanning tree.

Thus, edge with weight 9, not being included, the minimum spanning tree obtained is:

5 7 4 6 6 9 Сл 7 8

Time complexity: O(ElogE) or O(ElogV). Since sorting of edges takes O(ELogE) time,(applying heapsort or Mergesort) and applying the apply find-union algorithm after going through all the weighted edges, the find and union operations take O(LogV) time in the worst case. So overall complexity of Kruskal's is O(ELogE + ELogV) time or generalising, overall time complexity is O(ElogE) or O(ElogV).

Specific attention can be given to the fact that the graph contains:

1. A pendant vertice

2. If DFS is applied to the original graph, then the edge (7-6) would have been classified asacross edge and not a tree edge.