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
  • High Level Algorithm
  • Data Structures
  • Differences with Kruskal's
  • Time Complexity

Was this helpful?

  1. Graph Algorithms
  2. Minimum Spanning Tree

Prims

High Level Algorithm

  1. Start with an arbitrary vertex. Mark it as known.

  2. Note all the vertices that extend from starting vertex. Select the next adjacent vertex that has the lowest cost relative (not cumulative); and will not create a cycle upon connection. Mark this vertex as known.

  3. Note the next possible connections of all the known vertex and select the next lowest vertex, such that it does not create a cycle.

  4. See 3. Stop once all nodes have at least one edge connected to it.

Data Structures

  • Minimum Binary Heap, or priority_queue. This will allow us to both efficiently insert elements into the graph when we discover a new node, as well as retrieve the next minimum Graph node to incorporate into the MST.

Differences with Kruskal's

  • Does not pick globally minimum vertex. Rather it only looks at the edges that were already introduced by the already visited vertices.

  • Doesn't begin with a distinguished vertex per say, because prims may generate different minimum spanning trees depending on what vertex it starts.

Time Complexity

  • O(nlogn)O(nlogn)O(nlogn) or more precisely O(VELog(V))O(VELog(V))O(VELog(V))

  • Priority Queue insertions will operate O(V) times, since we pop from the queue at most once for all the vertices of the graph.

  • Per each pop, we scan through the adjacenct elements of a particular vertecy possible update an edge weight. This is will be proportional to the number of edges E.

PreviousMinimum Spanning TreeNextImplementation 1

Last updated 5 years ago

Was this helpful?