#include<iostream.h>
#include <stdio.h>
#include <conio.h>
class adj{
int i,j,c[10],graph[10][10],num,span[10][10];
public: void in();
void out();
};
void adj::in()
{
cout<<"Enter the number of nodes:-> ";
cin>>num;
cout<<"GRAPH IS REPRESENTED USING A ADJECENCY MATRIX "<<endl;
for(i=0;i<num;i++)
{
c[i]=i;
graph[i][i]=0;
for(j=i+1;j<num;j++)
{
graph[i][j]=0;
cout<<endl<<"Enter the value for edge from node "<<i<< " to "<<j<<" -> ";
cin>>graph[i][j];
graph[j][i]=graph[i][j];
}
}
}
void adj::out()
{
cout<<endl<<endl<<"ADJECENCY MATRIX FOR THE GRAPH IS "<<endl;
for(i=0;i<num;i++)
{
cout<<endl<<(char)179;
for(j=0;j<num;j++)
cout<<" "<<graph[i][j]<<" ";
cout<<(char)179;
}
for(i=0;i<num;i++)
for(j=i;j<num;j++)
{
span[i][j]=0;
if((c[i]!=c[j])&&(graph[i][j]!=0))
{
span[i][j]=graph[i][j];
if(c[i]<c[j])
c[j]=c[i];
else
c[i]=c[j];
}
span[j][i]=span[i][j];
}
cout<<endl<<"ADJECENCY MATRIX FOR THE SPANNING TREE IS"<<endl;
for(i=0;i<num;i++)
{
cout<<endl<<(char)179;
for(j=0;j<num;j++)
cout<<" "<<span[i][j]<<" ";
cout<<(char)179;
}
}
void main()
{
clrscr();
adj ad;
ad.in();
ad.out();
getch();
}
The output of the above program is:
Enter the number of nodes:-> 3
GRAPH IS REPRESENTED USING A ADJECENCY MATRIX
Enter the value for edge from node 0 to 1 -> 1
Enter the value for edge from node 0 to 2 -> 2
Enter the value for edge from node 1 to 2 -> 3
ADJECENCY MATRIX FOR THE GRAPH IS
| 0 1 2 |
| 1 0 3 |
| 2 3 0 |
ADJECENCY MATRIX FOR THE SPANNING TREE IS
| 0 1 2 |
| 1 0 0 |
| 2 0 0 |
***********************************************************
#include<iostream.h>
#include<conio.h>
#include
void create(); // For creating a graph
void dfs(); // For Deapth First Search(DFS) Traversal.
void bfs(); // For Breadth First Search(BFS) Traversal.
struct node // Structure for elements in the graph
{
int data,status;
struct node *next;
struct link *adj;
};
struct link // Structure for adjacency list
{
struct node *next;
struct link *adj;
};
struct node *start,*p,*q;
struct link *l,*k;
int main()
{
int choice;
clrscr();
create();
while(1)
{
cout<<"\n\n-----------------------";
cout<<"\n1: DFS\n2: BSF\n3: Exit\nEnter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
dfs();
break;
case 2:
bfs();
break;
case 3:
exit(0);
break;
default:
cout<<"\nIncorrect choice!\nRe-enter your choice.";
getch();
}
}
return 0;
}
void create() // Creating a graph
{
int dat,flag=0;
start=NULL;
cout<<"\nEnter the nodes in the graph(0 to end): ";
while(1)
{
cin>>dat;
if(dat==0)
break;
p=new node;
p->data=dat;
p->status=0;
p->next=NULL;
p->adj=NULL;
if(flag==0)
{
start=p;
q=p;
flag++;
}
else
{
q->next=p;
q=p;
}
}
p=start;
while(p!=NULL)
{
cout<<"Enter the links to "<
data<<" (0 to end) : ";
flag=0;
while(1)
{
cin>>dat;
if(dat==0)
break;
k=new link;
k->adj=NULL;
if(flag==0)
{
p->adj=k;
l=k;
flag++;
}
else
{
l->adj=k;
l=k;
}
q=start;
while(q!=NULL)
{
if(q->data==dat)
k->next=q;
q=q->next;
}
}
p=p->next;
}
cout<<"\n\n-------------------------";
return;
}
// Deapth First Search(DFS) Traversal.
void bfs()
{
int qu[20],i=1,j=0;
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
qu[0]=p->data;
p->status=1;
while(1)
{
if(qu[j]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==qu[j])
break;
p=p->next;
}
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
qu[i]=q->data;
q->status=1;
qu[i+1]=0;
i++;
}
k=k->adj;
}
j++;
}
j=0;
cout<<"\n\nBreadth First Search Results\n";
cout<<"\n---------------------------\n";
while(qu[j]!=0)
{
cout<status=0;
p=p->next;
}
p=start;
stack[0]=0;
stack[top]=p->data;
p->status=1;
while(1)
{
if(stack[top]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==stack[top])
break;
p=p->next;
}
cout<adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
top++;
stack[top]=q->data;
q->status=1;
}
k=k->adj;
}
}
getch();
return;
}
//a)Program to implement Breadth first Search algorithm.
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int cost[10][10],i,j,k,n,queue[10],front,rear,v,visit[10],visited[10];
void main()
{
int m;
clrscr();
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 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
queue[rear++]=j;
}
v=queue[front++];
cout<<v << " ";
k++;
visit[v]=0;
visited[v]=1;
}
getch();
}
//ANOTHER WAY
/*WAP TO IMPLEMENT BINARY SEARCH TREE(BST) AND ITS OPERATIONS
/*C++ program to implement Binary Search Tree(BST) and its Operations
*/
/*C++ program to implement Binary Search Tree(BST) and its Operations
*/
#include <iostream.h>
class btree
{
private :
struct node
{
node *left ;
char data ;
node *right ;
} *root ;
char *arr ;
int *lc ;
int *rc ;
public :
btree ( char *a, int *l, int *r, int size ) ;
void insert ( int index ) ;
static node* buildtree ( char *a, int *l, int *r, int index ) ;
void display( ) ;
static void inorder ( node *sr ) ;
~btree( ) ;
static void del ( node *sr ) ;
} ;
btree :: btree ( char *a, int *l, int *r, int size )
{
root = NULL ;
arr = new char[size] ;
lc = new int[size] ;
rc = new int[size] ;
for ( int i = 0 ; i < size ; i++ )
{
* ( arr + i ) = * ( a + i ) ;
* ( lc + i ) = * ( l + i ) ;
* ( rc + i ) = * ( r + i ) ;
}
}
void btree :: insert ( int index )
{
root = buildtree ( arr, lc, rc, index ) ;
}
node* btree :: buildtree ( char *a, int *l, int *r, int index )
{
node *temp = NULL ;
if ( index != -1 )
{
temp = new node ;
temp -> left = buildtree ( a, l, r, * ( l + index ) ) ;
temp -> data = * ( a + index ) ;
temp -> right = buildtree ( a, l, r, * ( r + index ) ) ;
}
return temp ;
}
void btree :: display( )
{
inorder ( root ) ;
}
void btree :: inorder ( node *sr )
{
if ( sr != NULL )
{
inorder ( sr -> left ) ;
cout << sr -> data << "\t" ;
inorder ( sr -> right ) ;
}
}
btree :: ~btree( )
{
delete arr ;
delete lc ;
delete rc ;
del ( root ) ;
}
void btree :: del ( node *sr )
{
if ( sr != NULL )
{
del ( sr -> left ) ;
del ( sr -> right ) ;
}
delete sr ;
}
void main( )
{
char a[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' } ;
int l[ ] = { 1, 3, 5, -1, 9, -1, -1, -1, -1, -1 } ;
int r[ ] = { 2, 4, 6, -1, -1, -1, -1, -1, -1, -1 } ;
int sz = sizeof ( a ) ;
btree bt ( a, l, r, sz ) ;
bt.insert( 0 ) ;
cout << "\nIn-order Traversal: " << endl ;
bt.display( ) ;
}
Basic Theory
Depth – first searches are performed by diving downward into a tree as quickly as possible. It does this by always generating a child node from the most recently expanded node, then generating that child’s children, and so on until a goal is found or some cutoff depth point d is reached. If a goal is not found when a leaf node is reached or at the cutoff point, the program backtracks to the most recently expanded node and generates another of its children. This process continues until a goal is found or failure occurs.
Algorithm
An algorithm for the depth – first search is the same as that for breadth first search except in the ordering of the nodes.
Place the starting node s on the top of the stack.
If the stack is empty, return failure and stop.
If the element on the stack is goal node g, return success and stop. Otherwise,
Remove and expand the first element , and place the children at the top of the stack.
Return to step 2.
Example 2:
#include<iostream.h>
#include<conio.h>
#define G 9
#define true 1
#define false 0
static int vertex[G][G]={
{0,},
{0,2,8,3},
{0,1,7,6},
{0,2,8},
{0,2,8},
{0,8,3},
{0,8,3},
{0,4,5,1,6,7}
};
int visited[G],v,w,front,rear;
int Q[G];
class bfs{
public: void AddQ(int,int[]);
void DelQ();
bfs()
{
rear=1;
front=1;
}
};
void bfs::AddQ(int v,int Q[])
{
Q[rear]=v;
rear++;
}
void bfs::DelQ()
{
front++;
if(front==G)
{
front=1;
rear=1;
}
}
void main()
{
clrscr();
bfs b;
for(v=1;v<G;v++)
visited[v]=false;
for(v=1;v<G;v++)
if(!visited[v])
{
b.AddQ(v,Q);
do
{
b.DelQ();
visited[v]=true;
for(w=1;w<G;w++)
{
if(vertex[v][w]==0)
continue;
if(!visited[vertex[v][w]])
{
visited[vertex[v][w]]=true;
b.AddQ(vertex[v][w],Q);
}
}
}while(front!=rear);
}
for(v=1;v<G;v++)
cout<<'\t'<<Q[v];
}
The output of the above program is:
1 2 8 3 4 5 6 7
//b)Program to implement Depth First Search Algorithm.
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int cost[10][10],i,j,k,n,stack[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--)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stack [top]=j;
top++;
}
v= stack [--top];
cout<<v << " ";
k++;
visit[v]=0; visited[v]=1;
}
getch();
}
/*
Complexity
The depth – first search is preferred over the breadth – first when the search tree is known to have a plentiful number of goals. The time complexity of the depth-first tree search is the same as that for breadth-first, O(bd). It is less demanding in space requirements, however, since only the path form the starting node to the current node needs to be stored. Therefore, if the depth cutoff is d, the space complexity is just O(d).
*/
Example 2:
#include<iostream.h>
#include<conio.h>
#define G 9
#define false 0
#define true 1
int visited[G],v;
static int vertex[G][G]={
{0},
{0,2,8,3},
{0,1,4,5},
{0,1,7,6},
{0,2,8},
{0,2,8},
{0,8,3},
{0,8,3},
{0,4,5,1,6,7}
};
class dfs{
public: void traverse(int);
dfs()
{
v=1;
}
};
void dfs::traverse(int v)
{
int w;
visited[v]=true;
if(v==1)
cout<<'\t'<<v;
for(w=1;w<G;++w)
{
if(vertex[v][w]==0)
continue;
if(!visited[vertex[v][w]])
{
cout<<'\t'<<vertex[v][w];
traverse(vertex[v][w]);
}
}
}
void main()
{
int v;
clrscr();
dfs d;
for(v=1;v<G;v++)
visited[v]=false;
for(v=1;v<G;v++)
if(!visited[v])
d.traverse(v);
getch();
}
The output of the above program is:
1 2 4 8 5 6 3 7
***********************************************************************
/* DIRECTED GRAPH */
/* THIS PROGRAM PERFORMS MANY OPERATIONS ON A DIRECTED GRAPH */
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
# define maxnodes 3
# define true 1
# define false 0
class Main_Graph{
int nodes[maxnodes];
public: int adjacent(int [][maxnodes], int, int);
int findpath(int,int,int,int [][maxnodes]);
void tranclos(int [][maxnodes],int [][maxnodes]);
void prod(int [][maxnodes],int [][maxnodes],int [][maxnodes]);
void tra_adj_mat(int [][maxnodes],int [maxnodes]);
void search(int *,int *,int,int);
void joinadj(int,int,int [][maxnodes]);
void removeadj(int,int,int [][maxnodes]);
void warshall(int [][maxnodes],int [][maxnodes]);
};
void main()
{
int m,n,steps,a,b,c,d,ctr,flag=0;
int nodes[maxnodes];
int adj[maxnodes][maxnodes];
int path[maxnodes][maxnodes];
char ch='y';
clrscr();
Main_Graph g;
while(ch=='y')
{
clrscr();
cout<<endl<<"1. For Creating the nodes of a graph ";
cout<<endl<<"2. For Establishing the Adjancecy between two nodes of a graph ";
cout<<endl<<"3. For Showing the Adjancecy Matrix of a Graph ";
cout<<endl<<"4. For Finding the path between two nodes of a Graph ";
cout<<endl<<"5. For Joining the two specified nodes of a Graph ";
cout<<endl<<"6. For Removing the Joining between two specified nodes of a Graph ";
cout<<endl<<endl<<"Enter your choice : ";
fflush(stdin);
cin>>ctr;
if((flag==0) && (ctr>1))
cout<<endl<<"There is no Graph present.";
else
{
switch(ctr)
{
case 1 :
for(m=0;m<maxnodes;m++)
{
cout<<"Enter the "<<m+1<<" node value : ";
cin>>nodes[m];
}
flag=1;
break;
case 2 :
for(m=0;m<maxnodes;m++)
{
for(n=0;n<maxnodes;n++)
if(m!=n)
{
cout<<endl<<"Is node "<<nodes[m]<<" adjacent to "<<nodes[n]<<" : ";
fflush(stdin);
ch=getchar();
if(ch=='y' || ch=='Y')
adj[m][n]=1;
else
adj[m][n]=0;
}
}
break;
case 3 :
cout<<endl<<"The ADJANCECY matrix according to the given nodes "<<endl;
g.tra_adj_mat(adj,nodes);
break;
case 4 :
cout<<endl<<"1. For Finding the path of specified length between two nodes of a Graph ";
cout<<endl<<"2. For Finding the path between two nodes of a Graph by using Warshall ";
cout<<endl<<"3. For Finding the path between two nodes of a Graph by using Transitive Closure ";
cout<<endl<<endl<<"Enter your choice : ";
cin>>ctr;
switch(ctr)
{
case 1 :
cout<<endl<<"Enter the node value between which you want to find the path : ";
cin>>c>>d;
cout<<endl<<"Enter the steps for finding the path : ";
cin>>steps;
g.search(&a,&b,c,d);
if((a==-1) || (b==-1))
cout<<endl<<"The given node does not exists in the graph ";
else
{
steps=g.findpath(a,b,steps,adj);
if(steps==1)
cout<<endl<<"The path exists between the given two nodes "<<endl;
else
cout<<endl<<"The path does not exists between the given two nodes "<<endl;
}
break;
case 2 :
cout<<endl<<"Enter the node value between which you want to find the path : ";
cin>>c>>d;
g.search(&a,&b,c,d);
if((a==-1) || (b==-1))
cout<<endl<<"The given node is not exists in the graph ";
else
{
g.warshall(adj,path);
steps=g.adjacent(path,a,b);
if(steps==1)
cout<<endl<<"The path is exists between the given two nodes "<<endl;
else
cout<<endl<<"The path is not exists between the given two nodes "<<endl;
}
break;
case 3 :
cout<<endl<<"Enter the node value between which you want to find the path : ";
cin>>c>>d;
g.search(&a,&b,c,d);
if((a==-1) || (b==-1))
cout<<endl<<"The given node is not exists in the graph ";
else
{
g.tranclos(adj,path);
steps=g.adjacent(path,a,b);
if(steps==1)
cout<<endl<<"The path is exists between the given two nodes "<<endl;
else
cout<<endl<<"The path is not exists between the given two nodes "<<endl;
}
break;
}
break;
case 5 :
cout<<endl<<"Enter the node value which you want join : ";
cin>>c>>d;
g.search(&a,&b,c,d);
if((a==-1) || (b==-1))
cout<<endl<<"The given node is not exists in the graph ";
else
g.joinadj(a,b,adj);
break;
case 6 :
cout<<endl<<"Enter the node value between which you want to remove the join : ";
cin>>c>>d;
g.search(&a,&b,c,d);
if((a==-1) || (b==-1))
cout<<endl<<"The given node is not exists in the graph ";
else
g.removeadj(a,b,adj);
break;
}
}
cout<<endl<<"Do you want to continue : ";
fflush(stdin);
ch=getchar();
if(ch=='Y')
ch='y';
}
}
int Main_Graph::findpath(int a,int b,int steps,int adj[][maxnodes])
{
int c;
if(steps==1)
return (adjacent(adj,a,b));
else
for(c=0;c<maxnodes;c++)
if((adjacent(adj,a,c)) && (findpath(c,b,steps-1,adj)))
return (true);
return (false);
}
int Main_Graph::adjacent(int adj[][maxnodes],int i,int j)
{
return(adj[i][j]);
}
void Main_Graph::tranclos(int adj[][maxnodes],int path[][maxnodes])
{
int i,j,k;
int newprod[maxnodes][maxnodes];
int adjprod[maxnodes][maxnodes];
for(i=0;i<maxnodes;i++)
for(j=0;j<maxnodes;j++)
adjprod[i][j]=path[i][j]=adj[i][j];
for(i=0;i<maxnodes;i++)
{
prod(adjprod,adj,newprod);
for(j=0;j<maxnodes;j++)
for(k=0;k<maxnodes;k++)
{
path[j][k]=path[j][k] || newprod[j][k];
adjprod[j][k]=newprod[j][k];
}
}
}
void Main_Graph::prod(int a[][maxnodes],int b[][maxnodes],int c[][maxnodes])
{
int i,j,k;
for(i=0;i<maxnodes;i++)
for(j=0;j<maxnodes;j++)
{
c[i][j]=false;
for(k=0;k<maxnodes;k++)
c[i][j]=(c[i][j] || (a[i][k] && b[k][j]));
}
}
void Main_Graph::tra_adj_mat(int adj[][maxnodes],int nodes[])
{
int i,j;
for(i=0;i<maxnodes;i++)
cout<<" "<<nodes[i];
for(i=0;i<maxnodes;i++)
{
cout<<" "<<endl<<nodes[i]<<" ";
for(j=0;j<maxnodes;j++)
cout<<adj[i][j]<<" ";
}
}
void Main_Graph::search(int *a,int *b,int c,int d)
{
int e;
*a=*b=-1;
for(e=0;e<maxnodes;e++)
{
if(nodes[e]==c)
*a=e;
if(nodes[e]==d)
*b=e;
}
getch();
}
void Main_Graph::joinadj(int a,int b,int adj[][maxnodes])
{
adj[a][b]=true;
}
void Main_Graph::removeadj(int a,int b,int adj[][maxnodes])
{
adj[a][b]=false;
}
void Main_Graph::warshall(int adj[][maxnodes],int path[][maxnodes])
{
int i,j,k;
for(i=0;i<maxnodes;i++)
for(j=0;j<maxnodes;j++)
path[i][j]=adj[i][j];
for(k=0;k<maxnodes;k++)
for(i=0;i<maxnodes;i++)
if(path[i][k]==true)
for(j=0;j<maxnodes;j++)
path[i][j]=path[i][j] || path[k][j];
}
The output of the above program is:
1. For Creating the nodes of a graph
2. For Establishing the Adjancecy between two nodes of a graph
3. For Showing the Adjancecy Matrix of a Graph
4. For Finding the path between two nodes of a Graph
5. For Joining the two specified nodes of a Graph
6. For Removing the Joining between two specified nodes of a Graph
Enter your choice : 1
Enter the 1 node value : 12
Enter the 2 node value : 23
Enter the 3 node value : 34
Do you want to continue : Y
1. For Creating the nodes of a graph
2. For Establishing the Adjancecy between two nodes of a graph
3. For Showing the Adjancecy Matrix of a Graph
4. For Finding the path between two nodes of a Graph
5. For Joining the two specified nodes of a Graph
6. For Removing the Joining between two specified nodes of a Graph
Enter your choice : 2
Is node 12 adjacent to 23 : Y
Is node 12 adjacent to 34 : N
Is node 23 adjacent to 12 : Y
Is node 23 adjacent to 34 : Y
Is node 34 adjacent to 12 : N
Is node 34 adjacent to 23 : Y
Do you want to continue : Y
1. For Creating the nodes of a graph
2. For Establishing the Adjancecy between two nodes of a graph
3. For Showing the Adjancecy Matrix of a Graph
4. For Finding the path between two nodes of a Graph
5. For Joining the two specified nodes of a Graph
6. For Removing the Joining between two specified nodes of a Graph
Enter your choice : 3
The ADJANCECY matrix according to the given nodes
12 23 34
12 0 1 0
23 1 0 1
34 0 1 0
Do you want to continue : Y
1. For Creating the nodes of a graph
2. For Establishing the Adjancecy between two nodes of a graph
3. For Showing the Adjancecy Matrix of a Graph
4. For Finding the path between two nodes of a Graph
5. For Joining the two specified nodes of a Graph
6. For Removing the Joining between two specified nodes of a Graph
Enter your choice : 4
1. For Finding the path of specified length between two nodes of a Graph
2. For Finding the path between two nodes of a Graph by using Warshall
3. For Finding the path between two nodes of a Graph by using Transitive Closure
Enter your choice : 1
Enter the node value between which you want to find the path : 12
34
Enter the steps for finding the path : 12-34
The path exists between the given two nodes
Do you want to continue : Y
1. For Creating the nodes of a graph
2. For Establishing the Adjancecy between two nodes of a graph
3. For Showing the Adjancecy Matrix of a Graph
4. For Finding the path between two nodes of a Graph
5. For Joining the two specified nodes of a Graph
6. For Removing the Joining between two specified nodes of a Graph
Enter your choice : 4
1. For Finding the path of specified length between two nodes of a Graph
2. For Finding the path between two nodes of a Graph by using Warshall
3. For Finding the path between two nodes of a Graph by using Transitive Closure
Enter your choice : 2
Enter the node value between which you want to find the path : 23
34
The path is exists between the given two nodes
Do you want to continue : Y
1. For Creating the nodes of a graph
2. For Establishing the Adjancecy between two nodes of a graph
3. For Showing the Adjancecy Matrix of a Graph
4. For Finding the path between two nodes of a Graph
5. For Joining the two specified nodes of a Graph
6. For Removing the Joining between two specified nodes of a Graph
Enter your choice : 5
Enter the node value which you want join : 34
12
Do you want to continue : Y
1. For Creating the nodes of a graph
2. For Establishing the Adjancecy between two nodes of a graph
3. For Showing the Adjancecy Matrix of a Graph
4. For Finding the path between two nodes of a Graph
5. For Joining the two specified nodes of a Graph
6. For Removing the Joining between two specified nodes of a Graph
Enter your choice : 6
Enter the node value between which you want to remove the join : 12
34
Do you want to continue : N
No comments:
Post a Comment