Greedy Algorithms | Set 5 (Prim's Minimum Spanning Tree (MST)) | GeeksforGeeks

http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
Like Kruskal’s algorithm, Prim’s algorithm is also a Greedy algorithm. It starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.

a spanning tree means all vertices must be connected. So the two disjoint subsets (discussed above) of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.

Algorithms in a Nutshell

Prim’s Algorithm shows how to construct an MST from such a graph by using a Greedy approach in which each step of the algorithm makes forward progress toward a solution without reversing earlier decisions. Prim’s Algorithm grows a spanning tree T one edge at a time until an MST results (and the resulting spanning tree is provably minimum). It randomly selects a start vertex s ∈ v to belong to a growing set S, and it ensures that T forms a tree of edges rooted at s. Prim’s Algorithm is greedy in that it incrementally adds edges to T until an MST is computed. The intuition behind the algorithm is that the edge (u, v) with lowest weight between u ∈ S and v ∈ V-S must belong to the MST. When such an edge (u, v) with lowest weight is found, it is added to T and the vertex v is added to S.

Prim's algorithm
Rather than build a subgraph one edge at a time, Prim's algorithm builds a tree one vertex at a time.
    Prim's algorithm:
    let T be a single vertex x
    while (T has fewer than n vertices)
    {
        find the smallest edge connecting T to G-T
        add it to T
    }
Since each edge added is the smallest connecting T to G-T, the lemma we proved shows that we only add edges that should be part of the MST.

1. 初始化：V_new = {x}，其中x为集合V中的任一节点（起始点），E_new = {}；
2. 重复下列操作，直到V_new = V：
   1. 在集合E中选取权值最小的边（u, v），其中u为集合V_new中的元素，而v则是V中没有加入V_new的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
   2. 将v加入集合V_new中，将（u, v）加入集合E_new中；

https://en.wikipedia.org/wiki/Prim%27s_algorithm

1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
3. Repeat step 2 (until all vertices are in the tree).

http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
1) Create a set mstSet that keeps track of vertices already included in MST.
2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
3) While mstSet doesn’t include all vertices
….a) Pick a vertex u which is not there in mstSet and has minimum key value.
….b) Include u to mstSet.
….c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v
http://www.codebytes.in/2015/06/prims-algorithm-java-implementation.html
Use Prims algorithm for - less nodes, large number of edges
Use Kruskal's algorithm for - more nodes, less edges (http://www.codebytes.in/2015/03/kruskals-algorithm-implementation-in.html)

    static class EDGE{
        int from, to;
        double weight;
        
        EDGE(int f, int t, double w){
            from = f;
            to = t;
            weight = w;
        }
    }
    
    public static ArrayList<EDGE> prims(ArrayList<ArrayList<EDGE>> G){
        if(G.isEmpty())throw new NullPointerException("The Graph is empty");
        
        ArrayList<EDGE> mst = new ArrayList<>();
        PriorityQueue<EDGE> pq = new PriorityQueue<>((EDGE o1, EDGE o2) -> {
            return Integer.compare(o1.weight, o2.weight);

        });
        
        for(EDGE e:G.get(0)){
            pq.add(e);
        } 
        
        boolean[] marked = new boolean[G.size()];
        marked[0] = true;
        while(!pq.isEmpty()){
            EDGE e = pq.poll();
            if(marked[e.from] && marked[e.to])continue;
            marked[e.from] = true;  
            for(EDGE edge:G.get(e.to)){
                if(!marked[edge.to]){
                    pq.add(edge);  
                }
            }
            marked[e.to] = true; 
            mst.add(e);            
        }
        return mst;
    }

Java code from http://codingrecipies.blogspot.com/2013/09/prims-algorithm_8.html
--Not goog at all.

 // Adjacecny list of vertices
 Map<Integer,LinkedList<AdjListNode>> adjList;

 // Heap , containis all those node which have not been included
 TreeMap<Integer,Integer> heap=new TreeMap<Integer,Integer>();

