int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
for(i=1;i<=n;i++)
if(a[v][i] && !visited[i]) q[++r]=i;
if(f<=r)
{
visited[q[f]]=1;
bfs(q[f++]);
}
}
void main()
{
int v;
printf("\n Enter the number of vertices:"); scanf("%d",&n);
for(i=1;i<=n;i++)
{
q[i]=0;
visited[i]=0;
}
printf("\n Enter graph data in matrix form:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:"); scanf("%d",&v);
bfs(v);
printf("\n The node which are reachable are:\n"); for(i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i);
}
9
include
include
int a[20][20],reach[20],n;
void dfs(int v)
{
int i; reach[v]=1;
for(i=1;i<=n;i++)
if(a[v][i] && !reach[i])
{
printf("\n %d->%d",v,i);
dfs(i);
}
}
void main()
{
int i,j,count=0;
printf("\n Enter number of vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
reach[i]=0; for(j=1;j<=n;j++)
a[i][j]=0;
}
printf("\n Enter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(1);
printf("\n");
for(i=1;i<=n;i++)
{
if(reach[i]) count++;
}
if(count==n)
printf("\n Graph is connected");
else
printf("\n Graph is not connected");
getch();
}
1
include
include
void qsort(int low,int high,int a[ ]); int partition(int low,int high,int a[ ]); void main() { int i,n,a[10],low,high; clrscr(); printf("enter the no.of elements\n"); scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); printf("elments before sorting\n"); for(i=0;i<n;i++) printf("%d\t",a[i]); qsort(0,n-1,a); printf("\nelements after sorting\n"); for(i=0;i<n;i++) { printf("%d\t",a[i]); } getch(); } void qsort(int low,int high,int a[]) { int mid; if(low<high) { mid=partition(low,high,a); qsort(low,mid-1,a); qsort(mid+1,high,a); } } int partition(int low,int high,int a[ ]) { int key,i,j,temp; key=a[low]; i=low+1; j=high; while(1) { while(i<=high&&a[i]<key) i++; while(a[j]>key) j- -; if(i<j) { temp=a[i]; a[i]=a[j]; a[j]=temp; } else {
temp=a[low]; a[low]=a[j]; a[j]=temp; return j; } } }
.....,..............................-_____
2
include
include
void simple_merge(int a[],int low,int mid ,int high) { int i=low; int j=mid+1; int k=low; int c[10]; while(i<=mid&&j<=high) { if(a[i]<a[j]) { c[k]=a[i]; i++; k++; } else { c[k]=a[j]; j++; k++; } } while(i<=mid) { c[k++]=a[i++]; } while(j<=high) { c[k++]=a[j++]; } for(i=low;i<=high;i++) { a[i]=c[i]; } } void merge_sort(int a[],int low,int high) { int mid; if(low<high) { mid=(low+high)/2; merge_sort(a,low,mid); merge_sort(a,mid+1,high); simple_merge(a,low,mid,high); } } void main() { int a[10],n,i; printf("enter no of elements\n"); scanf("%d",&n); printf("enter the elements to sorted\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); merge_sort(a,0,n-1); printf("sorted elements\n"); for(i=0;i<n;i++) printf("%d\t",a[i]); }
3
include
include int
minm(int m,int n) { return ((m>n)?n:m); } void sssp(int cost[20][20],int n,int source,int dest[20]) { int s[20],min,w,i,j,v; for(i=1;i<=n;i++) { s[i]=0; dest[i]=cost[source][i]; } s[source]=1; for(i=1;i<=n-1;i++) { min=999; for(j=1;j<=n;j++) if((s[j]==0) && (min>dest[j])) { min=dest[j]; w=j; } s[w]=1; for(v=1;v<=n;v++) if(s[v]==0) { dest[v]=minm(dest[v],(dest[w]+cost[w][v])); } } } void main() { int source,i,j,n; int cost[20][20],dest[20]; clrscr(); printf("enter no of vertices\n"); scanf("%d",&n); printf("enter source vertex\n"); scanf("%d",&source); printf("enter cost matrix\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&cost[i][j]); sssp(cost,n,source,dest); printf(":the shortest distance is \n") for(i=1;i<=n;i++) printf("the cost from %d to %d is %d\t", source,i,dest[i]); getch(); }
4
include
int max(int a, int b); int p[10],w[10],n; int g(int i,int m) { if((i==n)&&(w[i]<=m)) return p[i]; if((i==n)&&(w[i]>m)) return 0; if(w[i]>m) return g(i+1,m); return max(g(i+1,m),g(i+1,m-w[i])+p[i]); } int max(int a,int b) { return(a>b)?a:b; } void main() { int i,m,profit; printf("Enter number of objects\n"); scanf("%d",&n); printf("Enter weight & profit\n"); for(i=1;i<=n;i++) { scanf("%d%d",&w[i],&p[i]); } printf("Enter Knapsack capacity\n"); scanf("%d",&m); profit=g(1,m); printf("Maximum profit earned = %d\n",profit); }
5
int a,b,u,v,n,i,j,ne=1; int visited[10]={0},min, mincost=0,cost[10][10]; void 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(); }
6
int n,a[10][10],p[10][10]; void path() { int i,j,k; for(i=0;i<n;i++) for(j=0;j<n;j++) p[i][j]=a[i][j]; for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(p[i][k]==1&&p[k][j]==1) p[i][j]=1; } void main() { int i,j; printf("Enter the number of nodes:"); scanf("%d",&n); printf("\nEnter the adjacency matrix:\n"); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); path(); printf("\nThe path matrix is shown below\n"); for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%d ",p[i][j]); printf("\n"); } }
7
include
int n,c[10][10],i,j,k,d[10][10]; void read_data(); void write_data(); void floyd(); void main() { printf("enter no.of nodes\n"); scanf("%d",&n); printf("enter the cost adjacency matrix\n"); read_data(); floyd(c,n); write_data(); } void read_data() { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&c[i][j]); } } } void floyd(int c[10][10],int n) { int min(int,int); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { d[i][j]=c[i][j]; } } for(k=1;k<=n;k++) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } } } } void write_data() { printf("the distance matrix is shown below\n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("%d\t",d[i][j]); } printf("\n"); } } int min(int a,int b) { return a<b?a:b; }
8
include
include
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1; void bfs(int v) { for(i=1;i<=n;i++) if(a[v][i] && !visited[i]) q[++r]=i; if(f<=r) { visited[q[f]]=1; bfs(q[f++]); } } void main() { int v; printf("\n Enter the number of vertices:"); scanf("%d",&n); for(i=1;i<=n;i++) { q[i]=0; visited[i]=0; } printf("\n Enter graph data in matrix form:\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&a[i][j]); printf("\n Enter the starting vertex:"); scanf("%d",&v); bfs(v); printf("\n The node which are reachable are:\n"); for(i=1;i<=n;i++) if(visited[i]) printf("%d\t",i); }
9
include
include
int a[20][20],reach[20],n; void dfs(int v) { int i; reach[v]=1; for(i=1;i<=n;i++) if(a[v][i] && !reach[i]) { printf("\n %d->%d",v,i); dfs(i); } } void main() { int i,j,count=0; printf("\n Enter number of vertices:"); scanf("%d",&n); for(i=1;i<=n;i++) { reach[i]=0; for(j=1;j<=n;j++) a[i][j]=0; } printf("\n Enter the adjacency matrix:\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&a[i][j]); dfs(1); printf("\n"); for(i=1;i<=n;i++) { if(reach[i]) count++; } if(count==n) printf("\n Graph is connected"); else printf("\n Graph is not connected"); getch(); }
10
include
include
include
define TRUE 1
define FALSE 0
void print_solution(int n,int x[]) { int c[10][10],i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) c[i][j]='X'; } for(i=1;i<=n;i++) { c[i][x[i]]='Q'; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("%c",c[i][j]); } printf("\n\n"); } } int place(int x[],int k) { int i; for(i=1;i<k;i++) { if(x[i]==x[k]||(i-x[i]==k-x[k])||(i+x[i])==(k+x[k])) return FALSE; } return TRUE; } void nqueens(int n) { int x[10],count=0,k=1; x[k]=0; while(k!=0) { x[k]+=1; while((x[k]<=n)&&(!place(x,k))) x[k]+=1; if(x[k]<=n) { if(k==n) { count++; printf("solution=%d\n",count); print_solution(n,x); } else { k++; x[k]=0; } } else k--; } } void main() { int n; clrscr(); printf("enter the no.of queens\n"); scanf("%d",&n); nqueens(n); getch(); }