Please enable JavaScript.

Coggle requires JavaScript to display documents.

Kruskal's , Disjoint subsets and Union-Find Algorithms: - Coggle…

- - - - The algorithm constructs a minimum spanning tree as an expanding sequence of
        subgraphs that are always acyclic but are not necessarily connected on the intermediate stages of the algorithm.
        
        begins by sorting the graph’s edges in nondecreasing order of their weights
        
        Starting with whe empy subgraph:
        
        Scans this sorted list
        
        Add the next edge on the list to the current subgraph if such inclusion does nod create a cycle and simply skipping the edge otherwise
  - - - running time is dominated by the time needed for sorting the edge weights of a given graph
        
        with an
        efficient sorting algorithm
        
        time efficiency of Kruskal’s algorithm will be in
        O(|E| log |E|).
- - - - makeset(x) creates a one-element set {x}. It is assumed that this operation can be applied to each of the elements of set S only once.
        
        The time efficiency of this
        operation is in BigTheta(1)
      - find(x) returns a subset containing x
      - union(x,y) constructs the union of the disjoint subsets Sx and Sy containing x and y,respectively, and adds it to the collection to replace Sx and Sy,which are deleted from it.
        
        The time efficiency of this operation is in BigTheta(n^2)
        
        A simple way to improve the overall efficiency of a sequence of union operations is to always append the shorter of the two lists to the longer one, with ties
        broken arbitrarily.
        
        union by size
        
        Time efficiency is O(n log n + m).
      - Alternatives for implementing this data structure
        
        quick find
        
        optimizes the time efficiency of the find operation
        
        Uses an array indexed by the elements of the underlying set S
        
        The array’s values indicate the representatives of the subsets containing those elements
        
        Each subset is implemented as a linked list
        
        1 more item...
        
        quick union
        
        optimizes the union operation
        
        The time efficiency is n O(n + m log n).
        
        path compression
        
        This modification makes every node
        encountered during the execution of a find operation point to the tree’s root