Prim's Algorithm

prim.c

void prim (int weight[ ][SIZE])‏
{
	int i, j, k, min, lowWeight[SIZE], closest[SIZE];
	for (i = 1; i < SIZE; ++i)	
	{						//  initialise lowWeight to weights from vertex 0
		lowWeight[i] = weight[0][i];  closest[i] = 0;	//  vertex 0 is closest	  
	}   
	for (i = 1; i < SIZE; ++i) 
	{		//  find nearest adjacent vertex to the tree 
		k = 1;  min = lowWeight[1];
		for (j = 2; j < SIZE; ++j)‏
			if (lowWeight[j] < min)‏
			{‏
				min = lowWeight[j];  k = j;  
			}
		prıntf(“(%d,  %d)/n”, k, closest[k]);	//  k is index of closest vertex
		lowWeight[k] = INFINITY;
		for (j = 1; j < SIZE; ++j)‏			//  update lowWeight and closest
			if ((weight[k][j] < lowWeight[j])) && (lowWeight[j] < INFINITY))‏
			{
				lowWeight[j] = weight[k][j];  closest[j] = k;  
			}
	}
}

This approach is to successively connect the closest as yet unvisited vertex to the existing spanning tree, starting at an arbitrary vertex. It doesn’t create a cycle. Also an optimal solution! Also a greedy algorithm. Complexity is O(n2) where n is number of vertices. Performs well if number of edges e approaches n2,
otherwise Kruskal is better.