DEV Community

Nic
Nic

Posted on • Originally published at coderscat.com on

4

Breadth-First-Search(BFS) Explained With Visualization

BFS Overview

The Breadth-First Search(BFS) is another fundamental search algorithm used to explore the nodes and edges of a graph. It runs with time complexity of O(V+E), where V is the number of nodes, and E is the number of edges in a graph.

BFS is particularly useful for finding the shortest path on unweighted graphs.

BFS Visualization on Maze

The source is at the position of left-up, and the target is the position of right-bottom.

As we can see, BFS uses the opposite strategy as with DFS. BFS will explore all of the neighbor nodes at the present position, then move on to the larger depth of nodes.

bfs.gif

The maze is generated by disjoint set.

The implementation

An implementation of BFS needs the data-structure of queue, with the property of First-In-First-Out.

The worst-case space complexity is O(V), where V is the number of nodes in the graph.

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

class Graph {
  int V;
  list<int> *adj;

public:
  Graph(int V);
  void addEdge(int v, int w);
  bool BFS(int v, int t);
};

Graph::Graph(int V) {
  this->V = V;
  adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
  adj[v].push_back(w);
}

bool Graph::BFS(int v, int t) {
  vector<bool> marked(V, false);
  queue<int> Q;

  Q.push(v);
  marked[v] = true;
  while(!Q.empty()) {
    int n = Q.front(); Q.pop();
    cout << n << " ";
    if(n == t) //Find a path to target
      return true;
    for(list<int>::iterator it = adj[n].begin(); it != adj[n].end(); ++it) {
      if(!marked[*it]) {
        marked[*it] = true;
        Q.push(*it);
      }
    }
  }
  return false;
}

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);

  cout << "Following is Breadth First Traversal (0 -> 3): \n";
  if(g.BFS(0, 3)) cout << "\nFind a Path!" << std::endl;
  else cout << "\nNo Path!" << std::endl;
  return 0;
}
Enter fullscreen mode Exit fullscreen mode

References

The post Breadth-First-Search(BFS) Explained With Visualization appeared first on CodersCat.

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay