IITDU Forum
Would you like to react to this message? Create an account in a few clicks or log in to continue.

BFS implementation of C++

Go down

CPP BFS implementation of C++

Post by BIT0102-Mohaimin Fri May 06, 2011 11:07 pm

Here is a breadth first search I implemented using C++.
I will be honoured if you use it. The wiki article on BFS and this article helped me on this.
The code includes two methods to read a graph. One assumes the graph to be directed, another assumes a undirected graph.
The input format is assumed as follows:
An integer N>=0 denoting the number of nodes.
Then following N lines consists at least one integer.
First integer indicates the number of connected vertices (0<=CThen there are C integers, the vertexes connected to current vertex.
Vertex number is assumed to start with 0

Code:
#include <cstdio>
#include <vector>
#include <queue>

#define WHITE 0
#define BLACK 2

using namespace std;

class Node;
void readDirected();
void readUDirected();
void BFS(int);

vector<Node> nodes;

class Node{
   public:
   /*
    * D = Distance from Source
    * C = Color
    * P = Index of the parent node in the vector nodes
    */
   int D, C, P;
   
   // List of adjucent nodes
   vector<int> adjucent;
   
   Node(){
      D = -1;
      C = WHITE;
      P = -1;
   }
   
   // Adds a node as adjucent
   void add(int n){
      adjucent.push_back(n);
   }
   
   // Degree of the node, equals the size of vector adjucent
   int degree(){
      return adjucent.size();
   }
};

void BFS(int SRC){
   int U, V;
   int v;
   
   nodes[SRC].D = 0;
   nodes[SRC].C = BLACK;
   
   queue<int>Q;   
   Q.push(SRC);
   
   while (!Q.empty()){
      U = Q.front();
      Q.pop();
      
      for (v = 0; v < nodes[U].degree(); v++){
         V = nodes[U].adjucent[v];
         
         if (nodes[V].C == WHITE){
            nodes[V].C = BLACK;
            nodes[V].P = U;
            nodes[V].D = nodes[U].D+1;
            
            Q.push(V);
         }
      }
      
      nodes[U].C = BLACK;
   }
}

/*
 * Reads a directed graph. assumes connection (i, j) != (j, i)
 */
void readDirected(){
   int C, v, N;
   Node w;
   scanf("%d",&N);
   
   for (int n = 0; n < N; n++){
      nodes.push_back(w);
      
      scanf("%d", &C);
      while (C--){
         scanf("%d", &v);
         nodes[n].add(v);
      }
   }
}

/*
 * Reads a undirected graph. assumes connection (i, j) = (j, i)
 */
void readUDirected(){
   int C, v, N;
   scanf("%d",&N);
   Node w;
   
   for (int n = 0; n < N; n++){
      nodes.push_back(w);
   }
   
   for (int n = 0; n < N; n++){      
      scanf("%d", &C);
      while (C--){
         scanf("%d", &v);
         nodes[n].add(v);
         nodes[v].add(n);
      }
   }
}
BIT0102-Mohaimin
BIT0102-Mohaimin
Programmer
Programmer

Course(s) :
  • BIT

Blood Group : B+
Posts : 415
Points : 715

Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum