# 6.4.2. Kruskal’s Algorithm vs Prim’s Algorithm (Greedy!)

ref. Courtesy of T. Cormen et al.

Kruskal’s algorithm
- In each step, find and add an edge of the least possible weight that connects any two trees in the (current) forest.
Prim’s algorithm
- In each step, find and add an edge of the least possible weight that connects the (current) tree to a non-tree vertex.

# Generic MST Algorithm and its Correctness

Generic algorithm for a graph G = (V, E) with a weight function w
- For an edge set A that is a subset of some MST, an edge (u, v) is called a safe edge for A if A \cup \{(u, v)\} is also a subset of some MST.
- Loop invariant for a set of edges A • Prior to each iteration, A is a subset of some minimum spanning tree.
```
Generic-MST(G) {
    A := empty; 
    // A: a set of edges of G 
    While (A does not form a spanning tree) {
        Find and edge (u, v) that is safe for A;
        A := A  {(u, v)}; 
    }
}
```
Some definitions

Courtesy of T. Cormen et al.
- A cut (S, V-S) of G is a partition of V.
- An edge (u, v) of G crosses a cut (S, V-S) if u \in S and v \in V-S→cut-set.
- A cut respects a set A of edges if no edge in A crosses the cut.
- An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.

# Cut Property

For any cut C of the graph, if the weight of an edge e in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.
Proof:
- Assume that there is an MST T that does not contain e.
- Adding e to T will produce a cycle, that crosses the cut once at e and crosses back at another edge e'.
- Deleting e' we get a spanning tree T∖\{e'\} \cup \{e\} of strictly smaller weight than T. This contradicts the assumption that T was a MST.
By a similar argument, if more than one edge is of minimum weight across a cut, then each such edge is contained in some minimum spanning tree.

Generic-MST(G) {
  A := empty; 
  // A: a set of edges of G 
  While (A does not form a spanning tree) {
    Find and edge (u, v) that is safe for A;
    A := A ∪  {(u, v)}; 
  }
}

Loop invariant for the set A
- Prior to each iteration, A is a subset of some minimum spanning tree.
Theorem
- Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E.
- Let A be a set of E that is included in some minimum spanning tree for G, let (S, V-S) be any cut of G that respects A, and let (u, v) be a light edge crossing (S, V-S). Then, edge (u, v) is safe for A.

# Selection of Next Edge: Kruskal’s Algorithm

In each step, find and add an edge of the least possible weight that connects any two trees in the (current) forest.

Generic-MST(G) {
  A := empty; 
  // A: a set of edges of G 
  While (A does not form a spanning tree) {
    Find and edge (u, v) that is safe for A;
    A := A ∪ { (u, v) }; 
  }
}

# Selection of Next Edge: Prim’s Algorithm

In each step, find and add an edge of the least possible weight that connects the (current) tree to a non-tree vertex.

Generic-MST(G) {
  A := empty; // A: a set of edges of G 
  While (A does not form a spanning tree) {
    Find and edge (u, v) that is safe for A;
    A := A ∪ { (u, v) }; }
}

Theorem
- Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a set of E that is included in some minimum spanning tree for G, let (S, V-S) be any cut of G that respects A, and let (u, v) be a light edge crossing (S, V-S). Then, edge (u, v) is safe for A.

# Kruskal’s Minimum Spanning Tree Algorithm

Idea
- Finds an edge of the least possible weight that connects any two trees in the forest.

Implementation using disjoint-set data structure

KRUSKAL(G):
A = 0
foreach v in G.V:
 MAKE-SET(v)
foreach (u,v) in G.E ordered by weight (u,v), increasing:
 if FIND-SET(u) != FIND-SET(v):
   A = A ∪ {(u,v)}
   UNION (u,v)
return

매 단계 forest를 어떻게 관리할 것인가?
두 tree를 어떻게 병합할 것인가?
매 단계 $(u, v)$를 어떻게 선택할 것인가?

Complexity
- Sort the edges by weight: O(E \log E)
- Process the edges until a tree is built: O(E \log V)
- O(E \log E + E \log V) = O(E \log V)
  - why?
- 0 \leq E \leq O(V^2), \log E \leq \log V^2

# An implementation of the Kruskal’s algorithm

geeksforgeeks

// C++ program for Kruskal's algorithm
// to find Minimum Spanning Tree of a
// given connected, undirected and weighted
// graph
#include <bits/stdc++.h>
using namespace std;

// a structure to represent a
// weighted edge in graph
class Edge {
public:
  int src, dest, weight;
};

// a structure to represent a connected,
// undirected and weighted graph
class Graph {
public:
  
  // V-> Number of vertices, E-> Number of edges
  int V, E;

