CODEWITHSUNDEEP
graph-algorithmbreadth-first-search
AlishasPayPal
AlishasPayPal

Reputation: 61

Two coloring Breadth-First Search

In a standard BFS implementation, a node can be one of three colors to represent if it is undiscovered, discovered but incomplete, or discovered and completed. Is there a way to implement BFS using only two colors instead of three?

Upvotes: 0

Views: 1225

Answers (1)

fkdosilovic
fkdosilovic

Reputation: 116

Yes, you can represent it with only two colors. Actually , in probably 99% of problems, you don't need a third color. You need to have an answer to: Is the node X in queue or not? To answer that question we need to have an array. Let's say we call that array visited.

Values that this array can have are, 0 or 1.

visited[X] = 1, if the node X is in queue(node X is waiting to be processed) or the node is was in queue(which means node X is currently being processed, or was processed and we are done with that node) visited[X] = 0, if the node X was not yet in queue

Here is a code:

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>

using namespace std;
const int N = 10003;

char visited[N];
queue<int> q;
vector<int> ls[N];

int main() {

  int n, m; scanf("%d%d", &n, &m); // number of vertices and number of edges
  for(int i = 0; i < m; ++i) {
    int x, y; scanf("%d%d", &x, &y);
    ls[x].push_back(y);
    ls[y].push_back(x);
  }

  int num_of_components = 0;

  for(int i = 1; i <= n; ++i) // iterating through all nodes
    if(!visited[i]) { // if we didn't visit node i , then this is a new component

      visited[i] = '1'; // mark node as visited
      q.push(i); // push node to queue
      ++num_of_components; // new component was found, so add one

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

        int sz = ls[x].size();
        for(int j = 0; j < sz; ++j) {
          int y = ls[x][j];
          if(!visited[y]) {
            visited[y] = '1';
            q.push(y);
          }
        }
      }
    }

  printf("%d\n", num_of_components);
  return 0;
}

Upvotes: 1

Related Questions