public void PrimeMST(Graph graph) {
  // List to Store MST formed
  Map<Integer,Integer> MSTholder=new TreeMap<Integer,Integer>();

  // initialize heap Except root
  Set<Integer> set=adjList.keySet();

  // Heap Creation for all keys in adjacency list
  for(Integer i:set)
  {
   createHeap(i,INF);
  }

  // Main Algo starts here , all initialisation over
  while(heap.size()!=0)
  {
   int minEdgeVertex=findMin(); // get the vertex with minimum edge in the heap
   heap.remove(minEdgeVertex);  // node removed from heap and its moves to the Set s.

   LinkedList<AdjListNode> list=adjList.get(minEdgeVertex);
   Iterator<AdjListNode> it=list.iterator();
   
   while(it.hasNext())
   {
    AdjListNode node=it.next();
    int vertex=node.dest;

    if( (heap.containsKey(vertex)) && (node.weight < INF))
    {
     heap.put(vertex,node.weight); // decreasing node value
     MSTholder.put(vertex, minEdgeVertex);
    }
   }
  }

  //TODO : uncomment if u wish to print Node of MST
  //printMST(MSTholder);
  long cost =MSTCost(MSTholder);
  System.out.println("Cost is :" + cost);

 } 
 private long MSTCost(Map<Integer,Integer> MSTholder) {
  Set<Map.Entry<Integer,Integer>> set=MSTholder.entrySet();

  long sum=0;
  for (Map.Entry<Integer, Integer> entry :set)
  {

   int key=entry.getKey();
   int value=entry.getValue();
   
   List<AdjListNode> list=adjList.get(value);
   if(list!=null)
   {
    for(int j=0;j<list.size();j++)
    {
     AdjListNode node=list.get(j);
     if((node.dest) == key )
     {
      sum+=node.weight;
     }
    }
   }
  }
  return sum;
 }

void primMST(int graph[V][V])

{

     int parent[V]; // Array to store constructed MST

     int key[V];   // Key values used to pick minimum weight edge in cut

     bool mstSet[V];  // To represent set of vertices not yet included in MST

     // Initialize all keys as INFINITE

     for (int i = 0; i < V; i++)

        key[i] = INT_MAX, mstSet[i] = false;

     // Always include first 1st vertex in MST.

     key[0] = 0;     // Make key 0 so that this vertex is picked as first vertex

     parent[0] = -1; // First node is always root of MST

     // The MST will have V vertices

     for (int count = 0; count < V-1; count++)

     {

        // Pick thd minimum key vertex from the set of vertices

        // not yet included in MST

        int u = minKey(key, mstSet);

        // Add the picked vertex to the MST Set

        mstSet[u] = true;

        // Update key value and parent index of the adjacent vertices of

        // the picked vertex. Consider only those vertices which are not yet

        // included in MST

        for (int v = 0; v < V; v++)

           // graph[u][v] is non zero only for adjacent vertices of m

           // mstSet[v] is false for vertices not yet included in MST

           // Update the key only if graph[u][v] is smaller than key[v]

          if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])

             parent[v]  = u, key[v] = graph[u][v];

     }

     // print the constructed MST

     printMST(parent, V, graph);

}

int minKey(int key[], bool mstSet[])

{

   // Initialize min value

   int min = INT_MAX, min_index;

   for (int v = 0; v < V; v++)

     if (mstSet[v] == false && key[v] < min)

         min = key[v], min_index = v;

   return min_index;

}

http://cs.fit.edu/~ryan/java/programs/graph/Prim-java.html

  4    public static int [] prim (WeightedGraph G, int s) {
  5       final int [] dist = new int [G.size()];  // shortest known distance to MST
  6       final int [] pred = new int [G.size()];  // preceeding node in tree
  7       final boolean [] visited = new boolean [G.size()]; // all false initially
  8 
  9       for (int i=0; i<dist.length; i++) {
 10          dist[i] = Integer.MAX_VALUE;
 11       }
 12       dist[s] = 0;
 13 
 14       for (int i=0; i<dist.length; i++) {
 15          final int next = minVertex (dist, visited);
 16          visited[next] = true;
 17 
 18          // The edge from pred[next] to next is in the MST (if next!=s)
 19 
 20          final int [] n = G.neighbors (next);
 21          for (int j=0; j<n.length; j++) {
 22             final int v = n[j];
 23             final int d = G.getWeight(next,v);
 24             if (dist[v] > d) {
 25                dist[v] = d;
 26                pred[v] = next;
 27             }
 28          }
 29       }
 30       return pred;  // (ignore pred[s]==0!)
 31    }
 32 
 33    private static int minVertex (int [] dist, boolean [] v) {
 34       int x = Integer.MAX_VALUE;
 35       int y = -1;   // graph not connected, or no unvisited vertices
 36       for (int i=0; i<dist.length; i++) {
 37          if (!v[i] && dist[i]<x) {y=i; x=dist[i];}
 38       }
 39       return y;
 40    }

