1.

KRUSKAL
#include <stdio.h>
#de ne INF 999

int p[10], c[10][10];

int nd(int x) { while (p[x]) x = p[x]; return x; }

int main() {
int n, i, j, k, a, b, min, cost = 0, x, y;
printf("Enter the n value:");
scanf("%d", &n);

printf("Enter the graph data:\n");

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &c[i][j]);

printf("\nEdges of spanning tree are:\n");

for (k = 1; k < n; k++) {
min = INF;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (c[i][j] < min &&
(x = nd(i)) != (y = nd(j))) {
min = c[i][j];
a = i; b = j;
}

p[ nd(b)] = nd(a);
cost += min;
printf("%d -> %d\n", a, b);
c[a][b] = c[b][a] = INF;
}

printf("\nCost of spanning tree is=%d", cost);

return 0;
}
fi
fi
fi
fi
fi
fi
 [Link]
#include <stdio.h>
#de ne INF 999

int c[10][10], d[10], p[10], v[10];

int main() {
int n, s, i, j, u, min, cost = 0;

printf("Enter the n value:");

scanf("%d", &n);

printf("Enter the graph data:\n");

for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d", &c[i][j]);

printf("Enter the source node:");

scanf("%d", &s);

for(i = 1; i <= n; i++)

d[i] = c[s][i], p[i] = s;

v[s] = 1;

printf("\nEdges of spanning tree are:\n");

for(i = 1; i < n; i++) {
min = INF;
for(j = 1; j <= n; j++)
if(!v[j] && d[j] < min)
min = d[u = j];

v[u] = 1;
cost += d[u];
printf("%d -> %d\n", p[u], u);

for(j = 1; j <= n; j++)

if(!v[j] && c[u][j] < d[j])
d[j] = c[u][j], p[j] = u;
}

printf("\nCost of spanning tree is=%d", cost);

return 0;
}
fi
3.
1. Floyd's Algorithm (Same Output as Original)

#include<stdio.h>

int main()
{
int a[10][10],n,i,j,k;

printf("\nEnter the n value:");

scanf("%d",&n);

printf("\nEnter the graph data:\n");

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);

for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][k]+a[k][j]<a[i][j])
a[i][j]=a[i][k]+a[k][j];

printf("\nShortest path matrix\n");

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",a[i][j]);
printf("\n");
}
return 0;
}

2. Warshall's Algorithm (Same Output as Original)

#include<stdio.h>

int main()
{
int a[10][10],n,i,j,k;
 printf("\nEnter the n value:");
scanf("%d",&n);

printf("\nEnter the graph data:\n");

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);

for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=a[i][j]||(a[i][k]&&a[k][j]);

printf("\nResultant path matrix\n");

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",a[i][j]);
printf("\n");
}
return 0;
}
 [Link] algo
#include <stdio.h>
#de ne INF 999

int c[10][10], d[10], v[10];

int main() {
int n, s, i, j, u, min;

printf("Enter the n value:");

scanf("%d", &n);

printf("Enter the graph data:\n");

for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d", &c[i][j]);

printf("Enter the source node:");

scanf("%d", &s);

for(i = 1; i <= n; i++)

d[i] = c[s][i], v[i] = 0;

d[s] = 0;
v[s] = 1;

for(i = 1; i < n; i++) {

min = INF;
for(j = 1; j <= n; j++)
if(!v[j] && d[j] < min)
min = d[u = j];

v[u] = 1;

for(j = 1; j <= n; j++)

if(!v[j] && d[u] + c[u][j] < d[j])
d[j] = d[u] + c[u][j];
}

printf("\nShortest distances are:\n");

for(i = 1; i <= n; i++)
printf("%d -> %d = %d\n", s, i, d[i]);

return 0;
}
fi
[Link] sort
#include <stdio.h>

int a[10][10], id[10], t[10], k = 0;

void topo(int n) {
int i, j;
for(i = 1; i <= n; i++)
if(id[i] == 0) {
id[i] = -1;
t[++k] = i;
for(j = 1; j <= n; j++)
if(a[i][j]) id[j]--;
i = 0;
}
}

int main() {
int n, i, j;

printf("Enter the n value:");

scanf("%d", &n);

printf("Enter the graph data:\n");

for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
if(a[i][j]) id[j]++;
}

topo(n);

if(k != n)
printf("Topological ordering not possible");
else {
printf("Topological ordering is:\n");
for(i = 1; i <= n; i++)
printf("%d ", t[i]);
}

return 0;
}
[Link] dynamic programing
#include <stdio.h>

int w[10], p[10], n;

int max(int a, int b) {

return a > b ? a : b;
}

int knap(int i, int m) {

if(i > n) return 0;
if(w[i] > m) return knap(i + 1, m);
return max(knap(i + 1, m), knap(i + 1, m - w[i]) + p[i]);
}

