#include<iostream>
using namespace std;
#include<stdio.h>
#include<stdlib.h>
int V,E,v1,v2;
int **adj;
int path[10],path_index=0;
void DFS_Util(int s,bool *visited)
{
int i;
visited[s]=true;
path[path_index]=s+1;
path_index++;
if(s!=v2)
{
for(i=0;i<V;i++)
{
if(adj[s][i]==1)
{
if(!visited[i])
{
// cout<<"In "<<i<<endl;
DFS_Util(i,visited);
// cout<<"Out "<<i<<endl;
}
}
}
}
else
{
for(int i=0;i<path_index;i++)
cout<<path[i]<<" ";
cout<<endl;
}
path_index--;
visited[s]=false;
return;
}
void DFS()
{
int i,j;
bool *visited=new bool[V];
for(i=0;i<V;i++)
visited[i]=false;
cout<<endl<<"Enter pair of vertices :";
cin>>v1>>v2;
v1-=1;
v2-=1;
// for(int i=0;i<V;i++)
// if(visited[i]==false)
DFS_Util(v1,visited);
}
int main()
{
int i,j;
printf("Enter the no. of Vertices:\n");
scanf("%d",&V);
printf("Enter the no. of Edges:\n");
scanf("%d",&E);
adj=new int*[V];
for(i=0;i<V;i++)
adj[i]=new int[V];
for(i=0;i<V;i++)
for(j=0;j<V;j++)
adj[i][j]=0;
for(i=0;i<E;i++)
{
printf("\nEnter vertices for edge:%d --->",i+1);
scanf("%d %d",&v1,&v2);
adj[v1-1][v2-1]=1;
adj[v2-1][v1-1]=1;
}
printf("\n\nAdjacency Matrix :");
for(i=0;i<V;i++)
{
printf("\n");
for(j=0;j<V;j++)
{
printf("%d ",adj[i][j]);
}
}
printf("\n\nDepth First Search :");
DFS();
return 0;
}Program to print all path from a given source to destination
Subscribe to:
Posts (Atom)
No comments:
Post a Comment