最小生成树

A minimum spanning tree of a weighted, connected graph is a subgraph in which a tree connects all the vertices together and has the minimum weight.

Prime's Algorithm

Prime's algorithm is a greedy algorithm that finds a minimum spanning tree for a undirected graph.

algorithm description

1. Starts from one vertex, select the least weight edge of that vertex;
2. Add a new vertex that connects with the visited vertices with the least weight edge;
3. Repeated until all vertices are visited

time complexity: O(|V|²)

Definition of Edge

class Edge{
    int from;
    int to;
    int weight;
    Edge(int u,int v,int w){
        from=u;
        to=v;
        weight=w;
    }
}

Pseudocode

Input - Weighted, connected Graph G, set v for vertices, set e for edges, starting vertex s
Output - Minimum Spanning Tree 

Prims(G, v, e, s) {
    for i = 0 to v
        visited[i] = false
        
    visited[start] = true
      
    count = 0   // counts vertices visited
    int min = 9999  //to get minimum edge
    for (int i = 0; i < v; i++) {
      if(visited[i]) {
            for (int j = 0; j < v; j++) {
              if (edge between i and j exists and visited[j] is false) {
                  if (min > G[i][j]) {
                      min = G[i][j];
                      x = i;
                      y = j;
                      add edge to Minimum Spanning Tree
                  }
              }
         }
     }
 }

 

Kruskal's Algorithm

algorithm description

1. Sort the graph edges with respect to their weights in increasing order;
2. Add edges to MST with least weight in a single round (make sure the added edges don't form a cycle--adding edges which only connect the disconnected components)

time complexity: O(|E|log|E|)

Pseudocode

MST- KRUSKAL (G, w)
  1. A ← ∅
  2. for each vertex v ∈ V [G]
  3.     do MAKE - SET (v)
  4.     sort the edges of E into non decreasing order by weight w
  5. for each edge (u, v) ∈ E, taken in non decreasing order by weight
  6.     do if FIND-SET (μ) ≠ if FIND-SET (v)
  7.     then A  ←  A ∪ {(u, v)}
  8.     UNION (u, v)
  9. return A