C Program to find a minimum spanning tree using Prim’s algorithm

C Program to implement the Prim’s algorithm. Prims algorithm is a greedy algorithm that finds the minimum spanning tree of a graph. Graph should be weighted, connected, and undirected. Read more about C Programming Language .

/***********************************************************
* You can use all the programs on www.c-program-example.com
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact [email protected]
* To find more C programs, do visit www.c-program-example.com
* and browse!
*
* Happy Coding
***********************************************************/

#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
clrscr();
printf("n Enter the number of nodes:");
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
visited[1]=1;
printf("n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf("n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("n Minimun cost=%d",mincost);
getch();
}
Data Structures
Dijkstras Algorithm

Learn C Programming

You can easily select the code by double clicking on the code area above.

You can discuss these programs on our Facebook Page. Start a discussion right now,

our page!

(you can send this program to your friend using this button)

(c) www.c-program-example.com

C Program to implement Dijkstra’s algorithm.

C Program to implement Dijkstra’s algorithm. Dijkstra’s Algorithm finds the shortest path with the lower cost in a Graph. Dijkstra’s Algorithm solves the Single Source Shortest Path problem for a Graph. It is a Greedy algorithm and similar to Prim’s algorithm. Read more about C Programming Language .

/***********************************************************
* You can use all the programs on www.c-program-example.com
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact [email protected]
* To find more C programs, do visit www.c-program-example.com
* and browse!
*
* Happy Coding
***********************************************************/

#include "stdio.h"
#include "conio.h"
#define infinity 999

void dij(int n,int v,int cost[10][10],int dist[])
{
int i,u,count,w,flag[10],min;
for(i=1;i<=n;i++)
flag[i]=0,dist[i]=cost[v][i];
count=2;
while(count<=n)
{
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !flag[w])
min=dist[w],u=w;
flag[u]=1;
count++;
for(w=1;w<=n;w++)
if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
dist[w]=dist[u]+cost[u][w];
}
}

void main()
{
int n,v,i,j,cost[10][10],dist[10];
clrscr();
printf("n Enter the number of nodes:");
scanf("%d",&n);
printf("n Enter the cost matrix:n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=infinity;
}
printf("n Enter the source matrix:");
scanf("%d",&v);
dij(n,v,cost,dist);
printf("n Shortest path:n");
for(i=1;i<=n;i++)
if(i!=v)
printf("%d->%d,cost=%dn",v,i,dist[i]);
getch();
}
Data Structures
Prims Algorithm

Learn C Programming

You can easily select the code by double clicking on the code area above.