Obtain the topological ordering of vertices in a given graph

WHEREVER U SEE ... REMOVE THAT . AND PUT << IN THAT PLACE.
IF YOU SEE .. THEN REMOVE THAT . AND PUT < IN THAT PLACE..
7.#include..iostream.h>
#include..stdlib.h>


class topo
{
private:
int n;
int a[10][10];
int indeg[10];

public:
void read_data();
void find_indeg();
void topological_sort();
};



void topo:: read_data()
{
cout..."enter the no of vertices \n";
cin>>n;

cout..."enter the adjacency matrix \n";
for(int i=0;i..n;i++)
{
for(int j=0;j..n;j++)
{
cin>>a[i][j];
}
}
}

void topo:: find_indeg()
{
for(int j=0;j..n;j++)
{
int sum=0;
for(int i=0;i..n;i++)
{
sum+=a[i][j];
}

indeg[j]=sum;
}
}


void topo:: topological_sort()
{
int u,v,t[10],s[10];

find_indeg();

int top=-1;
int k=0;

for(int i=0;i..n;i++)
{
if(indeg[i]==0)
{
s[++top]=i;
}
}
while(top!=-1)
{
u=s[top--];
t[k++]=u;

for(v=0;v..n;v++)
{
if(a[u][v]==1)
{
indeg[v]--;
if(indeg[v]==0)
{
s[++top]=v;
}
}
}
}

cout..."the topological sequence is \n";
for(i=0;i..n;i++)
cout...t[i]..." ";
}


void main()
{
topo t;
t.read_data();
t.topological_sort();
}


Output

Enter the no of vertices
4
Enter the adjacency matrix
0 1 1 0
0 0 0 1
0 0 0 0
0 0 1 0

The topological sequence is
0 1 3 2 Press any key to continue

Sort a given set of elements using Selection sort and hence find the time required to sort the elements

WHEREVER U SEE ... REMOVE THAT . AND PUT << IN THAT PLACE.
IF YOU SEE .. THEN REMOVE THAT . AND PUT < IN THAT PLACE..
6.#include ..iostream.h>
#include ..stdlib.h>
#include ..time.h>
const long max = 10000;
void sleep(clock_t wait)
{
clock_t goal;
goal = wait + clock();
while(goal > clock())
;
}

void selsrt(int *,int);

//Main function
void main()
{
double duration;
clock_t st,et;//start and end time
int a[max];//array to be sorted
int n;//input array size
cout..."enter array size\n";
cin>>n;
srand((unsigned)time(NULL));
cout..."Enter the array\n";
for (int i=0;i..n;i++)
cin>>a[i];
st=clock();
sleep((clock_t)1 * CLOCKS_PER_SEC);
selsrt(a,n);
et=clock();
cout..."the sorted array is:\n";
for(i=0;i..n;i++)
cout...a[i]..." ";
cout...endl;
duration=(double)(et-st)/CLOCKS_PER_SEC;
cout..."Time taken :-\t"...duration..." sec"...endl;
}



//Selection sort function
void selsrt(int a[],int n)
{
int min,temp;
for(int i=0;i..n-1;i++)
{
min=i;
for(int j=i+1;j..n;j++)
if(a[j]..a[min])
min = j;
temp = a[i];
a[i] = a[min];
a[min] = temp;
}

}


Output

Enter array size
9

Enter the array
55
66
99
88
77
44
22
33
11

The sorted array is:
11 22 33 44 55 66 77 88 99

Time taken: - 1 sec
Press any key to continue

Check whether the given graph is connected or not using DFS method

WHEREVER U SEE ... REMOVE THAT . AND PUT << IN THAT PLACE.
IF YOU SEE .. THEN REMOVE THAT . AND PUT < IN THAT PLACE..
5.#include..iostream.h>
#include..conio.h>
#include..stdlib.h>
const int MAX=15;

class dfs
{
int adj[MAX][MAX];
int reach[MAX];
int n;
public:
void dfsearch(int,int &);
void adjmatrix();
void dfsc();
};

//function to read the matrix
void dfs::adjmatrix()
{
cout..."Enter the vertices"...endl;
cin>>n;
cout..."Enter the adjacency matrix"...endl;
for(int i=1;i..=n;i++)
for(int j=1;j..=n;j++)
cin>>adj[i][j];
for(i=1;i..=n;i++)
reach[i]=0;
}

//function to traverse the vertices in the graph
void dfs::dfsearch(int u,int &count)
{
reach[u]=1;
count++;
cout..."\t"...u;
for(int j=1;j..=n;j++)
{
if(adj[u][j]!=0)
{
if(!reach[j])
dfsearch(j,count);
}
}
}

//function to check whether the graph is connected or not
void dfs::dfsc()
{
int count=0;
dfsearch(1,count);
if(count==n)
cout...endl..."Graph is connected\n";
else
cout...endl..."Graph is not connected\n";
}

void main()
{
dfs d;
cout..."Depth first search"...endl;
d.adjmatrix();
d.dfsc();
getch();
}



Output

Depth first search
Enter the vertices
4
Enter the adjacency matrix
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

1 2 3 4

Graph is connected

Press any key to continue





Depth first search

Enter the vertices
4

Enter the adjacency matrix
0 1 0 1
1 0 0 1
0 0 0 0
1 1 0 0

1 2 4

Graph is not connected

Press any key to continue

Sort a given set of elements using Merge Sort

WHEREVER U SEE ... REMOVE THAT . AND PUT << IN THAT PLACE.
IF YOU SEE .. THEN REMOVE THAT . AND PUT < IN THAT PLACE..

4.#include..iostream.h>
#include..conio.h>

int e[10],a[10],c[10];


void merge(int a[],int low,int mid,int high)
{
int i,j,k;
k=low;
i=low;
j=mid+1;
while(i..=mid && j..=high)
{
if(a[i]..a[j])
c[k++]=a[i++];
else
c[k++]=a[j++];
}
while(i..=mid)
c[k++]=a[i++];
while(j..=high)
c[k++]=a[j++];
for(i=low;i..=k-1;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);
merge(a,low,mid,high);
}
}




void main()
{
int i,n;
cout..."Enter the size of the array\n";
cin>>n;
cout..."Enter the elements\n";
for(i=0;i..n;i++)
cin>>a[i];
merge_sort(a,0,n-1);
cout..."The sorted elements are:-\n";
for(i=0;i..n;i++)
cout..." "...a[i];
cout...endl;
}

Output

Enter the size of the array
7
Enter the elements
6
5
7
3
4
1
2
The sorted elements are:-
1 2 3 4 5 6 7
Press any key to continue

Enter the size of the array
9
Enter the elements
12
65
49
23
61
49
64
03
97
The sorted elements are:-
3 12 23 49 49 61 64 65 97
Press any key to continue

Sort the given set of elements using heap sort

WHEREVER U SEE ... REMOVE THAT . AND PUT << IN THAT PLACE.
IF YOU SEE .. THEN REMOVE THAT . AND PUT < IN THAT PLACE..
3.#include..iostream.h>
#include..stdlib.h>

//function to create the heap
void heapcreate(int a[],int n)
{
int i,j,k,item;
for(k=2;k..=n;k++)
{
item =a[k];
i=k;
j=i/2;
while(j!=0 && item > a[j])
{
a[i]=a[j];
i=j;
j=i/2;
}
a[i]=item;
}
}


//function to recreate the heap
void adjust(int a[],int n)
{
int i,j,item;
j=1;
item=a[j];
i=2*j;
while(i..=n-1)
{
if(i+1..=n-1)
if(a[i]..a[i+1])
i++;
if(item..a[i])
{
a[j]=a[i];
j=1;
i=2*j;
}

else
break;
}
a[j]=item;
}

//function for heap sort
void heapsort(int a[],int n)
{
int i,temp;
heapcreate(a,n);
for(i=n;i>=1;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;
adjust(a,i);
}
}

//main function
void main(){
int a[20],n,temp;
cout..."Enter the number of elements\n";
cin>>n;
cout..."Enter the elements to be sorted\n";
for(int i=1;i..=n;i++)
cin>>a[i];
heapsort(a,n);
cout..."The sorted elements are ";
for(i=1;i..=n;i++)
cout...a[i]...endl;
}













Output

