# BFS and DFS in C++

• Basic DFS plunges depth first into the graph without regard for which edges!!

#### Code for DFS

``````#include<iostream>
#include<map>
#include<list>
using namespace std;

template<typename T>
class Graph{

private:

public:
Graph(){}

void addEdge(T u, T v,bool bidir=true){
// Bidir = Bidirectional !!
if(bidir){
}
}

void print(){

cout<<i.first<<"->";

for(T entry:i.second){
cout<<entry<<",";
}
cout<<endl;
}
}

void dfsHelper(T node,map<T,bool> &visited){
visited[node] = true;
cout << node <<" " << endl;

if(!visited[neighbour]){
dfsHelper(neighbour,visited);
}
}
}

void dfs(T src){
map<T,bool> visited;

dfsHelper(src,visited);
}
};

int main(){

Graph<int> g;
g.print();
cout << endl;
g.dfs(8);

cout << endl;
}
``````

#### Ouput

``````0->1,6,4,
1->0,2,
2->1,4,3,
3->2,4,5,
4->0,2,3,
5->3,8,9,
6->0,7,
7->6,8,
8->7,5,
9->5,

8
7
6
0
1
2
4
3
5
9
``````
• Level-by-Level search of a Graph from a Node/Vertex

#### BFS Code

``````#include<iostream>
#include<map>
#include<list>
#include<queue>
using namespace std;

template<typename T>
class Graph{

public:
Graph(){}

void addEdge(T u, T v,bool bidir=true){

if(bidir){
}
}

void print(){

cout << i.first<<"->";

for(T entry : i.second){
cout<< entry <<",";
}
cout<<endl;
}
}

void bfs(T src){

queue<T> q;

map<T,bool> visited;

q.push(src);
visited[src] = true;

while(!q.empty()){

T node = q.front();
cout << node << " " << endl;
q.pop();

if(!visited[neigbour]){

q.push(neigbour);
visited[neigbour] = true;
}
}
}
}
};

int main(){

Graph<char> g;

g.print();
cout << endl;

cout << "BFS FROM A: " << endl;
g.bfs('A');
}
``````

#### Output

``````A->C,B,E,
B->A,E,D,
C->A,F,G,
D->B,E,
E->A,B,D,
F->C,
G->C,

BFS FROM A:
A
C
B
E
F
G
D
``````

Updated: