a) Write a C program that accepts the vertices and edges of a graph

and stores it as an adjacency matrix. Display the adjacency matrix.

#include<stdio.h>
void main()
{
int m[10][10],n,v,i,j;
printf("How many vertices:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("Is there edge between %d->%d (1/0):",i+1,j+1);
scanf("%d",&m[i][j]);
}
}

printf("Adjacency matrix is\n");

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

a) Implement a Binary search tree (BST) library (btree.h)

with
operations – create, search, insert, inorder, preorder and
postorder.
Write a menu driven program that performs the
above operations.

//btree.h*/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct node
{
int info;
struct node *left,*right;
}NODE;
NODE * createbst(NODE *root)
{
NODE *newnode,*temp,*parent;
int i,n,num;
printf("how many nodes");
scanf("%d",&n);
printf("enter the %d elements:",n);
for(i=1;i<=n;i++)
{
newnode=(NODE *)malloc(sizeof(NODE));
printf("\n enter data");
scanf("%d",&num);
newnode->info=num;
newnode->left=newnode->right=NULL;
if(root==NULL)
{
root=newnode;
continue;
}
temp=root;
while(temp!=NULL)
{
parent=temp;
if(num<temp->info)
temp=temp->left;
else
temp=temp->right;
}
if(num<parent->info)
parent->left=newnode;
else
parent->right=newnode;
}
return(root);
}
NODE * search(NODE *root, int key)
{
NODE *temp=root;
while(temp!=NULL)
{
if(key==temp->info)
return temp;
else if(key<temp->info)
temp=temp->left;
else
temp=temp->right;
}
return NULL;
}
NODE *insertbst(NODE *root, int num)
{
NODE *newnode,*temp=root,*parent;
newnode=(NODE *)malloc(sizeof(NODE));
newnode->info=num;
newnode->left=newnode->right=NULL;
if(root==NULL)
{
root=newnode;
return root;
}
while(temp!=NULL)
{
parent=temp;
if(num<temp->info)
temp=temp->left;
else
temp=temp->right;
}
if(num<parent->info)
parent->left=newnode;
else
parent->right=newnode;
return(root);
}
void preorder(NODE *root)
{
NODE *temp=root;
if(temp!=NULL)
{
printf("%d\t",temp->info);
preorder(temp->left);
preorder(temp->right);
}
}
void inorder(NODE *root)
{
NODE *temp=root;
if(temp!=NULL)
{
inorder(temp->left);
printf("\t%d",temp->info);
inorder(temp->right);
}
}

void postorder(NODE *root)

{
NODE *temp=root;
if(temp!=NULL)
{
postorder(temp->left);
postorder(temp->right);
printf("\t%d",temp->info);
}
}

ass1a1.c
#include<stdio.h>
#include "btree.h"
void main()
{
NODE *root=NULL,*temp1;
int ch,num;

do
{
printf("\n1:Create BST");
printf("\n2:Insert");
printf("\n3;search");
printf("\n4:Inodrder");
printf("\n5:Preorder");
printf("\n6:Postorder");

printf("\nenter your choice");

scanf("%d",&ch);
switch(ch)
{
case 1:root=createbst(root);
break;
case 2:printf("enter a value to insert");
scanf("%d",&num);
root=insertbst(root,num);
break;
case 3: printf("enter a value to search");
scanf("%d",&num);
temp1=search(root,num);
if(temp1==NULL)
printf("number not found");
else
printf("number is found");
break;
case 4: inorder(root);
break;
case 5:preorder(root);
break;
case 6:postorder(root);
break;
}
}while(ch!=7);
}

a) Write a C program for the implementation of

Topological sorting.

#include <stdio.h>
#define MAXSIZE 20
typedef struct
{
int data[MAXSIZE];
int top;
}STACK;

void push(STACK *ps,int n)

{
ps->data[++ps->top]=n;
}
int pop(STACK *ps)
{
return ps->data[ps->top--];
}
void init(STACK *ps)
{
ps->top=-1;
}
int isempty(STACK *ps)
{
return(ps->top==-1);
}

