Lalaen Sultan

MSCS (Session: 2017 – 2019)

Department of Computer Science

Lahore College for Women University, Lahore

Abstract:

Minimum cost spanning tree has a popular issue to solve it in a concise and accelerated way. In this assignment, we first discussed the basic idea of Kruskal algorithm and then presented a suggested and modified algorithm. This version of Kruskal algorithm is modified to choose a middle value and to reduce the time complexity. So we find out that modified Kruskal algorithm is more convenient and effective in most cases.

1. Introduction

The problem of minimum spanning tree is to select the best path that has least cost. Kruskal algorithm finds an edge of the least possible weight that connects any two trees within all forest. Actually Kruskal is greedy algorithm that finds a MST for a connected weighted graph by adding the increasing cost arcs at each step. It finds a set of the edges that forms a tree which includes every vertex in a way that the total weight of all the edges in the tree is minimized. (wikipedia)

Kruskal algorithm was designed in a way that it can choose n ? 1 edges one time, and then it apply the greedy technique of choosing one edge with minimum cost, but it shouldn’t form any cycle to join the set which was selected.

In assignment 1, there is a complete analysis of simple Kruskal algorithm. We calculated that its time complexity for solving the minimum cost spanning tree is O (|E| log |E|). (Wikipedia)

· At first A= ? and each vertex is in its each connected component. It will merge two components into one by choosing the light edge between them.

· The edges E are maintained as a min heap. The next edge can be obtained or deleted in O (log E) time if G has E edges.

· It requires O (E log E) for sorting the edges. And O (E) time to traverse the sorted edges. Then requires O (V log V) time for each Union-find operation.

2. Modified versions of Kruskal algorithm

Here, we will discuss the modified versions of Kruskal algorithm that are two way Kruskal Algorithm. Modified Kruskal Algorithm has reduced the time complexity of O (|E| log |E|). (sciencedirect)

Modified Kruskal Algorithm

When we solve minimum cost spanning tree, the minimum heap was established, the adjacency matrix was needed to be detected and we calculated the time efficiency as O (n2). After that heap insert operation is applied for x times, and every time call stack algorithm was needed to insert operation, then time efficiency of heap insert operation is O (|E|log2|E|). So, we need a minimum cost spanning tree to call stack the output heap operation, then the simple minimum cost spanning tree’s Kruskal algorithm time complexity is O (|E|log|E|). A new modified algorithm has been proposed.

The Basic Ideas of modified Kruskal Algorithm

After the modified Kruskal algorithm was studied and analyzed, here are the basic ideas of this algorithm:

1) It is supposed that a connected graph, G = {V, E} with n vertexes and a non-connected graph without vertex T = {V, ?}. The cost of all the edges in graph G is an array A at first, and select a cost K as an intermediate value, then array A is divided into two parts, A1 & A2. Whereas in A1, there will be all the costs that are less than the middle value k and in A2, there will be all the costs that are greater than the middle x. Then, we will obtain the edge set E1 corresponding to A1 and the edge set E2 corresponding to A2.

2) Then, the vertex set is divided into n equivalent classes, as the total number of the equivalent classes is n = E1 + E2, each equivalent class contains a vertex.

3) In graph G1 = {V, E1}, one can deal with each edge by ascending order of cost, if one edge connects two different equivalent classes, then this edge will be added to T, and the two equivalent classes will be merged into the same class at once.

4) The previous operation will be repeated until each edge of the E1 has been considered. Then, the total number of the equivalent classes is 1 + E2 for graph G= {V, E}, and deal with all edges E2 in G2= {V, E2} again, if one edge connects to the vertexes of two different equivalent classes in graph G, the edge will be added to T, and the two equivalent classes a remerged into the same equivalent class at the same time immediately.

5) This previous operation will be performed repeatedly until each edge of the E2 has been considered. At the end, the total number of the equivalent classes is 1 for the graph G = {V, E} at this time, so that you obtained minimum cost spanning tree of graph G.

The Procedure of the modified Kruskal Algorithm (G)

So here is the modified Kruskal algorithm for constructing minimum spanning tree:

· Take input weighted connected graph G=, intermediate value X.

· Output as Et, is edge collection of minimum spanning tree that are composed of G

· Then select an intermediate value X from the set E

· The E is divided into E1 composed by the edge whose weight is less than X and E2 composed by the edge whose weight is more than or equal to X, Then we’ll sort the collection E1 according to the non-decreasing order of the weight w (e1) of the edge.

· Et?Ø; encounter?0

(We’ll initialize the vertex set of the tree and the size of the collection)

· x?0

(Then initialize the number of initialized edges)

· while encounter