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 <|V|-1 do (Handle edges in E1) · x?x+1 · if Et?{ei} No loop · Et?Et{i}; encounter?encounter+1 · while encounter<|V|-1 do (Handle edges in E2) · x?x+1 · if Et?{ei} No loop · Et?Et{ei}; encounter?encounter+1 · Return Et Example of modified Kruskal Algorithm (www.chegg.com) Using the modified Kruskal algorithm to find the minimum spanning tree for Figure 1. Figure 1. Example tree. Solution: 1) First obtain the array A = {3, 1, 4, 4, 6, 5, 5, 6, 2, 8} by the weight of all the edges from the set of E. 2) Then select 5 as the middle value of X from the array A, then A will be divided into A1 = {1, 3, 4, 4, 2} and A2 = {6, 5, 5, 6, 8} 3) Corresponding edge set E1 = {(b, c) (a, b) (b, f) (c, f) (e, f)}, and E2 = {(a, e) (a, f) (d, f) (c, d) (d, e)} 4) Handle E1: a) Handle edge (b, c) Figure 2. Edge (b, c). b) Handle edge (e, f) Figure 3. Edge (e, f). c) Handle edge (a, b) Figure 4. Edge (a, c) and (f, e). d) Handle edge (b, f) Figure 5. Edge (b, f). 5) Handle E2: A. Handle edge (d, f) Figure 6. Edge (d, f). Thus, Figure 6 is the minimum spanning tree. Comparison between the Classic and the modified Kruskal Algorithm The time complexity for solving the minimum cost spanning tree of classic Kruskal algorithm is O (|E|log|E|). So now we'll find the time complexity of this modified Kruskal algorithm, in the normal case (the value chose in step 1 of the algorithm is not the maximum or minimum value of the costs), |E1| = e1, |E2| = e2, so E1 + E2 = e Its sum of the maximum time cost of the initial construction of the heap: (2 e1 ? loge1 ? 1) + (2 e2 ? loge2 ? 1) The maximum time to rebuild the heap: e1loge1 + e2loge2 Then the time of the two sub sequence overhead in the first step is e. So the maximum total time cost of the modified Kruskal algorithm is, BT1 = e + e + 2(e1 ? 1) loge1 + loge2 ? 2(e2 ? 1) (Under normal circumstances) (www.geeksforgeeks.org) As, the time cost is affected by selection of the value and the arrangement method of edge costs. Thus, the average time cost of the modified Kruskal algorithm is difficult to estimate. Conclusion The modified Kruskal algorithm is an improvement of the simple Kruskal algorithm, compared with the simple Kruskal algorithm. It has a middle value and uses simple Kruskal algorithm for two times. In the extreme case: The modified Kruskal algorithm has a meaningless step of division according to the intermediate value compared with the simple Kruskal algorithm which causes that the time complexity of the modified Kruskal algorithm is greater than the simple Kruskal algorithm. In normal case: The modified Kruskal algorithm's time complexity is less than the simple Kruskal algorithm under normal circumstances. Therefore, we can try to select the appropriate intermediate values to solve the minimum cost spanning tree in real life. It can reduce the cost to a certain extent. Hence, there are many other modifications of Kruskal's algorithm including (Nevalainen's) paper that is an alternative of implementation of Kruskal's minimum spanning tree algorithm and the filter Kruskal's minimum spanning tree algorithm by (Vitaly Osipov). References · Nevalainen, J. K. (n.d.). An alternative implementation of kruskal's minimum spanning tree algorithm. · sciencedirect. (n.d.). sciencedirect.com. Retrieved from sciencedirect.com: https://www.sciencedirect.com/science/article/pii/0167642383900114 · Vitaly Osipov, P. S. (n.d.). The Filter-Kruskal Minimum Spanning Tree Algorithm. · Wikipedia.org. (n.d.). Retrieved from Wikipedia.org: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm · wikipedia.org. (n.d.). wikipedia.org. Retrieved from wikipedia.org: http://en.wikipedia.org/wiki/Minimum_spanning_tree · www.chegg.com. (n.d.). www.chegg.com. Retrieved from www.chegg.com: http://www.chegg.com/homework-help/use-modification-kruskal-s-algorithm-find-maximum-spanning-t-chapter-14.4-problem-36e-solution-9780321867322-exc · www.geeksforgeeks.org. (n.d.). www.geeksforgeeks.org. Retrieved from www.geeksforgeeks.org: https://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/