Please enable JavaScript.

Coggle requires JavaScript to display documents.

Prim's/Kruskal Algorithm - Coggle Diagram

- - - - G = (V,E)
    - - Edges of Minimum Spanning Tree of G
    - - Name of the Nearest Tree Vertex
        
        ∞
        
        Unseen
      - Edge´s weight
        
        Null
  - - - Θ(|V|²)
    - - Θ(|E| log |V|)
- - - - G=(V,E)
    - - Edges of Minimum Spanning Tree of G
    - - Cycle
        
        Don´t add to Et
      - ̶c̶y̶c̶l̶e̶
        
        Add to Et
  - - - Efficiency
        
        find(x),makeset(x) ∈ Θ(1)
        
        union(x,y) ∈ Θ(V²)
      - Union by size
        
        O(n log n)
    - - Efficiency
        
        makeset(x),union(x,y) ∈ Θ(1)
        
        find(x) ∈ Θ(n)
      - Union by size
      - Union by Rank
        
        find(x) ∈ O(n + m log n)
      - Path Compression
- - - - Minimum Spanning Tree Problem