C Program For Dijkstra's Algorithm(Greedy Algorithm) Method 2

Source Code:

 #include<stdio.h>
 #include<conio.h>
 #define F 9999

 int search_for_qm(char[],int);
 int search_vstar(char[],int[],int);
 void display(char[],int[],char[],int);

 void main()
  {
	 int i,sv,dist[50],vstar,n,j,s=0;
	 char status[50],next[50];
	 int matrix[7][7]={{F,3,6,F,F,F,F},{3,F,2,4,F,F,F},{6,2,F,1,4,2,F},{F,4,1,F,2,F,4},
         {F,F,4,2,F,2,1},{F,F,2,F,2,F,1},{F,F,F,4,1,1,F}};
	 clrscr();

     printf("\n executing the dijkstra algooooo");
	 sv=0;
	 n=7;
     status[sv]='!';
     dist[sv]=0;
     next[sv]='*';
     for(i=0;idist[vstar]+matrix[vstar][i])
		   {
			dist[i]=dist[vstar]+matrix[vstar][i];
			next[i]=vstar+65;
		   }
		 }
	   }
	   display(status,dist,next,n);
	 }


   printf("\n printing d considr vector............");
   for(i=1;ito%c",next[i],i+65);
   printf("\n d shortest paTH..............");
   for(i=1;i<n;i++)
    {
       for(j=0;j<n;j++)
	{
	   if(next[i]==j+65)
	    {
	       if(i==n-1)
		 printf("%d",matrix[j][i]);
	       else
		 printf("%d+",matrix[j][i]);
	       s=s+matrix[j][i];
	      break;
	    }
       }
   }
  printf("= %d",s);
  getch();
 }
 int search_for_qm(char status[],int n)
  {
    int i=0;
	while(i!=n && status[i]!='?')
	   i++;
    if(i==n)
	 return 0;
	else
	 return 1;
  }
  int search_vstar(char status[],int dist[],int n)
    {
      int i,minpos=-1;
      for(i=0;i<n;i++)
	{
	  if(status[i]=='?')
	   {
	     if(minpos==-1)
		minpos=i;
	     else if(dist[i]<dist[minpos])
		    minpos=i;
	   }
	}
	return minpos;
    }

  void display(char status[],int dist[],char next[],int n)
   {
     int i;
	 printf("\n vertex|");
	 for(i=0;i<n;i++)
	   printf("%c",i+65);
	 printf("\n status|");
     for(i=0;i<n;i++)
	printf("%c", status[i]);
	 printf("\n dist  |");
	 for(i=0;i<n;i++)
	  {
	if(dist[i]==F)
	 {
	   printf("-");
	 }
	else
	   printf("%d",dist[i]);
	  }
	printf("\n next  |");
    for(i=0;i<n;i++)
	  printf("%c", next[i]);
	printf("\n");
 }

C Program For Dijkstra's Algorithm(Greedy Algorithm) Method 1

Source Code:


#include<stdio.h>
#include<conio.h>
#define INFINITY 9999

int minimum_dist_vertex(int dist[],char status[],int N);

