MST (Prim's algorithm)

Prim's Algorithm : node(vertex)-based approach(ranking)

 

Pseudo Code

---

F=empty set    // 추가되는 edge 집합

Y=P{v1}    // 추가되는 vertex 집합

while NOT solved yet{

    1. select v in V-Y nearest to Y; // seletion

    2. feasibility test (cycle?)    // 불필요 -> 이미 가지고 있는 노드 집합에서 edge를 만들기 때문에

    ADD v to Y.

    3. if V == Y, then stop/exit.

}

 

// A C program for Prim's Minimum
// Spanning Tree (MST) algorithm. The program is
// for adjacency matrix representation of the graph
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
// Number of vertices in the graph
#define V 5
 
// A utility function to find the vertex with
// minimum key value, from the set of vertices
// not yet included in MST
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;
}
 
// A utility function to print the
// constructed MST stored in parent[]
int printMST(int parent[], int graph[V][V])
{
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}
 
// Function to construct and print MST for
// a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
    // Array to store constructed MST
    int parent[V];
    // Key values used to pick minimum weight edge in cut
    int key[V];
    // To represent set of vertices included in MST
    bool mstSet[V];
 
    // 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.
    // Make key 0 so that this vertex is picked as first vertex.
    key[0] = 0;
    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 the 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, graph);
}
 
// driver program to test above function
int main()
{
    /* Let us create the following graph
        2 3
    (0)--(1)--(2)
    | / \ |
    6| 8/ \5 |7
    | /     \ |
    (3)-------(4)
            9         */
    int graph[V][V] = { { 0, 2, 0, 6, 0 },
                        { 2, 0, 3, 8, 5 },
                        { 0, 3, 0, 0, 7 },
                        { 6, 8, 0, 0, 9 },
                        { 0, 5, 7, 9, 0 } };
 
    // Print the solution
    primMST(graph);
 
    return 0;
}

 

---

Proof of Greedy_algorithm

 

Prim's Theorem : Prim's algo produces MST

Induction : CS에서 많이 사용되는 증명 방법 -> 특히, greedy algo에서 많이 사용

 

(Base) F=empty is promising. (MST를 만들어 낸다.)

(H) Assume : Prim's algo produces MST (MST T=(Y,F))

(Induction) F + next edge (그 다음 생성되는 MST) is MST.

증명과 주장이 반복

Proof on Induction is required --> Lemma.

(technique : proof by contradiction)

Contradiction: NOT - F + next edge (그 다음 생성되는 MST) is MST. 

T=(Y,F) ==> next prim's algo. T(prim)=(Y+v, F+e) MST X.

--> there exist another optimal MST:T(opt)=(Y+v', F+e') MST O

 

summary : edge를 추가했을 때 다른 최적으 경로가 없다는 것을 보여주며 반박.