Kruskal's Algorithm

10 Key excerpts on "Kruskal's Algorithm"

• 

  eBook - ePub

  Quick Reference to Data Structures and Computer Algorithms, A

  An Insight on the Beauty of Blockchain

  • Divya Joseph, Raji Ramakrishnan Nair, Divya Joseph, Alen Joseph(Authors)
  • 2019(Publication Date)
  • BPB Publications

    (Publisher)

  This algorithm is used for finding a minimum spanning tree, by opting the greedy approach. In Kruskal’s algorithm, every node is assumed as an independent tree and connects one node with another, only if the edge forming has the lowest cost compared to all other options available.

  Normally, we follow the steps given below for Kruskal’s algorithm:

  • Edges of graph are sorted on the basis of weights (or costs).
  • We start the process by adding edges with smallest weight or cost to the spanning tree till we get the edge of the largest weight or cost.
  • Only add edges which don’t form a cycle – edges which connect only disconnected components.

  Or, as a simpler explanation:

  Step 1: Remove all loops and parallel edges.

  Step 2: Arrange all the edges in ascending order of cost.

  Step 3: Add edges with least weight.

  Let us take the following graph and see how Kruskal’s method is implemented to find the minimum cost spanning tree:

  Stages in Kruskal’s algorithm to find the minimum cost spanning tree:

  For clarity, Kruskal’s method is written out more formally in the following algorithm. We assume, E is the set of all edges in G. The only functions we wish to perform on this set are as follows: (1) Determine an edge with minimum cost, and (2) Delete this edge Some of the real – life applications of Kruskal’s algorithm are as follows: (1) Landing cables (2) TV Network (3) Tour operations

  Let us describe a problem and then come up with a solution. The problem is named as Pokemon Go -flavored and the problem is mentioned as follows:

  • Imagine, there are 8 Pokestops located in your area and you want to visit all of them.
  • Each Pokestop can be reached via another Pokestop.
  • Every connection has a positive distance ( > 0 ).
  • The sum of the distances of all chosen connections must be minimal.

  Formally:

  The distance of a connection is indicated by ‘d’, which takes as input, two Pokestop IDs; d(1,2) = d(2, 1) = 5

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in Python

  • Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser(Authors)
  • 2013(Publication Date)
  • Wiley

    (Publisher)

  676 Chapter 14. Graph Algorithms 14.7.2 Kruskal’s Algorithm In this section, we introduce Kruskal’s algorithm for constructing a minimum span- ning tree. While the Prim-Jarn ´ ık algorithm builds the MST by growing a single tree until it spans the graph, Kruskal’s algorithm maintains a forest of clusters, repeat- edly merging pairs of clusters until a single cluster spans the graph. Initially, each vertex is by itself in a singleton cluster. The algorithm then considers each edge in turn, ordered by increasing weight. If an edge e connects two different clusters, then e is added to the set of edges of the minimum spanning tree, and the two clusters connected by e are merged into a single cluster. If, on the other hand, e connects two vertices that are already in the same cluster, then e is discarded. Once the algorithm has added enough edges to form a spanning tree, it terminates and outputs this tree as the minimum spanning tree. We give pseudo-code for Kruskal’s MST algorithm in Code Fragment 14.17 and we show an example of this algorithm in Figures 14.22, 14.23, and 14.24. Algorithm Kruskal(G): Input: A simple connected weighted graph G with n vertices and m edges Output: A minimum spanning tree T for G for each vertex v in G do Define an elementary cluster C(v) = {v}. Initialize a priority queue Q to contain all edges in G, using the weights as keys. T = ∅ {T will ultimately contain the edges of the MST} while T has fewer than n − 1 edges do (u, v) = value returned by Q.remove min() Let C(u) be the cluster containing u, and let C(v) be the cluster containing v. if C(u) = C(v) then Add edge (u, v) to T . Merge C(u) and C(v) into one cluster. return tree T Code Fragment 14.17: Kruskal’s algorithm for the MST problem. As was the case with the Prim-Jarn ´ ık algorithm, the correctness of Kruskal’s al- gorithm is based upon the crucial fact about minimum spanning trees from Propo- sition 14.25.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Simulation for Applied Graph Theory Using Visual C++

  • Shaharuddin Salleh, Zuraida Abal Abas(Authors)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Prim’s algorithm and Kruskal’s algorithm are among the prominent methods used to find the minimum spanning tree. Finding the minimum spanning tree is a very com-mon problem as it has many real-world applications. Among these applications are large-scale planning of distribution networks, transportation and communication, data storage reduction, and in data mining. This chapter presents three different projects related to the minimum spanning tree problems: Code 5 A , Code 5 B , and Code 5 C . Code 5 A is the greedy algorithm used to compute the minimum spanning tree using Kruskal’s algorithm, while Code 5 B and Code 5 C are applications of Kruskal’s algorithm for a transportation problem and a broadcasting in ad hoc wireless network problem, respectively. 134 Simulation for Applied Graph Theory Using Visual C++ 5.2 Algorithms for Computing Minimum Spanning Tree The minimum spanning tree problem has its solutions in the form of a greedy algorithm; the most common are Kruskal’s algorithm and Prim’s algorithm. Kruskal’s algorithm focuses on the selection of edges while Prim’s algorithm is based on the selection of nodes. 5.2.1 Kruskal’s Algorithm Kruskal’s algorithm is a greedy algorithm, which is the easiest method for finding the minimum spanning tree of a graph. The idea of Kruskal’s algorithm is to find the mini-mum spanning tree by initially having each node as its own component with no edges. An edge with minimum weight will be added to merge the components or the nodes. This procedure is repeated until all the nodes are connected and become a tree. The selection of the edges continues until the total number of edges becomes n − 1. Note that the selection of the edges during the procedure must not create a cycle. Figure 5.3a through f illustrates the execution of Kruskal’s algorithm. In (a) weight w ij is assigned to the graph G ( V , E ) with V = { v i } and E = { e ij } where i , j = 1, 2,…5.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structure Practice

  for Collegiate Programming Contests and Education

  • Yonghui Wu, Jiande Wang(Authors)
  • 2016(Publication Date)
  • CRC Press

    (Publisher)

  405 Chapter 12 Algorithms of Minimum Spanning Trees A tree is a connected undirected simple graph with no circuit. A tree with n vertices has n – 1 edges. If an edge of a tree is deleted, the tree becomes an unconnected graph. If an edge is added between any two vertices in a tree, a circuit is produced. As mentioned, breadth-first search (BFS) or depth-first search (DFS) for a connected graph will produce a BFS tree or a DFS tree. In this chapter, we focus on finding a spanning tree so that the sum of weights of edges of the tree is minimized in a weighted undirected connected graph. Such a spanning tree is called a minimum spanning tree (MST). The greedy strategy is used to find an MST. That is, at each step, the added edge can’t form a circuit, and based on it, the weight of the added edge should be minimal. Such an added edge is called a safe edge. There are two algorithms of MSTs: 1. Kruskal algorithm 2. Prim algorithm The two algorithms get an MST by different methods. 12.1 Kruskal Algorithm Initially, n vertices constitute a forest. Then, edge ( u , v ) connecting two distinct trees in the forest with the least weight is regarded as the safe edge and is added to the forest. Repeat the process until the MST is obtained. Based on it, given a weighted connected graph G ( V , E ), where | V | = n and | E | = m , Kruskal algorithm is as follows: Sort edges in ascending order of weight values; Suppose initially F is a forest consisting of n trees, and each tree corresponds to a vertex in graph G ; Initially the sum of weights of edges of the minimum spanning tree ans = 0;

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in C++

  • Michael T. Goodrich, Roberto Tamassia, David M. Mount(Authors)
  • 2011(Publication Date)
  • Wiley

    (Publisher)

  The development of efficient algorithms for the minimum spanning tree prob- lem predates the modern notion of computer science itself. In this section, we discuss two classic algorithms for solving the MST problem. These algorithms are both applications of the greedy method, which, as was discussed briefly in the previous section, is based on choosing objects to join a growing collection by itera- tively picking an object that minimizes some cost function. The first algorithm we discuss is Kruskal’s algorithm, which “grows” the MST in clusters by considering edges in order of their weights. The second algorithm we discuss is the Prim-Jarn ´ ık algorithm, which grows the MST from a single root vertex, much in the same way as Dijkstra’s shortest-path algorithm. As in Section 13.5.2, in order to simplify the description of the algorithms, we assume, in the following, that the input graph G is undirected (that is, all its edges are undirected) and simple (that is, it has no self-loops and no parallel edges). Hence, we denote the edges of G as unordered vertex pairs (u, z). Before we discuss the details of these algorithms, however, let us give a crucial fact about minimum spanning trees that forms the basis of the algorithms. 646 Chapter 13. Graph Algorithms A Crucial Fact About Minimum Spanning Trees The two MST algorithms we discuss are based on the greedy method, which in this case depends crucially on the following fact. (See Figure 13.17.) Figure 13.17: The crucial fact about minimum spanning trees. Proposition 13.24: Let G be a weighted connected graph, and let V 1 and V 2 be a partition of the vertices of G into two disjoint nonempty sets. Furthermore, let e be an edge in G with minimum weight from among those with one endpoint in V 1 and the other in V 2 . There is a minimum spanning tree T that has e as one of its edges. Justification: Let T be a minimum spanning tree of G. If T does not contain edge e, the addition of e to T must create a cycle.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Computer Science, Algorithms and Complexity

  • Adele Kuzmiakova(Author)
  • 2020(Publication Date)
  • Arcler Press

    (Publisher)

  3.5. MINIMUM SPANNING TREES iven a networked and undirected graph, the spanning tree is subgraph, which is the tree, connecting together different vertices. One graph may have multiple different spanning trees. The minimum spanning tree (MST) refers to the spanning tree that weighs less than and even equal to densities of different other spanning trees in the network. Additionally, the spanning tree’s weight refers to the amount of weights provided to every spanning tree edge. The edge-weighted graph refers to a graph that associates weights and costs with every edge (Sirmacek, 2018) (Figure 3.3). Computer Science, Algorithms and Complexity 68 Figure 3.3: Kruskal’s algorithm is a popular minimum-spanning tree algorithm. Source: https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algo-rithm-greedy-algo-2/ (accessed on 6 April 2020). 3.5.1. Assumptions There are several important adoptions that must be considered. First, the graph is interconnected. Second, as the name suggests, the graph should be some form of MST. In case a graph isn’t connected, it is possible to adapt the algorithms to calculate the MSTs of every connected component, commonly referred to as the minimum spanning forest. Besides, the edge weights do not necessarily correspond to distance because they can take another different form. Geometric intuition is also sometimes beneficial although the edge weights may be random. The edge weights might be a zero or negative. In case the edge weights read positive, then it suffices to describe the MST as a subgraph having minimal average weight which connects different vertices. All edge weights are different in their own perspective. In case edges have equal weights, then MST might not be special after all. Making this assumption supports some of the already established proofs, even though every algorithm works efficiently even in the existence of equivalent weights (Sirmacek, 2018).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Graphs and Networks

  • S. R. Kingan(Author)
  • 2022(Publication Date)
  • Wiley

    (Publisher)

  ◽ In 1956 Joseph Kruskal described one way of selecting safe edges (Kruskal, 1956). The next year Robert Prim described another way (Prim, 1957). In the case of Kruskal’s algorithm, a forest is grown by starting with the lowest weight edge and at each stage the safe edge selected has lowest weight among available edges anywhere in the graph. In the case of Prim’s algorithm, a tree is grown by starting with a vertex and at each stage the safe edge selected has lowest weight among the neighbors of already visited vertices. Algorithm 5.2.4. Kruskal’s Algorithm Input: A connected graph G = (V , E) and a weight function on the edges. Output: A set of edges that forms a minimum spanning tree. (1) Let A be an empty set of edges. (2) Let m be |E|. (3) Arrange the edges of E into a list in non-decreasing order by weight. (4) For each i = 1, … , m: If the edge e at position i in the list connects two previously disconnected components of G ′ = (V , A): Add e to A. (5) Return A. Consider an edge e added at iteration i of Step 4 in Kruskal’s Algorithm. Let C denote one of the disconnected components of G ′ = (V , A) connected by e, and let S be the set of vertices in V incident with some edge in C. Then no edge in A crosses (S, V − S), e does cross (S, V − S), and because the edges are considered in non-decreasing order by weight, it is a minimum weight edge that does so. There- fore by Theorem 5.2.3, e is a safe edge for A. The complexity of Kruskal’s Algorithm is O(m log n), where m is the number of edges and n is the number of vertices in the input graph. While the algorithm’s main loop is O(m), sorting the edges in non-descending order is an O(m log n) operation ((Cormen et al., 2001), p. 570). Figure 5.2 shows a step-by-step implementation of Kruskal’s algorithm. ● At Step 3, all the edges are sorted in increasing order by weight: [𝑣 3 𝑣 6 , 𝑣 2 𝑣 6 , 𝑣 4 𝑣 5 , 𝑣 1 𝑣 2 , 𝑣 2 𝑣 3 , 𝑣 1 𝑣 6 , 𝑣 5 𝑣 6 , 𝑣 3 𝑣 5 , 𝑣 3 𝑣 4 ].

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Graphs

  Theory and Algorithms

  • K. Thulasiraman, M. N. S. Swamy(Authors)
  • 2011(Publication Date)
  • Wiley-Interscience

    (Publisher)

  326 GRAPH ALGORITHMS 51. Set i = 1 and E 0 = 0. 52. Select an edge e, of minimum weight such that e,&E,_ l and the edge-induced subgraph (E,_iU{e,}) is acyclic, and then define T, = (£,_, U {e,}) and £, = U {e,}. If no such edge exists, then let T m i n = Γ,., and HALT. 53. Set i = i + 1 and go to S2. • Kruskal's Algorithm essentially proceeds as follows. Edges are first sorted in the order of nondecreasing weights and then examined, one at a time, for inclusion in a minimum weight spanning tree. An edge is included if it does not form a circuit with the edges already selected. For an illustration of Kruskal's Algorithm see Section 10.9. Next we prove the correctness of Kruskal's Algorithm. Theorem 11.7. Kruskal's Algorithm constructs a minimum weight spanning tree of a weighted connected graph. Proof. Let G be the given nontrivial weighted connected graph. Clearly, when Kruskal's Algorithm terminates, the edges selected will form a span-ning tree of G. Thus the algorithm terminates with i = n, and T„_ t is a spanning tree of G. We next establish that Γ„_, is indeed a minimum weight spanning tree of G by proving that every 7, constructed in the course of Kruskal's Algorithm is contained in a minimum weight spanning tree of G. Our proof is by induction on /'. Clearly by Theorem 11.5 G contains a minimum weight spanning tree that contains the edge e v In other words T x is contained in a minimum weight spanning tree of G. As inductive hypothesis assume that T„ i s 1 is contained in a minimum weight spanning tree of G. Let G' be the graph obtained by contracting the edges of T r Again, by Theorem 11.5, the edge e i+l is contained in a minimum weight spanning tree T' min of G'. By Theorem 11.6, T, U T' mm is a minimum weight spanning tree of G. More specifically T i+l = T t U {e i+1 } is contained in a minimum weight spanning tree of G and the correctness of Kruskal's Algorithm follows.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Algorithm Design and Applications

  • Michael T. Goodrich, Roberto Tamassia(Authors)
  • 2014(Publication Date)
  • Wiley

    (Publisher)

  C-15.10 Suppose Joseph Kruskal had an evil twin, named Peter, who designed an algo- rithm that takes the exact opposite approach from his brother’s algorithm for find- ing an MST in an undirected, weighted, connected graph, G. Also, for the sake of simplicity, suppose the edges of G have distinct weights. Peter’s algorithm is as follows: consider the edges of G by decreasing weights. For each edge, e, in this order, if the removal of e from G would not disconnect G, then remove e from G. Peter claims that the graph that remains at the end of his algorithm is a minimum spanning tree. Prove or disprove Peter’s claim. C-15.11 Suppose Vojtˇ ech Jarn ´ ık had an evil twin, named Stanislaw, who designed a divide- and-conquer algorithm for finding minimum spanning trees. Suppose G is an undirected, connected, weighted graph, and, for the sake of simplicity, let us further suppose that the weights of the edges in G are distinct. Stanislaw’s al- gorithm, MinTree(G), is as follows: If G is a single vertex, then it just returns, outputting nothing. Otherwise, it divides the set of vertices of G into two sets, V 1 and V 2 , of equal size (plus or minus one vertex). Let e be the minimum-weight edge in G that connects V 1 and V 2 . Output e as belonging to the minimum span- ning tree. Let G 1 be the subgraph of G induced by V 1 (that is, G 1 consists of the 15.5. Exercises 441 vertices in V 1 plus all the edges of G that connect pairs of vertices in V 1 ). Simi- larly, let G 2 be the subgraph of G induced by V 2 . The algorithm then recursively calls MinTree(G 1 ) and MinTree(G 2 ). Stanislaw claims that the edges output by his algorithm are exactly the edges of the minimum spanning tree of G. Prove or disprove Stanislaw’s claim. Applications A-15.1 Suppose you are a manager in the IT department for the government of a corrupt dictator, who has a collection of computers that need to be connected together to create a communication network for his spies.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Introduction To The Analysis Of Algorithms, An (2nd Edition)

  • Michael Soltys-kulinicz(Author)
  • 2012(Publication Date)
  • World Scientific

    (Publisher)

  If it has less than ( n -1) edges, it is certainly not connected, and if it has more than ( n -1) edges, it is certainly not acyclic. We are interested in finding a minimum cost spanning tree for G , as-suming that each edge e is assigned a cost c ( e ). The understanding is that the costs are non-negative real number, i.e., each c ( e ) is in R + . The total cost c ( T ) is the sum of the costs of the edges in T . We say that T is a minimum cost spanning tree (MCST) for G if T is a spanning tree for G and given any spanning tree T 0 for G , c ( T ) ≤ c ( T 0 ). Given a graph G = ( V, E ), where c ( e i ) = “cost of edge e i ,” we want to find a MCST. It turns out, fortuitously, that an obvious greedy algorithm— known as Kruskal’s algorithm—works. The algorithm is: sort the edges in non-decreasing order of costs, so that c ( e 1 ) ≤ c ( e 2 ) ≤ . . . ≤ c ( e m ), and add the edges one at a time, except when including an edge would form a cycle with the edges added already. Greedy Algorithms 41 Algorithm 2.1 Kruskal 1: Sort the edges: c ( e 1 ) ≤ c ( e 2 ) ≤ . . . ≤ c ( e m ) 2: T ←-∅ 3: for i : 1 ..m do 4: if T ∪ { e i } has no cycle then 5: T ←-T ∪ { e i } 6: end if 7: end for But how do we test for a cycle, i.e., execute line 4 in algorithm 2.1? At the end of each iteration of the for-loop, the set T of edges divides the vertices V into a collection V 1 , . . . , V k of connected components . That is, V is the disjoint union of V 1 , . . . , V k , each V i forms a connected graph using edges from T , and no edge in T connects V i and V j , if i 6 = j . A simple way to keep track of V 1 , . . . , V k is to use an array D [ i ] where D [ i ] = j if vertex i ∈ V j . Initialize D by setting D [ i ] ←-i for every i = 1 , 2 , . . . , n . To check whether e i = ( r, s ) forms a cycle within T , it is enough to check whether D [ r ] = D [ s ].

  Sign up to read

  Learn more about book