BFS and DFS in C++

Depth First Search

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

Notes on DFS

Code for DFS

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

template<typename T>
class Graph{

	private:
		map<T,list<T> > adjList;

	public:
		Graph(){}

		void addEdge(T u, T v,bool bidir=true){
			// Bidir = Bidirectional !!
			adjList[u].push_back(v);
			if(bidir){
				adjList[v].push_back(u);
			}
		}

		void print(){

			for(auto i:adjList){
				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;

			for(T neighbour : adjList[node]){

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

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

			dfsHelper(src,visited);
		}
};

int main(){

	Graph<int> g;
	g.addEdge(0,1);
	g.addEdge(0,6);
	g.addEdge(6,7);
	g.addEdge(7,8);
	g.addEdge(1,2);
	g.addEdge(0,4);
	g.addEdge(2,4);
	g.addEdge(2,3);
	g.addEdge(3,4);
	g.addEdge(3,5);	
	g.addEdge(5,8);
	g.addEdge(5,9);
	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 

Breadth-First Search

• Level-by-Level search of a Graph from a Node/Vertex

Notes on BFS

BFS Code

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


template<typename T>
class Graph{

	map<T,list<T> > adjList;

public:
	Graph(){}

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

		adjList[u].push_back(v);
		if(bidir){
			adjList[v].push_back(u);
		}
	}

	void print(){

		for(auto i : adjList){
			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(); 

			for(int neigbour : adjList[node]){

				if(!visited[neigbour]){

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

int main(){

	Graph<char> g;
	g.addEdge('A','C');
	g.addEdge('A','B');
	g.addEdge('A','E');
	g.addEdge('C','F');
	g.addEdge('C','G');
	g.addEdge('B','E');
	g.addEdge('B','D');
	g.addEdge('D','E');

	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