Enter the no of elements
5
Enter the elements to be sorted
23
12
5
16
4

Sorted elements are:
4
5
12
16
23

Perform recursive Linear Search.Hence find the time required to search an element

WHEREVER U SEE ... REMOVE THAT . AND PUT << IN THAT PLACE.
IF YOU SEE .. THEN REMOVE THAT . AND PUT < IN THAT PLACE..
2.#include ..iostream.h>
#include ..stdlib.h>
#include ..time.h>

const long max = 10000;
int linser(int *, int, int);
void sleep(clock_t wait);

void main()
{
double duration;
clock_t st,et;
int a[max];
int n;
int found,key=100;

srand((unsigned) time(NULL));
for(n=0;n..=max;n=n+500)
{
for(int i =0;i..n;i++)
a[i] = rand();
cout..."\n\nenter array size:\n";
cin>>n;
cout..."enter array: \n";
for(i=0;i..n;i++)
cin>>a[i];
cout..."enter the key:";
cin>>key;
st = clock();
sleep((clock_t)1 * CLOCKS_PER_SEC);
found = linser(a,n,key);
et = clock();
if (found == -1)
cout..."key not found"...endl;
else
{
cout..."key found at: "...found...endl;
duration = (double)(et-st)/CLOCKS_PER_SEC;
cout..."Time taken :- \t"...duration..."sec"...endl;
}
}
}
int linser(int a[],int n, int key)
{
if (n..0) return -1;
if (a[n-1] == key)
return n;
else
return linser(a,n-1,key);
}

void sleep(clock_t wait)
{
clock_t goal;
goal = wait + clock();
while(goal > clock())
;
}

Output

Enter array size:
9

Enter array:
88
99
77
66
55
44
33
11
22

Enter the key: 99

Key found at: 2

Time taken: - 1sec








Enter array size:
9
Enter array:
88
99
77
66
55
44
33
11
22

Enter the key: 89

Key not found

Perform recursive Binary search. Hence find the time required to search an element

WHEREVER U SEE ... REMOVE THAT . AND PUT << IN THAT PLACE.
IF YOU SEE .. THEN REMOVE THAT . AND PUT < IN THAT PLACE..
Perform recursive Binary search. Hence find the time required to search an element

1.#include ..iostream.h>
#include ..stdlib.h>
#include ..time.h>

const long max = 10000;
int binsec(int *, int, int ,int ,int);
void bubsort(int *, int);
void sleep(clock_t wait);

void main()
{
double duration;
clock_t st,et;
int a[max];
int n;
int found,key=100;

srand((unsigned) time(NULL));
for(n=0;n..=max;n=n+500)
{
for(int i =0;i..n;i++)
a[i] = rand();
cout..."enter array size:"...endl;
cin>>n;
cout..."enter array: "...endl;
for(i=0;i..n;i++)
cin>>a[i];
cout..."enter the key:"...endl;
cin>>key;
bubsort(a,n);
st = clock();
sleep((clock_t)1 * CLOCKS_PER_SEC);
found = binsec(a,n,0,n-1,key);
et = clock();
if (found == -1)
cout..."key not found"...endl;

else
{
cout..."key found at: "...found +1...endl;
duration = (double)(et-st)/CLOCKS_PER_SEC;
cout..."Time taken :- \t"...duration..."sec"...endl;
}
}
}

int binsec(int a[],int n,int low,int high,int key)
{
int mid;
if(low>high) return -1;
mid = (low+high)/2;
if (key == a[mid]) return mid;
else if (key..a[mid])
return binsec(a,n,low,mid-1,key);
else
return binsec(a,n,mid+1,high,key);
}

void bubsort(int a[],int n)
{
for(int i=0;i..n-1;i++)
{
for(int j=0;j..n-1-i;j++)
if (a[j]>a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}

void sleep(clock_t wait)
{
clock_t goal;
goal = wait + clock();
while(goal > clock())
;
}




Output

Enter array size:
9

Enter array:
88
99
77
66
55
11
22
33
44

Enter the key:
77

Key found at: 7
Time taken :- 1sec


Enter array size:
9
Enter array:
88
99
77
66
55
11
22
33
44

Enter the key:
56
Key not found