Given an undirected,unweighted graph and two vertices u and v,the task is to find the path between these two vertices.u can be considered as the source vertex and v as the destination vertex.
Example-
Number of vertices-5
Number of edges-4
Given vertices are 2 and 4.
Edges-
1 2
1 3
3 4
4 5
The path between 2 and 4 is 2->1->3->4.
Algorithm-
1.DFS is called on vertex u.
2.A stack S is kept to keep track of the path between the source vertex and the current vertex.
3.As soon as destination vertex v is encountered,we return the path as the contents of the stack.
Code-
[cpp]
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;
vector<int>arr[10005];
int n,a,b,j=0,m;
int color[100005];
int u,v;
stack<int> path;
void dfs(int node)
{
//printing the vertices of the path
printf("%d->",node+1);
//until final vertex is reached
if(node!=v-1)
{
color[node]=2;//marking the visited nodes
for(int i=0;i<arr[node].size();++i)
{
if(color[arr[node][i]]==0)
{
dfs(arr[node][i]);
}
}
}
}
int main()
{
int t,p;
int i;
p=1;
j=0;
// n is the number of vertices
// m is the number of edges
scanf("%d %d",&n,&m);
// u is the source vertex
// v is the destination vertex
scanf("%d %d",&u,&v);
//clearing the arrays and vectors
for(i=0;i<n;i++)
arr[i].clear();
for(i=0;i<n;++i){
color[i]=0;
}
while(j<m)
{
//a and b denote the starting and ending points of the edge
scanf("%d %d",&a,&b);
//maintaining the adjacency lists
arr[a-1].push_back(b-1);
arr[b-1].push_back(a-1);
j++;
}
//calling dfs on source vertex
dfs(u-1);
return 0;
}
[/cpp]