void topologicalSort(int m[5][5],int n)

{
int i,j,v,w;
int visited[20]={0};
int indeg[10]={0};
/* calculate the indegree*/
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
indeg[i]=indeg[i]+m[j][i];
}
}

STACK s;
init(&s);
printf("\ntopological sorting::");
while(1)
{
for(v=0;v<n;v++)
{
 if((visited[v]==0)&&(indeg[v]==0))
{
visited[v]=1;
push(&s,v);
printf("v%d\t",v+1);
}
}
if(isempty(&s))
break;
v=pop(&s);
for(w=0;w<n;w++)
{
if(m[v][w]==1)
indeg[w]=indeg[w]-1;
}
} // end of while
} //end of function

int main()
{
int m[5][5],n,i,j;
printf("How many vertices:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("Is there edge between %d->%d (1/0):",i+1,j+1);
scanf("%d",&m[i][j]);
 }
}
topologicalSort(m,5);
return 0;

b) Write a C program for the Implementation of Prim’s Minimum

spanning tree algorithm.

#include<stdio.h>
void main()
{
int a,b,u,v,i,j,e,n;
int cost[10][10];
int visited[10]={0},min,mincost=0;
printf("enter no of vertices");
scanf("%d",&n);
printf("\nenter cost for verices");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("Enter the cost for vertices %d->%d
(cost/999):",i+1,j+1);
scanf("%d",&cost[i][j]);
}
}
visited[0]=1;
printf("\n");
for(e=0;e<n;e++)
{
//find edge with smallest weight
for(i=0,min=999;i<n;i++)
for(j=0;j<n;j++)
{
if(cost[i][j]==0)
cost[i][j]=999;
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",e+1,a+1,b+1,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;//mark edge so that it is not eslected
}
printf("\n Minimum cost=%d",mincost);
}

a) Write a C program that accepts the vertices and edges of

graph. Create adjacency list and display the adjacency list.

#include<stdio.h>
typedef struct node
{
int vertex;
struct node *next;
}NODE;

NODE *list[10];

void createlist(int n)
{
int i,j,ans;
struct node *temp,*newnode;
for(i=0;i<n;i++)
{
list[i]=NULL;
for(j=0;j<n;j++)
{
if(i!=j)
{
printf("is there any edge between %d
and %d(1/0):",i+1,j+1);

scanf("%d",&ans);
 if(ans==1)
{
newnode=(NODE
*)malloc(sizeof(NODE));
newnode->vertex=j+1;
newnode->next=NULL;
if(list[i]==NULL)
list[i]=temp=newnode;
else
{
temp-
>next=newnode;
temp=newnode;
}
}
}
}
}
}//end of function

void displist(int n)
{
struct node *temp;
int i;
printf("\n The adjacency list is:\n");
for(i=0;i<n;i++)
{
printf("\nv%d->",i+1);
temp=list[i];
while(temp)
{
printf("v%d->",temp->vertex);
temp=temp->next;
}
printf("NULL");
}
}//end of function

void main()
{
int n;
printf("enter number of vertices");
scanf("%d",&n);
 printf("\nEnter data for adjacency list");
createlist(n);
displist(n);

Q 2. Write a C program that accepts the vertices and edges of a

graph and store it as an adjacencymatrix. Implement function to
traverse the graph using Depth First Search (DFS) traversal.

#include<stdio.h>
#define MAXSIZE 20
typedef struct
{
int data[MAXSIZE];
int front,rear;
}QUEUE;

void addq(QUEUE *pq,int n)

{
pq->data[++pq->rear]=n;
}
int removeq(QUEUE *pq)
{
return pq->data[++pq->front];
}
void initq(QUEUE *pq)
{
pq->front=pq->rear=-1;
}
int isempty(QUEUE *pq)
{
return(pq->rear==pq->front);
}

void bfs(int m[10][10],int n)

{
int i,j,v,w;
int visited[20]={0};
QUEUE q;
initq(&q);
printf("\nBFS");
v=1;
visited[v]=1;
 addq(&q,v);
while(!isempty(&q))
{
v=removeq(&q);
printf("v%d\t",v);
for(w=1;w<=n;w++)
{
if((m[v][w]==1)&&(visited[w]==0))
{
addq(&q,w);
visited[w]=1;
}
}
}//end of while
}// end of bfs

void main()
{
int m[10][10],n,v,i,j;
printf("How many vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("Is there edge between %d->%d (1/0):",i,j);
scanf("%d",&m[i][j]);
}
}
printf("Adjacency matrix is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",m[i][j]);
}
printf("\n");
}

printf("\nBFS Traversal");
bfs(m,n);

}
Q 1. Write a C program for the implementation of Floyd Warshall’s
algorithm for finding all pairs shortest path using adjacency cost
matrix. [15 Marks]

#include<stdio.h>
#define INF 99999

void printSolution(int graph[5][5],int num)

{
int i,j;
printf("\ndistance between each pairs of vertices:\n");
for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
{
if(graph[i][j] == INF)
printf("%7s","INF");
else printf("%7d",graph[i][j]);
}
printf("\n");
}
}

void floydwarshall(int graph[5][5],int num)

{
int i,j,k;
for(k=0;k<num;k++)
{
for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
{
if(graph[i][k] + graph[k][j] < graph[i][j])
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
printSolution(graph,num);
}

int main()
{
int graph[5][5],num,i,j;
printf("\nHow many vertices:");
scanf("%d",&num);
for(i=0;i<num;i++)
{
 graph[i][i]=0;
for(j=0;j<num;j++)
{
if(i!=j)
{
printf("Enter edge cost bet V%d & V%d (99999 if
edge not present)",i+1,j+1);
scanf("%d",&graph[i][j]);
}
}
}
printSolution(graph,num);
floydwarshall(graph,num);
return 0;
}

Q 1. Write a C program for the Implementation of Kruskal’s

Minimum spanning tree algorithm. [15 Marks]

#include<stdio.h>
typedef struct
{
int src,dest,weight;
}edge;

edge graph[12]={1,2,5, 1,3,3, 2,3,4, 2,4,6, 2,5,2, 3,4,5, 3,6,6, 4,5,8, 4,6,6, 5,6,3,5,7,5,
6,7,4};
int MSTvertices [10];

void sort(edge graph[],int nE)

{
int i,pass;
edge temp;
for(pass=1;pass<nE-1;pass++)
{
for(i=0;i<nE-pass;i++)
{
if(graph[i].weight>graph[i+1].weight)
{
temp=graph[i];
graph[i]=graph[i+1];
graph[i+1]=temp;
}
}
}
}

int find(int v,int nV)

{
int k;
for(k=0;k<nV;k++)
{
if(MSTvertices[k]==v)
return 1;
}
return 0;
}

void kruskalMST(int nV,int nE)

{
edge mst[14];
int i=1,j=2,k=1,count=1,mincost=0, first=0,second=0;
//sort edges in ascending order
sort(graph,nE);
mst[0]=graph[0];
MSTvertices[0]=graph[0].src;
MSTvertices[1]=graph[0].dest;
mincost=graph[0].weight;
while(count<=nV-1)
{
first=find(graph[i].src,nV); //chk if first vertex is in selected list
second=find(graph[i].dest,nV); //chk if second vertex is in selected list

if(!(first&&second))
{
mst[k++]=graph[i];
count++;
mincost=mincost+graph[i].weight;
if(first)
MSTvertices[j++]=graph[i].dest;
else
MSTvertices[j++]=graph[i].src;
}
i++;
}
printf("The edge in the minimum spanning tree are\n");
for(i=0;i<nV-1;i++)
printf("%d--%d==%d\n",mst[i].src,mst[i].dest,mst[i].weight);
printf("minimum cost of spanning tree:%d",mincost);
}

void main()
{
int nV=7,nE=12;
kruskalMST(nV,nE);
}
Q 1. Write a C program for the implementation of Floyd Warshall’s
algorithm for finding all pairs shortest path using adjacency cost
matrix. [15 Marks]

#include<stdio.h>
#define INF 99999

void printSolution(int graph[5][5],int num)

{
int i,j;
printf("\ndistance between each pairs of vertices:\n");
for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
{
if(graph[i][j] == INF)
printf("%7s","INF");
else printf("%7d",graph[i][j]);
}
printf("\n");
}
}

void floydwarshall(int graph[5][5],int num)

{
int i,j,k;
for(k=0;k<num;k++)
{
for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
{
if(graph[i][k] + graph[k][j] < graph[i][j])
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
printSolution(graph,num);
}

int main()
{
int graph[5][5],num,i,j;
printf("\nHow many vertices:");
scanf("%d",&num);
for(i=0;i<num;i++)
{
graph[i][i]=0;
 for(j=0;j<num;j++)
{
if(i!=j)
{
printf("Enter edge cost bet V%d & V%d (99999 if
edge not present)",i+1,j+1);
scanf("%d",&graph[i][j]);
}
}
}
printSolution(graph,num);
floydwarshall(graph,num);
return 0;
}

Q 2. Write a C program which uses Binary search tree library and

displays nodes at each level, and total levels in the tree. [15 Marks]

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct node
{
int info;
struct node *left,*right;
}NODE;
typedef struct
{
NODE *data[MAXSIZE];
int front,rear;
}QUEUE;

void initq(QUEUE *pq)

{
pq->front=pq->rear=-1;
}

void addq(QUEUE *pq,NODE *tnode)

{
pq->data[++pq->rear]=tnode;
}

NODE* removeq(QUEUE *pq)

{
return pq->data[++pq->front];
}
int isempty(QUEUE *pq)
{
return(pq->front==pq->rear);
}

int isfull(QUEUE *pq)

{
return(pq->rear==MAXSIZE-1);
}

NODE * createbst(NODE *root)

{
NODE *newnode,*temp,*parent;
int i,n,num;
printf("how many nodes");
scanf("%d",&n);
printf("enter the %d elements:",n);
for(i=1;i<=n;i++)
{
newnode=(NODE *)malloc(sizeof(NODE));
scanf("%d",&num);
newnode->info=num;
newnode->left=newnode->right=NULL;
if(root==NULL)
{
root=newnode;
continue;
}
temp=root;
while(temp!=NULL)
{
parent=temp;
if(num<temp->info)
temp=temp->left;
else
temp=temp->right;
}
if(num<parent->info)
parent->left=newnode;
else
parent->right=newnode;
}
return(root);
}

void levelorder(NODE *root)

{
int i,level=0;
 NODE *temp,*marker=NULL;
QUEUE q;
int total=0,cnt=0;
initq(&q);
addq(&q,root);
addq(&q,marker);
printf("\n Level %d--->",level);
while(!isempty(&q))
{
temp=removeq(&q) ;
if(temp==marker)
{
printf("\t cnt=%d",cnt);
cnt=0;
level++;
if(!isempty(&q))
{
addq(&q,marker);
printf("\nLevel %d--->",level);
}
}
else
{
printf("%d\t",temp->info);
if(temp->left)
addq(&q,temp->left);
if(temp->right)
addq(&q,temp->right);
total=total+1;
cnt=cnt+1;
}
}
printf("\ntotal nodes=%d",total);
}

/**********************************************ass2a1.c***************
******************/
#include<stdio.h>
#include<stdlib.h>
#include "bst.h"

void main()
{
NODE *root=NULL;
root=createbst(root);
printf("\nLevel order traversal is");
levelorder(root);
}
Q 2. Write a C program for the implementation of Dijkstra’s
shortest path algorithm for finding shortest path from a given
source vertex using adjacency cost matrix. [15 Marks]

#include<stdio.h>

int cost[8][8]={{0,999,999,999,999,999,999,999},{30,0,999,999,999,999,999,999},
{100,80,0,999,999,999,999,999},{999,999,120,0,999,999,999,999},{999,999,999,150,
0,25,999,999},
{999,999,999,100,999,0,90,140},{999,999,999,999,999,999,0,100},{170,999,999,999,
999,999,999,0}};

void dijkstra(int v,int n)

{
int i,j,u,w,count,min;
int dist[10],visited[10]={0};
visited[v]=1; // first set vertex V=4 as 1 means Selected vertex or visited
vertex
for(i=0;i<n;i++)
dist[i]=cost[v][i];
count=2;
while(count<n)
{
min=999;
for(i=0;i<n;i++)
if(visited[i]==0 && dist[i]<min)
{
min=dist[i];
u=i;
}
visited[u]=1;
for(w=0;w<n;w++)
if(dist[u]+cost[u][w]<dist[w])
dist[w]=dist[u]+cost[u][w];
count++;
}
printf("\n Shortest distances from vertex %d are:-\n",v);
for(i=0;i<n;i++)
printf("%d\t",dist[i]);
}
void main()
{

dijkstra(4,8); //4 means starting vertesi.e vertex V4

}
Q) Write a C program that accepts the vertices and edges of a graph
and store it as an adjacency matrix. Implement
function to traverse the graph using Breadth First Search (BFS)
traversal.

#include<stdio.h>
#define MAXSIZE 20
typedef struct
{
int data[MAXSIZE];
int front,rear;
}QUEUE;

void addq(QUEUE *pq,int n)

{
pq->data[++pq->rear]=n;
}
int removeq(QUEUE *pq)
{
return pq->data[++pq->front];
}
void initq(QUEUE *pq)
{
pq->front=pq->rear=-1;
}
int isempty(QUEUE *pq)
{
return(pq->rear==pq->front);
}

void bfs(int m[10][10],int n)

{
int i,j,v,w;
int visited[20]={0};
QUEUE q;
initq(&q);
printf("\nBFS");
v=1;
visited[v]=1;
addq(&q,v);
while(!isempty(&q))
{
v=removeq(&q);
printf("v%d\t",v);
for(w=1;w<=n;w++)
{
if((m[v][w]==1)&&(visited[w]==0))
{
 addq(&q,w);
visited[w]=1;
}
}
}//end of while
}// end of bfs

void main()
{
int m[10][10],n,v,i,j;
printf("How many vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("Is there edge between %d->%d (1/0):",i,j);
scanf("%d",&m[i][j]);
}
}
printf("Adjacency matrix is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",m[i][j]);
}
printf("\n");
}

printf("\nBFS Traversal");
bfs(m,n);

Q1. Write a menu driven program to implement hash table using

array (insert, delete,display). Use any of the above-mentioned hash
functions. In case of collision apply linear probing. [15 Marks]

#include<stdio.h>
int hf(int key,int i)
{
return (key%10 + i)%10;
}
void insert(int HT[10],int key)
{
int i,index;
 for(int i=0;i<10;i++)
{
index=hf(key,i);
if(HT[index]==-1)
{
HT[index]=key;
return;
}
}
printf("Could not insert key %d",key);
}
int search(int HT[10],int key)
{
int i,index;
for(i=0;i<10;i++)
{
index=hf(key,i);
if(HT[index]==key)
return index;
}
return -1;
}
void deletekey(int HT[10],int key)
{
int index;
index=search(HT,key);
if(index==-1)
printf("key %d not found",key);
else
HT[index]=-1; //delete key
}
void showTable(int HT[10])
{
int i;
for(i=0;i<10;i++)
printf("%d[%d]\n",i,HT[i]);
}
int main()
{
int HT[10],choice,key,index;
for(int i=0;i<10;i++)
HT[i]=-1;
do
{
printf("1: INSERT\n2: SEARCH\n3: DELETE\n4: EXIT\n");
printf("Enter your choice:-");
scanf("%d",&choice);
switch(choice)
 {
case 1:
printf("Enter the key to be inserted:-");
scanf("%d",&key);
insert(HT,key);
showTable(HT);
break;
case 2:
printf("Enter the key to be searched:-");
scanf("%d",&key);
index=search(HT,key);
if(index==-1)
printf("%d not found",key);
else
printf("%d found at position %d",key,index);
break;
case 3:
printf("Enter the key to be deleted:-");
scanf("%d",&key);
deletekey(HT,key);
showTable(HT);
}
}while(choice!=4);
return 0;
}