Difference Between BFS and DFS (with code and diagrams)

BFS

DFS

BFS stands for Breadth-First Search.

DFS stands for Depth First Search.

In order to determine the shortest path, BFS traverses all of its nodes that are connected to the individual nodes, starting with the first or root node. After reading the example below, you will clearly understand how it functions.

DFS uses a depth-based methodology and traverses every node connected to the relevant node in its entirety. After reading the example below, you will clearly understand how it functions.

It is carried out utilizing the First In, First Out (FIFO) principle (FIFO) whilst using the Queue data structure.

Utilizing the Last In First Out (LIFO) method and using the Stack data structure.

Multiple traversals of a node result in its removal from the queue.

When there are no additional nodes to be visited, the visited nodes are removed from the stack.

Compared to Depth First Search, it is slower.

Compared to the Breadth-First Search algorithm, it is quicker.

Consumes more memory than DFS where stack occupies less memory.

Memory allocation is low compared to BFS.

The applications of DFS include the inspection of two edge connected graphs, strongly connected graphs, acyclic graphs, and topological order.

BFS can be useful in finding whether the graph has connected components or not. And also it can be used in detecting a bipartite graph.

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

class Graph {
  int numVertices;
  list<int>* adjLists;
  bool* visited;

  public:
  Graph(int vertices);
  void addEdge(int src, int dest);
  void BFS(int startVertex);
};

Graph::Graph(int vertices) {
  numVertices = vertices;
  adjLists = new list<int>[vertices];
}
void Graph::addEdge(int src, int dest) {
  adjLists[src].push_back(dest);
  adjLists[dest].push_back(src);
}

void Graph::BFS(int startVertex) {
  visited = new bool[numVertices];
  for (int i = 0; i < numVertices; i++)
    visited[i] = false;

  list<int> queue;

  visited[startVertex] = true;
  queue.push_back(startVertex);

  list<int>::iterator i;

  while (!queue.empty()) {
    int currVertex = queue.front();
    cout << "Visited " << currVertex << " ";
    queue.pop_front();

    for (i = adjLists[currVertex].begin(); i != adjLists[currVertex].end(); ++i) {
      int adjVertex = *i;
      if (!visited[adjVertex]) {
        visited[adjVertex] = true;
        queue.push_back(adjVertex);
      }
    }
  }
}

int main() {
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);

  g.BFS(2);
  return 0;
}

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

class Graph {
  int numVertices;
  list<int> *adjLists;
  bool *visited;

  public:
  Graph(int V);
  void addEdge(int src, int dest);
  void DFS(int vertex);
};


Graph::Graph(int vertices) {
  numVertices = vertices;
  adjLists = new list<int>[vertices];
  visited = new bool[vertices];
}


void Graph::addEdge(int src, int dest) {
  adjLists[src].push_front(dest);
}

void Graph::DFS(int vertex) {
  visited[vertex] = true;
  list<int> adjList = adjLists[vertex];

  cout << vertex << " ";

  list<int>::iterator i;
  for (i = adjList.begin(); i != adjList.end(); ++i)
    if (!visited[*i])
      DFS(*i);
}

int main() {
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 3);
  g.DFS(2);
  return 0;
}