Life Hacks

# programs

## Write a program to find the all pairs shortest path for a given graph

#include<iostream.h> #include<conio.h> #include<stdlib.h> int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u; void main() { clrscr(); int m,c; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES Cost\n"; for(k=1;k<=m;k++) { cin >>i>>j>>c; cost[i][j]=c; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]==0) cost[i][j]=31999; cout<<”\n*****prim’s algorithm*****”; cout <<"\nORDER OF VISITED VERTICES"; k=1; while(k<n) { m=31999; if(k==1) { for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(cost[i][j]<m) […]

## Write a program to find the shortest distance from the source node to every other node

#include<iostream.h> #include<conio.h> #include<stdlib.h> int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u; void main() { clrscr(); int m,c; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES Cost\n"; for(k=1;k<=m;k++) { cin >>i>>j>>c; cost[i][j]=c; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]==0) cost[i][j]=31999; cout<<”\n*****prim’s algorithm*****”; cout <<"\nORDER OF VISITED VERTICES"; k=1; while(k<n) { m=31999; if(k==1) { for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(cost[i][j]<m) […]

## Write a program to construct a MST (Minimum Spanning Tree) using Kruskal Algorithm

#include<iostream.h> #include<conio.h> #include<stdlib.h> int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p; void main() { clrscr(); int dup1,dup2; cout<<"enter no of vertices"; cin >> n; cout <<"enter no of edges"; cin >>m; cout <<"EDGE Cost"; for(k=1;k<=m;k++) { cin >>i >>j >>c; cost[i][j]=c; cost[j][i]=c; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]==0) cost[i][j]=31999; visit=1; while(visit<n) { v=31999; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]!=31999 && cost[i][j]<v && cost[i][j]!=-1 ) { int […]

## Write a program to construct a MST (Minimum Spanning Tree) using Prims Algorithm.

#include<iostream.h> #include<conio.h> #include<stdlib.h> int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u; void main() { clrscr(); int m,c; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES Cost\n"; for(k=1;k<=m;k++) { cin >>i>>j>>c; cost[i][j]=c; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]==0) cost[i][j]=31999; cout<<”\n*****prim’s algorithm*****”; cout <<"\nORDER OF VISITED VERTICES"; k=1; while(k<n) { m=31999; if(k==1) { for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(cost[i][j]<m) […]

## Write a program to solve the travelling salesman problem

//Travelling Salesman problem #include <iostream.h> #include <conio.h> class dynamic { private: int c[5][5],n,d[24],p[24][6],list[5],r,i,j; public: dynamic(); void getdata(); void display(); int fact(int num); int min(int list[]); void perm(int list[], int k, int m); void sol(); }; dynamic::dynamic() { r=0; } void dynamic::getdata() { cout<<"Enter no. of cities:"; cin>>n; cout<<endl; for (int i=0;i<n;i++) for (int j=0;j<n;j++) c[i][j]=0; […]

## a program to traverse a graph using Depth First Search Algorithm

#include<iostream.h> #include<conio.h> #include<stdlib.h> int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10]; void main() { int m; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES \n"; for(k=1;k<=m;k++) { cin >>i>>j; cost[i][j]=1; } cout <<"enter initial vertex"; cin >>v; cout <<"ORDER OF VISITED VERTICES"; cout << v <<" "; visited[v]=1; k=1; while(k<n) { for(j=n;j>=1;j–) […]

## Write a program to traverse a graph using Breadth First Search Algo rithm.

#include<iostream.h> #include<conio.h> #include<stdlib.h> using namespace std; int cost[10][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10]; main() { int m; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES \n"; for(k=1;k<=m;k++) { cin >>i>>j; cost[i][j]=1; } cout <<"enter initial vertex"; cin >>v; cout <<"Visitied vertices\n"; cout << v; visited[v]=1; k=1; while(k<n) { for(j=1;j<=n;j++) if(cost[v][j]!=0 && […]

## Write a program to solve the 8 Queens Problem.

#include<stdio.h> #include<conio.h> #include<math.h> int a[30],count=0; int place(int pos) { int i; for(i=1;i<pos;i++) { // condition for placing queen. if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos)))) return 0; } return 1; } void print_sol(int n) { int i,j; count++; printf("\n\nSolution #%d:\n",count); // if placing is right then count inc. for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(a[i]==j) printf("Q\t"); else printf("*\t"); } printf("\n"); } } void […]

## Write a program to solve the Knapsack problem using greedy technique.

#include<iostream.h> #include<conio.h> void knapsack01(int v[ ], int w[ ], int n, int capacity) { int x = 0, b[100][100], i = 0; for(x = 0; x <= capacity; x++) b[0][x] = 0; //set first column to zero for(i = 1; i <= n; i ++) { for(x = 0; x <= capacity; x ++) { […]

## Write a program of the Merge Sort.

#include <iostream.h> #include<conio.h> int a[50]; /* local variable */ void merge(int, int, int); void merge_sort(int low, int high) { int mid; /* local variable */ if(low < high) { mid = (low + high) / 2; merge_sort(low, mid); merge_sort(mid + 1, high); merge(low, mid, high); } } void merge(int low, int mid, int high) { […]