Question

CSC 430              GRAPH PROJECT

Implement a graph class using an adjacency matrix or an adjacency list.

The class should have a constructor, a copy constructor, a destructor and all the methods necessary to add/delete vertices, add/delete edges…

Write a menu-driven program to THOROUGHLY check your class and all the functions included in your program. You can choose the data type. Allow the user to continue with operations as long as he/she wants to.

Your program should check if an operation is possible ( ex: check if the graph is empty before attempting to delete an item; check if it is full before attempting to insert an item…)

Your main program should have the following functions:

1. A DFS function to perform Depth First Search
2. A BFS function to perform Breadth First Search
3. A shortestPath functions that print the shortest path from a given vertex v to any other vertex
4. Additional functions that will make your program more structured. C++ language

Answer 1

To write a C++ program to create a dfs and bfs tree and perform insertion and search operation on it.

ALGORITHM:

Step1: Start the program.

Step 2: Create a tree using linked representation with nodes having the structure LEFT->DATA->RIGHT. Build the tree in such a way that values at each left is less and values at each right is greater.

Step 3: Insert: Get the value to be inserted. Create a new node and set the data field to X. then set the left and right links to NULL.

Step 4: Compare X with root node data in X <root continue search in left subtree. If X=root, then display “Duplicate ”, if X>root then search in right subtree. Then insert the node in its right position.

Step 5: Display all the data in the tree.

Step 6: Stop the program.

PROGRAM:

#include<iostream>

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

#include<stdlib.h>

#define NULL 0

using namespace std;

int cost[10 ][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10],stk[10],top,v,

main()

{

int m;

cout<<"enter the number of vertices";

cin>>n;

cout<<"enter no of edges";

cin>>m;

count<,"\nEDGES\n";

for(k=1;k<=m;k++)

{

cin >>i>>j;

cost[i][j]=1;

}

cout<<"enter the initial vertex';cin>>v;

cout<<"visited vertices\n";

cout<<v;

cout<<"DFS ORDER OF VISITED VERTICES:";

cout<< v <<" ";

visited[v]=1;

k=1;

while(k<n)

{

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

if(cost[v][j]!=0 && visted[j]!=1 && visit[j]!=1

{

visit[j]=1;

stk[top]=j;

top++;

}

v=stk[--top];

cout<<v <<" ";k++;

visit[v]=0;

visited[v]=1;

}

qu[rare++]=j;

}

v=qu[front++];

count<<v << ";

k++;

visit[v]=0; visited[v]= 1;

}

}

struct search

{

int element;

struct search* left;

struct search *right;

};

struct search *t;

struct search *makeempty(struct search *);

struct search *findmin(struct search *);

struct search *findmax(struct search *);

void inorder(struct search *);

struct search *insert(int,struct search *);

struct search *delet(int,struct search *);

int retrieve(struct search *);

void main()

{

int choice,element;

clrscr();

printf(“\n\t\t tree”);

t=makeempty(NULL);

printf(“\n Operations on tree”);

printf("\n 1.Findmin \t 2.Findmax \t 3.Insert \t 4.Delete \t 5.Exit \n");

do

{

printf("\nEnter your choice:");

scanf("%d",&choice);

switch(choice)

{

case 1:

printf("\n Minimum:%d",retrieve(findmin(t)));

break;

case 2:

printf("\n Maximum:%d",retrieve(findmax(t)));

break;

case 3:

printf("\n Enter an element to insert:");

scanf("%d",&element);

t=insert(element,t);

inorder(t);

39

www.rejinpaul.combreak;

case 4:

printf("\nEnter the element to delete:");

scanf("%d",&element);

t=delet(element,t);

inorder(t);

break;

case 5:

exit(0);

}

}while(choice!=6);

getch();

}

struct search *makeempty(struct search *t)

{

if(t!=NULL)

{

makeempty(t->left);

makeempty(t->right);

free(t);

}

return(0);

}

struct search *findmin(struct search *t)

{

if(t==NULL)

return(NULL);

else if(t->left==NULL)

return(t);

else

return(findmin(t->left));

}

struct search *findmax(struct search *t)

{

if(t!=NULL)

while(t->right!=NULL)

t=t->right;

return(t);

}

struct search *insert(int x,struct search *t)

{

if(t==NULL)

{

40

www.rejinpaul.comt=(struct search *)malloc(sizeof(struct search));

if(t==NULL)

{

exit(1);

}

else

{

t->element=x;

t->left=t->right=NULL;

}

}

else

{

if(x<t->element)

t->left=insert(x,t->left);

else if(x>t->element)

t->right=insert(x,t->right);

}

return(t);

}

struct search *delete(int x, struct search *t)

{

if(t==NULL)

printf("\nElement not found");

else if(x<t->element)

t->left=delet(x,t->left);

else if(x>t->element)

t->right=delet(x,t->right);

else if(t->left && t->right)

{

tmp=findmin(t->right);

t->element=tmp->element;

t->right=delet(t->element,t->right);

}

else

{

tmp=t;

if(t->left==NULL)

t=t->right;

else if(t->right==NULL)

t=t->left;

free(tmp);

}

int retrieve(struct search *p)

{

41

www.rejinpaul.comreturn(p->element);

}

void inorder(struct search *t)

{

if(t!=NULL)

{

inorder(t->left);

printf("\t %d\t",t->element);

inorder(t->right);

}

}

getch();

return 0;

}