main()
{
   int L[100][100],dist[100],prev[100];
   char status[100];
   int Source,Dest,i,j,k,N,Vstar;

   printf("Enter Number Of Vertices:");
   scanf("%d",&N);

   printf("\nEnter Length Matrix:\n\n");
   for(i=1;i<=N;i++)
      for(j=1;j<=N;j++)
	 scanf("%d", &L[i][j]);

   printf("\nEnter Source Node: ");
   scanf("%d",&Source);

   printf("\nEnter Destination Node: ");
   scanf("%d",&Dest);

   status[Source]='!';
   dist[Source]=0;
   prev[Source]=0;

   for(i=1;i<=N;i++)
      if(i!=Source)
      {
	 status[i]='?';
	 dist[i]=L[Source][i];
	 prev[i]=Source;
      }
   k=1;
   do
   {
   printf("\nVertex\t\t");
   for(i=1;i<=N;i++)
      printf("V[%d]\t",i);
   printf("\n");
   printf("Status\t\t");
   for(i=1;i<=N;i++)
      printf("%c\t",status[i]);
   printf("\n");
   printf("Dist  \t\t");
   for(i=1;i<=N;i++)
      printf("%d\t",dist[i]);
   printf("\n");
   printf("Prev  \t\t");
   for(i=1;i<=N;i++)
      printf("%d\t",prev[i]);
   printf("\n");
   for(i=1;i<=70;i++)
   printf("_");

   Vstar=minimum_dist_vertex(dist,status,N);
   status[Vstar]='!';

   for(i=1;i<=N;i++)
   {
      if(status[i]=='?')
      {
	 if (dist[i]> dist[Vstar]+L[Vstar][i])
	 {
	     dist[i]=dist[Vstar]+L[Vstar][i];
	     prev[i]=Vstar;
	 }
      }
   }
   k++;
}
while(k<=N);
printf("\n\nThe Minimum Distance Is:  %d",dist[Dest]);
getch();
}
int minimum_dist_vertex(int dist[],char status[],int N)
{
   int minimum,minposition,i;
   minimum=INFINITY;
   minposition=1;
   for(i=1;i<=N;i++)
     if(status[i]=='?')
       if(dist[i]<minimum)
       {
	  minimum=dist[i];
	  minposition=i;
	}
   return(minposition);
}

C Program For Kruskal Algorithm

Source Code:

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define N 4
#define INF 9999

typedef struct
{
 int weight;
 int visited;
}AdjMatrix;

typedef struct
{
 int weight;
 int u;
 int v;
}Edge;

void takeInput(AdjMatrix graph[][N])
{
 int i,j;
 for(i = 0; i < N; i++)
 {
  for (j = 0; j < N; j++)
  {
   printf("Enter Value For Matrix[%d][%d]: ",i,j);
   scanf("%d",&graph[i][j].weight);
   if(graph[i][j].weight == 0) graph[i][j].weight = INF;
   graph[i][j].visited = FALSE;
  }
 }
}

void printGraph(AdjMatrix graph[][N])
{
 int i,j;
 for(i = 0; i < N; i++)
 {
  putchar('[');
  for (j = 0; j < N; j++)
  { if(graph[i][j].weight == INF)
    printf("%3d ",0);
   else
    printf("%3d ",graph[i][j].weight);
  }
  putchar(']');
  putchar('\n');
 }
}

int find(int set[], int i)
{

    if (set[i] == -1)
  return i;
    else
  return find(set, set[i]);
}

//Function to union two sets...
void Union(int set[], int u, int v)
{
    int uset = find(set, u);
    int vset = find(set, v);
    set[uset] = vset;
}

//A comparison function for built-in qsort()...
int myComp(const void* a, const void* b)
{
    Edge *a1 = (Edge *)a;
    Edge *b1 = (Edge *)b;

    if (a1->weight > b1->weight)
  return 1;
    else
  return -1;
}

//Function for finding MST using Kruskal's Algorithm....
void kruskalMST(AdjMatrix graph[][N])
{
 int i, j, k=0, x, y, set[20], cost = 0, e=0;
 AdjMatrix tree[N][N];
 Edge edge[20];

 //Picking The Edges...
 for(i = 0; i < N; i++)
 {
  for (j = 0; j < N; j++)
  {
   tree[i][j].weight = 0;
   if(graph[i][j].visited != TRUE)
   {
    edge[k].weight = graph[i][j].weight;
    edge[k].u = i;
    edge[k++].v = j;
    graph[j][i].visited = TRUE;

   }
  }
 }

 //Sorting the edges using quicksort()....
 qsort(edge, k, sizeof(Edge), myComp);

 //Setting all elements of parent = -1
 //each element of parent is a disjoint set..
 memset(set, -1, N * sizeof(set[0]));

 i = 0;
 //Loops untill all vertices are considered that is e = #(vertices) - 1
 while (e < N - 1)
 {
  x = find(set, edge[i].u);
  y = find(set, edge[i].v);

  if (x != y)
  {
   cost = cost + edge[i].weight;
   tree[x][y].weight = edge[i].weight;
   tree[y][x].weight = edge[i].weight;
   Union(set, x, y);
   e++;
  }
  i++;
 }

 puts("\nAdjMatrix For MST:\n");
 printGraph(tree);
 printf("\n\nMST Cost = %d",cost);
}