  // graph is represented as an array of edges.
  // Since the graph is undirected, the edge
  // from src to dest is also edge from dest
  // to src. Both are counted as 1 edge here.
  Edge* edge;
};

// Creates a graph with V vertices and E edges
Graph* createGraph(int V, int E)
{
  Graph* graph = new Graph;
  graph->V = V;
  graph->E = E;

  graph->edge = new Edge[E];

  return graph;
}

// A structure to represent a subset for union-find
class subset {
public:
  int parent;
  int rank;
};

// A utility function to find set of an element i
// (uses path compression technique)
int find(subset subsets[], int i)
{
  // find root and make root as parent of i
  // (path compression)
  if (subsets[i].parent != i)
    subsets[i].parent
      = find(subsets, subsets[i].parent);

  return subsets[i].parent;
}

// A function that does union of two sets of x and y
// (uses union by rank)
void Union(subset subsets[], int x, int y)
{
  int xroot = find(subsets, x);
  int yroot = find(subsets, y);

  // Attach smaller rank tree under root of high
  // rank tree (Union by Rank)
  if (subsets[xroot].rank < subsets[yroot].rank)
    subsets[xroot].parent = yroot;
  else if (subsets[xroot].rank > subsets[yroot].rank)
    subsets[yroot].parent = xroot;

  // If ranks are same, then make one as root and
  // increment its rank by one
  else {
    subsets[yroot].parent = xroot;
    subsets[xroot].rank++;
  }
}

// Compare two edges according to their weights.
// Used in qsort() for sorting an array of edges
int myComp(const void* a, const void* b)
{
  Edge* a1 = (Edge*)a;
  Edge* b1 = (Edge*)b;
  return a1->weight > b1->weight;
}

// The main function to construct MST using Kruskal's
// algorithm
void KruskalMST(Graph* graph)
{
  int V = graph->V;
  Edge result[V]; // Tnis will store the resultant MST
  int e = 0; // An index variable, used for result[]
  int i = 0; // An index variable, used for sorted edges

  // Step 1: Sort all the edges in non-decreasing
  // order of their weight. If we are not allowed to
  // change the given graph, we can create a copy of
  // array of edges
  qsort(graph->edge, graph->E, sizeof(graph->edge[0]),
    myComp);

  // Allocate memory for creating V ssubsets
  subset* subsets = new subset[(V * sizeof(subset))];

  // Create V subsets with single elements
  for (int v = 0; v < V; ++v)
  {
    subsets[v].parent = v;
    subsets[v].rank = 0;
  }

  // Number of edges to be taken is equal to V-1
  while (e < V - 1 && i < graph->E)
  {
    // Step 2: Pick the smallest edge. And increment
    // the index for next iteration
    Edge next_edge = graph->edge[i++];

    int x = find(subsets, next_edge.src);
    int y = find(subsets, next_edge.dest);

    // If including this edge does't cause cycle,
    // include it in result and increment the index
    // of result for next edge
    if (x != y) {
      result[e++] = next_edge;
      Union(subsets, x, y);
    }
    // Else discard the next_edge
  }

  // print the contents of result[] to display the
  // built MST
  cout << "Following are the edges in the constructed "
      "MST\n";
  int minimumCost = 0;
  for (i = 0; i < e; ++i)
  {
    cout << result[i].src << " -- " << result[i].dest
      << " == " << result[i].weight << endl;
    minimumCost = minimumCost + result[i].weight;
  }
  // return;
  cout << "Minimum Cost Spanning Tree: " << minimumCost
    << endl;
}

// Driver code
int main()
{
  /* Let us create following weighted graph
      10
    0--------1
    |  \     |
   6|    5\  |15
    |      \ |
    2--------3
      4 */
  int V = 4; // Number of vertices in graph
  int E = 5; // Number of edges in graph
  Graph* graph = createGraph(V, E);

  // add edge 0-1
  graph->edge[0].src = 0;
  graph->edge[0].dest = 1;
  graph->edge[0].weight = 10;

  // add edge 0-2
  graph->edge[1].src = 0;
  graph->edge[1].dest = 2;
  graph->edge[1].weight = 6;

  // add edge 0-3
  graph->edge[2].src = 0;
  graph->edge[2].dest = 3;
  graph->edge[2].weight = 5;

  // add edge 1-3
  graph->edge[3].src = 1;
  graph->edge[3].dest = 3;
  graph->edge[3].weight = 15;

  // add edge 2-3
  graph->edge[4].src = 2;
  graph->edge[4].dest = 3;
  graph->edge[4].weight = 4;

  // Function call
  KruskalMST(graph);

  return 0;
}

// This code is contributed by rathbhupendra

