educative.io

Please also share solution of this Challenge in C++

Courses
,
#1

Please also share solution of this Challenge in C++

#2

Hi @Aman_Singh_Chauhan !!
Here you go

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

struct BFSInfo {
  BFSInfo(int _distance = -1,
          int _predecessor = -1) {
    distance = _distance;
    predecessor = _predecessor;
  }

  int distance;
  int predecessor;
};

vector<BFSInfo>
doBFS(vector<vector<int>> graph,
      int source) {
  vector<BFSInfo> bfsInfo(graph.size());

  bfsInfo[source].distance = 0;

  queue<int> q;
  q.push(source);

  while (!q.empty()) {
    int u = q.front();
    q.pop();

    // Traverse the neighbors of u
    for (int v : graph[u]) {
      if (bfsInfo[v].distance == -1) {
        bfsInfo[v].distance = bfsInfo[u].distance + 1;
        bfsInfo[v].predecessor = u;
        q.push(v);
      }
    }
  }

  return bfsInfo;
}

In the while loop, we repeatedly dequeue a vertex u from the queue q. Then, we traverse the neighbors of u using the adjacency list representation of the graph in graph[u]. For each neighbor v of u that has not been visited, we set its distance to 1 greater than u's distance, its predecessor to u, and enqueue v.

The function returns the bfsInfo vector that records the distances and predecessors of each vertex from the source vertex.
I hope it helps. Happy Learning :blush:

1 Like