int main()
{
 AdjMatrix graph[N][N];
 system("cls");
 takeInput(graph);
 printf("\nGiven Graph In AdjMatrix Representation:\n");
 printGraph(graph);
 kruskalMST(graph);
 getch();
 return 0;
}

C Program For Prim's Algorithm.

Source Code:

#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];
int main()
{
 printf("\n Enter the number of nodes:");
 scanf("%d",&n);
 printf("\n Enter the adjacency 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]=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();
 return 0;
}

output:

 Enter the number of nodes:6

 Enter the adjacency matrix:
0 3 1 6 0 0
3 0 5 0 3 0
1 5 0 5 6 4
6 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0


 Edge 1:(1 3) cost:1
 Edge 2:(1 2) cost:3
 Edge 3:(2 5) cost:3
 Edge 4:(3 6) cost:4
 Edge 5:(6 4) cost:2
 Minimun cost=13
 

C Program For Bfs,Dfs,Floyd-Warshall

Source Code:

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1 
#define FALSE 0
 
typedef struct Queue 
{
 int *arr;
 int f, r, size, capacity;
}Queue;

typedef struct Stack
{
 int *arr;
 int top, capacity;
}Stack;

void createGraph(int G[][50], int v) 
{
 int i, j;
 printf("\nEnter The Adjacency Matrix: \n");
 for(i = 0; i < v; i++)
 {
  for(j = 0; j < v; j++)
  {
   printf("\nBetween (%d,%d)?: ",i+1, j+1);
   scanf("%d",&G[i][j]);
  }
 }
}

int countEdge(int G[][50], int v)
{
 int i, j, e = 0;
 
 for(i = 0; i < v; i++)
  for(j = 0; j < v; j++)
   if(G[i][j] == 1) 
    e = e + 1;
 return e/2;
}

void printGraph(int G[][50], int v)
{
 int i, j;
 for(i = 0; i < v; i++)
 {
  putchar('[');
  for (j = 0; j < v; j++)
   printf("%3d ",G[i][j]);
  putchar(']');
  putchar('\n');
 }
}

void DFS(int G[][50], int i, int visited[], int v)
{
 int u;
 visited[i] = TRUE;
 for(u = 0; u < v; u++)
  if(G[i][u] == TRUE && visited[u] != TRUE)
   DFS(G, u, visited, v);
}
int visitAll(int G[][50], int v)
{
 int i, visited[50], count = 0;
 
 for(i = 0; i < v; i++)
  visited[i] = FALSE;
 
 for(i = 0; i < v; i++)
 {
  if(visited[i] != TRUE) 
  {
   ++count;
   DFS(G, i, visited, v);
  }
 }
 return count;
}


int isConnected(int G[][50], int v)
{
 return ((visitAll(G, v) > 1)? FALSE : TRUE);
}
int countIsolated(int G[][50], int v)
{
 int i, j, count = 0, flag;
 for(i = 0; i < v; i++)
 {
  flag = TRUE;
  for(j = 0; j < v & flag; j++)
   if(G[i][j] == TRUE) flag = FALSE;
  if(j == v & flag == TRUE) count++;
 }
 return count;
}


Queue *createQueue(int N)
{
 Queue *Q = (Queue*)malloc(sizeof(Queue));

 Q->capacity = N;
 Q->arr = (int*)malloc(sizeof(int) * Q->capacity);
 Q->size = 0;
 Q->f = 0;
 Q->r = Q->capacity-1; 
 
 return Q;
}

void enqueue(Queue *Q, int item)
{
 if(Q->size == Q->capacity)
 {
  printf("\nOverflow.");
  exit(-1);
 }
 Q->r = (Q->r +1) % Q->capacity;
 Q->arr[Q->r] = item;
 Q->size = Q->size + 1;
}

int isEmptyQueue(Queue *Q)
{
 return (Q->size == 0);
}

int dequeue(Queue *Q)
{
 int item;
 if(isEmptyQueue(Q))
 {
  printf("\nEmpty.");
  exit(-1);
 }
 item = Q->arr[Q->f];
 Q->f = (Q->f +1) % Q->capacity;
 Q->size = Q->size - 1;
 return item;
}

void BFS(int G[][50], int s, int v)
{
 Queue *Q = createQueue(30);
 int u, w, visited[30] = {0};
 
 enqueue(Q,s);
 visited[s] = TRUE;
 while(!isEmptyQueue(Q))
 {
  u = dequeue(Q);
  
  printf("%d  ",u);
  
  for(w = 0; w < v; w++)
  {
   if(G[u][w] == TRUE && visited[w] == FALSE)
   {
    enqueue(Q,w);
    visited[w] = TRUE;
   }
  }
 }
}



Stack *createStack(int capacity)
{
 Stack *S = (Stack*)malloc(sizeof(Stack));
 S->top = -1;
 S->capacity = capacity;
 S->arr = (int*)malloc(sizeof(int) * S->capacity);
 return S;
}

int isEmptyStack(Stack *S)
{
 return (S->top == -1);
}

void push(Stack *S, int item)
{
 if(S->top== S->capacity-1)
 {
  printf("\nOverslow.");
  exit(-1);
 }
 
 S->top = S->top + 1;
 S->arr[S->top] = item;
}

int pop(Stack *S)
{
 int item;
 if(isEmptyStack(S))
 {
  printf("\nEmpty.");
  exit(-1);
 }
 item = S->arr[S->top];
 S->top = S->top - 1;
 return item;
}

void DFS(int G[][50], int s, int v)
{
 Stack *S = createStack(30);
 int u, w, visited[30] = {0};
 
 push(S,s);
 visited[s] = TRUE;
 while(!isEmptyStack(S))
 {
  u = pop(S);
  
  printf("%d  ",u);
  
  for(w = 0; w < v; w++)
  {
   if(G[w][u] == TRUE && visited[w] == FALSE)
   {
    push(S,w);
    visited[w] = TRUE;
   }
  }
 }
}



int min(int a, int b)
{
 return (a>b?b:a);
}

void warshall(int G[][50], int v)
{
 int P[50][50], i, j, k;
 
 for(i = 0; i < v; i++)
  for(j = 0; j < v; j++) 
   P[i][j] = G[i][j];
 for(k = 0; k < v; k++)
  for(i = 0; i < v; i++)
   for(j = 0; j < v; j++)
    P[i][j] = P[i][j] || (P[i][k] && P[k][j]);
  
 printGraph(P,v);
}

void floydWarshall(int G[][50], int v)
{
 int D[50][50], i, j, k;
 
 for(i = 0; i < v; i++)
  for(j = 0; j < v; j++) 
   (G[i][j] == 0) ? D[i][j] = 999 : D[i][j] = G[i][j];
 for(k = 0; k < v; k++)
  for(i = 0; i < v; i++)
   for(j = 0; j < v; j++)
    D[i][j] = min(D[i][j],D[i][k]+D[k][j]);
  
 printGraph(D,v);
}

int main()
{
 int G[50][50], v, e;
 
 printf("Enter The Number Of Vertices: ");
 scanf("%d",&v);
 
 createGraph(G, v);
 
 printf("\nThe Adjacency Matrix:\n\n");
 printGraph(G, v);
  
 printf("\nNumber Of Edges Are: %d.",countEdge(G, v));
 
 printf("\n\nThe Given Graph Is%sConnected.",isConnected(G, v)?" ":" Not ");
 
 printf("\n\nThere Are %d Components.",visitAll(G, v));
 
 printf("\n\nThere Are %d Isolated Vertex.",countIsolated(G, v));
 
 printf("\n\nThe BFS Traversal Is:");
 BFS(G, 0, v);
 printf("\n\nThe DFS Traversal Is:");
 DFS(G, 0, v);
 
 printf("\n\nFloyd-Warshall:\n");
 floydWarshall(G,v);
 
 printf("\n\nWarshall:\n");
 warshall(G,v);

 
 return 0;
}