BFS & DFS IMPLEMENTATION
Ayush Singh
375
exploreJanuary LeetCoding Challenge 2021

EASY APPROACH DFS VS BFS

BFS stands for Breadth First Search is a vertex based technique for finding a shortest path in graph. It uses a Queue data structure which follows first in first out. In BFS, one vertex is selected at a time when it is visited and marked then its adjacent are visited and stored in the queue. It is slower than DFS.
DFS stands for Depth First Search is a edge based technique. It uses the Stack data structure, performs two stages, first visited vertices are pushed into stack and second if there is no vertices then visited vertices are popped.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

void bfsPrint(vector<vector<int> > v, int sv){
    int n = v.size();
     vector<bool> visited(n,false);
     queue<int> q;
     q.push(sv);
     visited[sv] = true;

     while(!q.empty()){
        int cv = q.front();
        q.pop();
        cout<<cv<<endl;
        for(int i=0;i<n;i++){
            if(v[cv][i] && !visited[i]){
                q.push(i);
                visited[i] = true;
            }
        }
     }
}

void print(vector<vector<int> > v, int sv, vector<bool> &visited){
    cout<<sv<<endl;
    visited[sv] = true;
    int n = v.size();
    for(int i=0;i<n;i++){
        if(v[sv][i] == 1 && visited[i]==false){
            print(v,i, visited);
        }
    }
}

int main(){
   int n,e;
   cin>>n>>e;

   vector<vector<int> > matrix(n,vector<int>(n,0));

   for(int i=1;i<=e;i++){
    int fv,sv;
    cin>>fv>>sv;
    matrix[fv][sv] = 1;
    matrix[sv][fv] = 1;
   }
   vector<bool> visited(n,false);

   cout<<"DFS "<<endl;
   print(matrix,0, visited);

   cout<<"BFS"<<endl;
   bfsPrint(matrix,0);
   return 0;
}
Comments (1)