Data Structures and Algorithms B
  • Introduction
  • Stable Marrage
  • Huffman Codes
    • ABL
    • Implementation
  • Graph Algorithms
    • Connect Component
    • Bipartiteness
    • Strongly Connected Components
      • Implementation
    • Topological Sort
      • Implementation 1
      • Implementation 2
    • Dijkstra’s Shortest Path
    • Minimum Spanning Tree
      • Prims
        • Implementation 1
      • Kruskels
        • Implementation 1
      • Traveling Salesman Problem
    • k-Clustering
    • Dynamic Programming with Trees
      • Implementation 1
      • Implementation 2
    • Disjoint Sets
      • Implementation
    • Eularian Cycle
      • Implementation
    • Hamiltonian Path
      • Implementation
  • Divide and Conquer
    • Merge Sort
    • Integer Multiplication
    • Closest Pair
    • Master Method
  • Dynamic Programming
    • Interval Scheduling
    • Knapsack Problem
  • Network Flow
    • Maximum Network Flow
    • Improvements
    • Image Segmentation
  • String Algorithms
    • Z Algorithm
    • Boyer-Moore
    • Knuth-Morris-Pratt
    • Suffix Trees
      • Naive Implementation
      • Ukkonens Algorithm
        • Implementation
      • Applications
        • Longest Common Substring
        • Longest Palindromic Substring
        • Longest Repeated Substring
  • Randomized Algorithms
    • Bloom Filters
      • Implementation
Powered by GitBook
On this page
  • Properties
  • Applications
  • Kruskels vs Prims

Was this helpful?

  1. Graph Algorithms

Minimum Spanning Tree

PreviousDijkstra’s Shortest PathNextPrims

Last updated 5 years ago

Was this helpful?

A minimum spanning tree is a the minimum amount of edge weights that produce a spanning tree of graph G.

Properties

  • Fully connected component, and any edge remove produces a disconnect

  • Acyclic, and the addition of any edge produces a cycle.

  • N-1 edges (where n = number of nodes)

    • Justification: Every node is connected to at least 1 other node, and 1 edge is used to connect 2 nodes.

  • ∑i=0n\sum_{i=0}^n∑i=0n​ = minimum

Applications

  • Graph point clustering

  • Image segementation

  • Circuit design

Kruskels vs Prims

  • Prims: When you have a lot of edges relative to the number of nodes. E.g. (close to n2n^2n2 - dense graph)

  • Kruskels: When you have a few amount of edges