int main() {
int i, m;

printf("Enter the no. of objects:");

scanf("%d", &n);

printf("Enter the knapsack capacity:");

scanf("%d", &m);

printf("Enter pro t followed by weight:\n");

for(i = 1; i <= n; i++)
scanf("%d%d", &p[i], &w[i]);

printf("Max pro t=%d", knap(1, m));

return 0;
}
fi
fi
 [Link] greedy

#include <stdio.h>

int p[10], w[10], x[10], n, m;

int main() {
int i, j, t, cw = 0;
oat r[10], tp = 0;

printf("Enter the number of objects:");

scanf("%d", &n);

printf("Enter the objects' weights:");

for(i = 1; i <= n; i++) scanf("%d", &w[i]);

printf("Enter the objects' pro ts:");

for(i = 1; i <= n; i++) scanf("%d", &p[i]);

printf("Enter the maximum capacity:");

scanf("%d", &m);

for(i = 1; i <= n; i++)

r[i] = ( oat)p[i] / w[i];

for(i = 1; i < n; i++)

for(j = i + 1; j <= n; j++)
if(r[i] < r[j]) {
oat tr = r[i]; r[i] = r[j]; r[j] = tr;
t = w[i]; w[i] = w[j]; w[j] = t;
t = p[i]; p[i] = p[j]; p[j] = t;
}

for(i = 1; i <= n; i++)

if(cw + w[i] <= m) {
x[i] = 1;
cw += w[i];
tp += p[i];
}
else {
tp += ( oat)(m - cw) * p[i] / w[i];
break;
}

printf("Optimal solution for greedy method: %.1f", tp);

return 0;
}
fl
fl
fl
fl
fi
[Link] OF SUBSETS

#include<stdio.h>

int s[10],x[10],n,d;

void sum(int k,int sum1)

{
int i;
if(sum1==d)
{
for(i=0;i<n;i++)
if(x[i])
printf("%d ",s[i]);
printf("\n");
return;
}

if(k==n || sum1>d)
return;

x[k]=1;
sum(k+1,sum1+s[k]);

x[k]=0;
sum(k+1,sum1);
}

int main()
{
int i;

printf("Enter n: ");
scanf("%d",&n);

printf("Enter the set:\n");

for(i=0;i<n;i++)
scanf("%d",&s[i]);

printf("Enter the sum: ");

scanf("%d",&d);

printf("Subsets are:\n");
sum(0,0);

return 0;
}
[Link] sort

#include <stdio.h>
#include <time.h>

void selsort(int a[], int n) {

int i, j, p, t;
for(i = 0; i < n - 1; i++) {
p = i;
for(j = i + 1; j < n; j++)
if(a[j] < a[p]) p = j;
t = a[i];
a[i] = a[p];
a[p] = t;
}
}

int main() {
int a[10], i, n;
clock_t s, e;

printf("Enter the n value:");

scanf("%d", &n);

printf("Enter the array:");

for(i = 0; i < n; i++)
scanf("%d", &a[i]);

s = clock();
selsort(a, n);
e = clock();

printf("\nTime taken is:%f", ( oat)(e - s) / CLOCKS_PER_SEC);

printf("\nSorted array is:");
for(i = 0; i < n; i++)
printf("%d ", a[i]);

return 0;
}
fl
[Link] sort

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

void quick(int a[],int l,int r)

{
int i=l,j=r,p=a[l],t;

if(l<r)
{
while(i<j)
{
while(a[i]<=p && i<r) i++;
while(a[j]>p) j--;

if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}

t=a[l];
a[l]=a[j];
a[j]=t;

quick(a,l,j-1);
quick(a,j+1,r);
}
}

int main()
{
int a[100],n,i,ch;

while(1)
{
printf("\[Link]\[Link]\[Link]");
 printf("\nEnter choice: ");
scanf("%d",&ch);

switch(ch)
{
case 1:
printf("\nGraph data stored\n");
break;

case 2:
printf("\nEnter size: ");
scanf("%d",&n);

srand(time(0));

for(i=0;i<n;i++)
a[i]=rand()%100;

printf("\nBefore Sorting:\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);

quick(a,0,n-1);

printf("\nAfter Sorting:\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);

break;

case 3:
exit(0);
}
}
}
12. N Queens
#include<stdio.h>
#include<stdlib.h>

int c[10],n,f=0;

int ok(int r){

int i;
for(i=1;i<r;i++)
if(c[i]==c[r]||abs(c[i]-c[r])==abs(i-r)) return 0;
return 1;
}

void q(int r){

int i,j;
for(c[r]=1;c[r]<=n;c[r]++)
if(ok(r))
if(r==n){
f=1;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
printf(j==c[i]?"Q":"-");
printf("\n");
}
printf("\n");
}else
q(r+1);
}

int main(){
printf("Enter the no. of queens:");
scanf("%d",&n);
q(1);
if(!f)
printf("No solution");
return 0;
}