prim.c File Reference

Prim's algorithm implementation in C to find the MST of a weighted, connected graph. More...

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <inttypes.h>

Include dependency graph for prim.c:

Macros
#define	MAX   20
	for IO operations
#define	INF   999

Functions
uint16_t	minimum (uint16_t arr[], uint16_t N)
	Finds index of minimum element in edge list for an arbitrary vertex.
void	prim (uint16_t G[][MAX], uint16_t MST[][MAX], uint16_t V)
	Used to find MST of user-generated adj matrix G.
static void	test (uint16_t G[][MAX], uint16_t MST[][MAX], uint16_t V)
	Self-test implementations.
void	user_graph (uint16_t G[][MAX], uint16_t MST[][MAX], uint16_t V)
	Function user_graph(); gets user input adj.
int	main (int argc, char const *argv[])
	Main function.

Detailed Description

Prim's algorithm implementation in C to find the MST of a weighted, connected graph.

Author

Timothy Maloney

Prim's algorithm uses a greedy approach to generate the MST of a weighted connected graph. The algorithm begins at an arbitrary vertex v, and selects a next vertex u, where v and u are connected by a weighted edge whose weight is the minimum of all edges connected to v. @references Page 319 "Introduction to the Design and Analysis of Algorithms" - Anany Levitin

To test - run './prim -test' prim() will find the MST of the following adj. matrix:

0 1 2 3 1 0 4 6 2 4 0 5 3 6 5 0

The minimum spanning tree for the above weighted connected graph is given by the following adj matrix:

0 1 2 3 1 0 0 0 2 0 0 0 3 0 0 0

The following link provides a visual representation of graphs that can be used to test/verify the algorithm for different adj matrices and their weighted, connected graphs.

Macro Definition Documentation

MAX

#define MAX   20

for IO operations

for string comparison for assert() for uint16_t

Function Documentation

main()

int main	(	int	argc,
		char const *	argv[]
	)

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored)

Returns

0 on exit

< weighted, connected graph G

< adj matrix to hold minimum spanning tree of G

< number of vertices in V in G

{   
 
    uint16_t G[MAX][MAX];    ///< weighted, connected graph G
    uint16_t MST[MAX][MAX];  ///< adj matrix to hold minimum spanning tree of G
    uint16_t V;              ///< number of vertices in V in G
 
 
    if(argc == 2 && strcmp(argv[1],"-test") == 0)
    {
      test(&(*G),&(*MST),V);
    }
    else
    {
      user_graph(&(*G),&(*MST),V);
    }
 
    return 0;
}

Here is the call graph for this function:

minimum()

uint16_t minimum	(	uint16_t	arr[],
		uint16_t	N
	)

Finds index of minimum element in edge list for an arbitrary vertex.

Parameters

arr	graph row
N	number of elements in arr

Returns

index of minimum element in arr

{
    uint16_t index = 0;
    uint16_t min = INF;
 
    for (uint16_t i = 0; i < N; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
            index = i;
        }
    }
    return index;
}

prim()

void prim	(	uint16_t	G[][MAX],
		uint16_t	MST[][MAX],
		uint16_t	V
	)

Used to find MST of user-generated adj matrix G.

Returns

void

{
    uint16_t u, v;
    uint16_t E_t[MAX], path[MAX];
    uint16_t V_t[MAX], no_of_edges;
 
    E_t[0] = 0;  // edges for current vertex
    V_t[0] = 1;  // list of visited vertices
 
    for (uint16_t i = 1; i < V; i++)
    {
        E_t[i] = G[i][0];
        path[i] = 0;
        V_t[i] = 0;
    }
 
    no_of_edges = V - 1;
 
    while (no_of_edges > 0)
    {
        u = minimum(E_t, V);
        while (V_t[u] == 1)
        {
            E_t[u] = INF;
            u = minimum(E_t, V);
        }
 
        v = path[u];
        MST[v][u] = E_t[u];
        MST[u][v] = E_t[u];
        no_of_edges--;
        V_t[u] = 1;
 
        for (uint16_t i = 1; i < V; i++)
        {
            if (V_t[i] == 0 && G[u][i] < E_t[i])
            {
                E_t[i] = G[u][i];
                path[i] = v;
            }
        }
    }
}

Here is the call graph for this function:

test()

static void test ( uint16_t  G[][MAX], uint16_t  MST[][MAX], uint16_t  V  )

static

Self-test implementations.

Returns

void

{
 
  uint16_t test[4][4] = {{0,1,2,3},{1,0,4,6},{2,4,0,5},{3,6,5,0}};
  uint16_t solution[4][4] = {{0,1,2,3},{1,0,0,0},{2,0,0,0},{3,0,0,0}};
 
  V = 4;
 
  for(uint16_t i = 0; i < V; ++i)
  {
    for(uint16_t j = 0; j < V; ++j)
    {
      G[i][j] = test[i][j];
    }
  }
 
  prim(&(*G),&(*MST),V);
 
  for(uint16_t i = 0; i < V; ++i)
  {
    for(uint16_t j = 0; j < V; ++j)
    {
      assert(MST[i][j] == solution[i][j]);
    }
  }
}

Here is the call graph for this function:

user_graph()

void user_graph	(	uint16_t	G[][MAX],
		uint16_t	MST[][MAX],
		uint16_t	V
	)

Function user_graph(); gets user input adj.

matrix and finds MST of that graph

Returns

void

{
      printf("Enter the number of vertices: ");
      scanf(" %hd", &V);
 
      assert(V <= MAX);
 
      printf("Enter the adj matrix\n");
      uint16_t i, j;
      for (i = 0; i < V; ++i)
      {
          for (j = 0; j < V; ++j)
          {
              printf("G[%d][%d]: ", i, j);
              scanf(" %hd", &G[i][j]);
              if (G[i][j] == 0)
                  G[i][j] = INF;
          }
      }
 
      prim(&(*G),&(*MST),V);
 
      printf("minimum spanning tree:\n");
      for (i = 0; i < V; ++i)
      {
          printf("\n");
          for (j = 0; j < V; ++j)
          {
              printf("%d\t", MST[i][j]);
          }
      }
}

Here is the call graph for this function: