BFS implementation of C++
Page 1 of 1
BFS implementation of C++
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:
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- Programmer
- Course(s) :
- BIT
Blood Group : B+
Posts : 415
Points : 715
Similar topics
» Algorithm implementation
» Huffman Algorithm Implementation
» Implementation of Different OS Algorithms by BIT0101 and BIT0122
» Implementation of different scheduling algorithm in java
» Intel Pentium memory translation and LRU implementation
» Huffman Algorithm Implementation
» Implementation of Different OS Algorithms by BIT0101 and BIT0122
» Implementation of different scheduling algorithm in java
» Intel Pentium memory translation and LRU implementation
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|
Tue Sep 29, 2015 2:45 pm by Sophiawood
» Cisco EHWIC SFP/GE WAN Card
Mon Sep 07, 2015 11:08 am by Sophiawood
» Huawei S1700-28GFR-4P-AC Price
Thu Jun 25, 2015 2:31 pm by Sophiawood
» teach yourself C++ / Herbert Schildt Solutions
Wed Jun 03, 2015 1:52 pm by Abdullah Al Noman
» teach yourself c by herbert schildt pdf
Wed May 13, 2015 11:01 pm by Raquib Ridwan
» ASA 5506X With Firepower ASA5506-K9
Fri Apr 10, 2015 4:31 pm by Sophiawood
» New Trends in Deal Business
Tue Feb 03, 2015 9:38 pm by nersoa
» PoE Power Allocation for WS-C2960S-24PS-L
Wed Nov 05, 2014 11:12 am by Sophiawood
» How to cure back pain
Fri Oct 31, 2014 7:15 pm by Bergen Guildford