Path Finding

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-


#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;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

42,383 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>