# Prim’s Minimum Spanning Tree Algorithm

Idea
- In each step, find and add an edge of the least possible weight that connects the (current) tree to a non-tree vertex.

Algorithm

Given G = (V, E),
Begin with a tree T0 = (V0, E0) where V0 = {v1} and E0 = {}. 
repeat { 
  // Ti = (Vi, Ei)→Ti+1 = (Vi +1, Ei +1)
  Select a vertex v in V - Vi that is nearest to Vi. 
    // Let v is from the edge (u, v), where u in Vi.
    Update T in such a way that
      Vi +1 = Vi + {v}, and Ei +1 = Ei + {(u, v)}.
until (an MST is found)

A key issue in implementation
- Tree vertices와 non-tree vertices들을 어떻게 관리할 것인가?
- Tree vertices와 non-tree vertices들 간의 최소 비용 edge를 어떻게 (효율적으 로) 찾을 것인가?
From Prof. Kenji Ikeda's Home Page

# Inductive Description of the Prim’s Algorithm

$ V={ v_0,v_1,v_2,...,v_ }with|V| = n$
T^k →T^{k+1}
- 매번 가장 비용이 낮은 fringe edge를 선택하여 T^k 로 옮긴 후 그에 따른 처리를 함.

# An O(n^2) Implementation: Adjacency Matrix 사용

a = 0, b = 1, c = 2, d = 3, e = 4, \\f = 5, g = 6, h = 7, i = 8, j = 9
st[i]: T로 선택된 vertex i의 parent vertex 번 호 저장
fr[i]: NT에 있는 vertex i에서 T에 있는 vertex 중 가장 가까운 vertex의 번호
wt[i]: NT에 있는 vertex i에 대해 그 vertex 에서 fr[i]까지의 거리

n=|V|

static int fr[maxV];
#define P G->adj[v][w]
void GRAPHmstV(Graph G, int st[], double wt[])
{

    int v, w, min, n = G->V;
    for (v = 0; v < n; v++)
    {

        st[v] = -1;
        fr[v] = v;
        wt[v] = maxWT;
    }

    wt[n] = maxWT;

    // wt[n] : dummy vertex, maxWT: dummy weight
    // 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.
    for (min = 0; min != n;){            
      //언제 끝날까?
        v = min; //다음으로 선택된 vertex 번호
        st[min] = fr[min];
        for (w = 0, min = n; w < n; w++)
//아직 선택되지 않은 모든 vertex w에 대해, v = min이 선택된 것에 대한 update 수행
            if (st[w] == -1)
            {
                if (P < wt[w])
                {
                    wt[w] = P;
                    fr[w] = v;
                }
                if (wt[w] < wt[min])
                    min = w;
//wt[w]를 update하면서, 동시에 가장 작은 wt 값을 가지는 vertex 번호 min을 계산
            }
    }
}

모든 계산이 끝난 후 wt[i]는 어떤 정보를 가지고 있을까?

# An O(e \log n) Implementation: Adjacency List 사용

n = | V |, e = | E |

Observations
- The inner for-loop in the O(n^2) implementation visits all the vertices to update wt[] array and to find the minimum.
- An O(e \log n) time implementation is possible.
  - If the graph is dense, n^2 \log n
  - If the graph is sparse, n \log n
- 0 \leq e \leq \frac{n(n-1)}{2}, O(n) \leq e\sim \frac {n^2}{\log n} \leq O(n^2)
We need to employ the priority queue that allows
- to insert a new item (PQinsert(w))
- to delete the minimum item (w = PQdelmin())
- to change the priority of an arbitrary specified item (PQdec(w)).

typedef struct node *link;
struct node
{
    int v;
    double wt, link next;
};

struct graph
{
    int V;
    int E;
    link *adj;
};

typedef struct graph *Graph;
#define GRAPHpfs GRAPHmst static int fr[maxV];
static double *priority;
// Put the priority queue codes here. #define P t->wt

void GRAPHpfs(Graph G, int st[], double wt[]){
    link t;
    int v, w;
    PQinit();
    priority = wt;

    for (v = 0; v < G->V; v++){
        st[v] = -1;
        fr[v] = -1;
    }
    fr[0] = 0;
    PQinsert(0 **) * *;
    while (!PQempty()){
      v = PQdelmin();
      st[v] = fr[v];
      for (t = G->adj[v]; t != NULL; t = t->next){
        if (fr[w = t->v] == -1){
          wt[w] = P;
          PQinsert (w);
          fr[w] = v;
        }
        else if ((st[w] == -1) && (P < wt[w])){
          wt[w] = P;
          PQdec (w);
          fr[w] = v;
        }
      }
    }
}

alg