DFS Sample Code


#include <bits/stdc++.h>

using namespace std;

vector<int>v[100];
bool visited[100];

int node,edge;

void DFS(int n)
{
    visited[n]=true;
    cout<<n<<" ";
    int temp;
    for(int i=0; i<v[n].size(); i++)
    {
        temp=v[n][i];
        if(!visited[temp])
            DFS(temp);
    }
}


int main()
{
    cin>>node>>edge;
    for(int i=0; i<edge; i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    int src,dst;
    cin>>src>>dst;
    memset(visited,0,sizeof visited);
    cout<<"DFS traverse order is = ";
    DFS(src);
    cout<<endl;
    if(visited[dst])
        cout<<dst<<" is reachable from "<<src<<endl;
    else
        cout<<dst<<" is not reachable from "<<src<<endl;
    return 0;
}


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s