Algorithms in Java, Part 5: Graph Algorithms, Third Edition
Adding a vertex to the MST is an incremental change: To implement Prim’s algorithm, we focus on the nature of that incremental change. The key is to note that our interest is in the shortest distance from each nontree vertex to the tree. When we add a vertex v to the tree, the only possible change for each nontree vertex w is that adding v brings w closer than before to the tree. In short, we do not need to check the distance from w to all tree vertices—we just need to keep track of the minimum and check whether the addition of v to the tree necessitates that we update that minimum.

After adding a new edge (and vertex) to the tree, we have two tasks to accomplish:
Check to see whether adding the new edge brought any nontree vertex closer to the tree.
Find the next edge to add to the tree.

Using a PFS implementation of Prim’s algorithm that uses a heap for the priority-queue implementation, we can compute an MST in time proportional to E lg V.

Proof: The algorithm directly implements the generic idea of Prim’s algorithm (add next to the MST a minimal edge that connects a vertex on the MST with a vertex not on the MST). Each priority-queue operation requires less than lg V steps. Each vertex is chosen with a remove the minimum operation; and, in the worst case, each edge might require a change priority operation. ▪

Priority-first search
Algorithms in a Nutshell

Prim’s Algorithm shows how to construct an MST from such a graph by using a Greedy approach in which each step of the algorithm makes forward progress toward a solution without reversing earlier decisions. Prim’s Algorithm grows a spanning tree T one edge at a time until an MST results (and the resulting spanning tree is provably minimum). It randomly selects a start vertex s ∈ v to belong to a growing set S, and it ensures that T forms a tree of edges rooted at s. Prim’s Algorithm is greedy in that it incrementally adds edges to T until an MST is computed. The intuition behind the algorithm is that the edge (u, v) with lowest weight between u ∈ S and v ∈ V-S must belong to the MST. When such an edge (u, v) with lowest weight is found, it is added to T and the vertex v is added to S.

Prim’s Algorithm for computing the minimum spanning tree for a graph uses a priority queue to store the unvisited vertices in order of their shortest distance to an initial vertex s. During a key step in the algorithm, one must determine whether a given vertex has already been visited. Because the binary heap implementation of the priority queue fails to provide this operation, a separate Boolean array inQueue is maintained to record the status of each vertex. In the same algorithm, a duplicate key array stores the computed distances to avoid having to search again through the priority queue. This extra storage on the order of O(n) is required to ensure the efficient implementation of the algorithm. In most situations, as long as the overhead is O(n), you are going to be safe.

https://www.quora.com/What-is-the-difference-in-Kruskals-and-Prims-algorithm
The basic difference is in which edge you choose to add next to the spanning tree in each step.

In Prim's, you always keep a connected component, starting with a single vertex. You look at all edges from the current component to other vertices and find the smallest among them. You then add the neighbouring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be merged to the current one if we have a connected graph.

In Kruskal's, you do not keep one connected component but a forest. At each stage, you look at the globally smallest edge that does not create a cycle in the current forest. Such an edge has to necessarily merge two trees in the current forest into one. Since you start with N single-vertex trees, in N-1 steps, they would all have merged into one if the graph was connected.

Use Prim's algorithm when you have a graph with lots of edges.
For a graph with V vertices E edges, Kruskal's algorithm runs in O(E log V) time and Prim's algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.
Prim's algorithm is significantly faster in the limit when you've got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.

http://algs4.cs.princeton.edu/43mst/
Lazy implementation. We use a priority queue to hold the crossing edges and find one of minimal weight. Each time that we add an edge to the tree, we also add a vertex to the tree. To maintain the set of crossing edges, we need to add to the priority queue all edges from that vertex to any non-tree vertex. But we must do more: any edge connecting the vertex just added to a tree vertex that is already on the priority queue now becomesineligible (it is no longer a crossing edge because it connects two tree vertices). The lazy implementation leaves such edges on the priority queue, deferring the ineligibility test to when we remove them.
http://algs4.cs.princeton.edu/43mst/LazyPrimMST.java.html

public LazyPrimMST(EdgeWeightedGraph G) {

        mst = new Queue<Edge>();
        pq = new MinPQ<Edge>();
        marked = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)     // run Prim from all vertices to
            if (!marked[v]) prim(G, v);     // get a minimum spanning forest

        // check optimality conditions
        assert check(G);
    }

    // run Prim's algorithm
    private void prim(EdgeWeightedGraph G, int s) {
        scan(G, s);
        while (!pq.isEmpty()) {                        // better to stop when mst has V-1 edges
            Edge e = pq.delMin();                      // smallest edge on pq
            int v = e.either(), w = e.other(v);        // two endpoints
            assert marked[v] || marked[w];
            if (marked[v] && marked[w]) continue;      // lazy, both v and w already scanned
            mst.enqueue(e);                            // add e to MST
            weight += e.weight();
            if (!marked[v]) scan(G, v);               // v becomes part of tree
            if (!marked[w]) scan(G, w);               // w becomes part of tree
        }
    }

    // add all edges e incident to v onto pq if the other endpoint has not yet been scanned
    private void scan(EdgeWeightedGraph G, int v) {
        assert !marked[v];
        marked[v] = true;
        for (Edge e : G.adj(v))
            if (!marked[e.other(v)]) pq.insert(e);
    }
    // check optimality conditions (takes time proportional to E V lg* V)
    private boolean check(EdgeWeightedGraph G) {

        // check weight
        double totalWeight = 0.0;
        for (Edge e : edges()) {
            totalWeight += e.weight();
        }
        if (Math.abs(totalWeight - weight()) > FLOATING_POINT_EPSILON) {
            System.err.printf("Weight of edges does not equal weight(): %f vs. %f\n", totalWeight, weight());
            return false;
        }

        // check that it is acyclic
        UF uf = new UF(G.V());
        for (Edge e : edges()) {
            int v = e.either(), w = e.other(v);
            if (uf.connected(v, w)) {
                System.err.println("Not a forest");
                return false;
            }
            uf.union(v, w);
        }

        // check that it is a spanning forest
        for (Edge e : G.edges()) {
            int v = e.either(), w = e.other(v);
            if (!uf.connected(v, w)) {
                System.err.println("Not a spanning forest");
                return false;
            }
        }

        // check that it is a minimal spanning forest (cut optimality conditions)
        for (Edge e : edges()) {

            // all edges in MST except e
            uf = new UF(G.V());
            for (Edge f : mst) {
                int x = f.either(), y = f.other(x);
                if (f != e) uf.union(x, y);
            }

            // check that e is min weight edge in crossing cut
            for (Edge f : G.edges()) {
                int x = f.either(), y = f.other(x);
                if (!uf.connected(x, y)) {
                    if (f.weight() < e.weight()) {
                        System.err.println("Edge " + f + " violates cut optimality conditions");
                        return false;
                    }
                }
            }

        }

        return true;
    }

Eager implementation. To improve the lazy implementation of Prim's algorithm, we might try to delete ineligible edges from the priority queue, so that the priority queue contains only the crossing edges. But we can eliminate even more edges. The key is to note that our only interest is in the minimaledge from each non-tree vertex to a tree vertex. When we add a vertex v to the tree, the only possible change with respect to each non-tree vertex w is that adding v brings w closer than before to the tree. In short, we do not need to keep on the priority queue all of the edges from w to vertices tree—we just need to keep track of the minimum-weight edge and check whether the addition of v to the tree necessitates that we update that minimum (because of an edge v-w that has lower weight), which we can do as we process each edge in s adjacency list. In other words, we maintain on the priority queue just one edge for each non-tree vertex: the shortest edge that connects it to the tree.

TODO:
http://algs4.cs.princeton.edu/43mst/PrimMST.java.html

Prim's algorithm computes the MST of any connected edge-weighted graph. The lazy version of Prim's algorithm uses space proportional to E and time proportional to E log E (in the worst case) to compute the MST of a connected edge-weighted graph with E edges and V vertices; the eager version uses space proportional to V and time proportional to E log V (in the worst case).
https://en.wikipedia.org/wiki/Prim%27s_algorithm

Minimum edge weight data structure	Time complexity (total)
adjacency matrix, searching	O(|V|2)
binary heap and adjacency list	O((|V| + |E|) log |V|) = O(|E| log |V|)
Fibonacci heap and adjacency list	O(|E| + |V| log |V|)

A simple implementation of Prim's, using an adjacency matrix or an adjacency list graph representation and linearly searching an array of weights to find the minimum weight edge, to add requires O(|V|²) running time. However, this running time can be greatly improved further by using heaps to implement finding minimum weight edges in the algorithm's inner loop.

A first improved version uses a heap to store all edges of the input graph, ordered by their weight. This leads to an O(|E| log |E|) worst-case running time. But storing vertices instead of edges can improve it still further. The heap should order the vertices by the smallest edge-weight that connects them to any vertex in the partially constructedminimum spanning tree (MST) (or infinity if no such edge exists). Every time a vertex v is chosen and added to the MST, a decrease-key operation is performed on all vertices w outside the partial MST such that v is connected to w, setting the key to the minimum of its previous value and the edge cost of (v,w).

Using a simple binary heap data structure, Prim's algorithm can now be shown to run in time O(|E| log |V|) where |E| is the number of edges and |V| is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O(|E| + |V| log |V|), which is asymptotically faster when the graph is dense enough that |E| is ω(|V|), and linear time when |E| is at least |V| log |V|. For graphs of even greater density (having at least |V|^c edges for some c > 1), Prim's algorithm can be made to run in linear time even more simply, by using a d-ary heap in place of a Fibonacci heap.

http://cs.stackexchange.com/questions/13608/mst-prims-algorithm-complexity-why-not-oev-lg-
The book says the total complexity is 

O(VlgV+ElgV)≈O(ElgV)$O(V\lg V+E\lg V)\approx O(E\lg V)$. 

The complexity is derived as follows. The initialization phase costs O(V)$O(V)$. The while$while$ loop is executed ∣∣V∣∣$\left|V\right|$ times. The for$for$ loop nested within the while$while$ loop is executed degree(u)$degree(u)$ times. Finally, the handshaking lemma implies that there are Θ(E)$\mathrm{\Theta }(E)$ implicit DECREASE-KEY’s. Therefore, the complexity is: Θ(V)∗TEXTRACT−MIN+Θ(E)∗TDECREASE−KEY$\mathrm{\Theta }(V)\ast T_{EXTRACT-MIN}+\mathrm{\Theta }(E)\ast T_{DECREASE-KEY}$.

The actual complexity depends on the data structure actually used in the algorithm. Using an array, TEXTRACT−MIN=O(V),TDECREASE−KEY=O(1)$T_{EXTRACT-MIN}=O(V),T_{DECREASE-KEY}=O(1)$, complexity is O(V2)$O(V^2)$ in the worst case.

Using a binary heap, TEXTRACT−MIN=O(logV),TDECREASE−KEY=O(logV)$T_{EXTRACT-MIN}=O(\log V),T_{DECREASE-KEY}=O(\log V)$, complexity is O(ElogV)$O(E\log V)$ in the worst case. Here is why: since E$E$ is at most V2$V^2$, then logE$\log E$ is at most 2logV$2\log V$. Probably, you missed this point.

Using a Fibonacci Heap, TEXTRACT−MIN=O(logV)$T_{EXTRACT-MIN}=O(\log V)$ amortized, TDECREASE−KEY=O(1)$T_{DECREASE-KEY}=O(1)$amortized, complexity is O(E+VlogV)$O(E+V\log V)$ in the worst case.

https://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/graph/Prim.java
Read full article from Greedy Algorithms | Set 5 (Prim’s Minimum Spanning Tree (MST)) | GeeksforGeeks