Breadth First Search C++
|
In graph theory, breadth first search c++ (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal. Algorithm 1. Enqueue the root node. 2. Dequeue a node and examine it. a. If the element sought is found in this node, quit the search and return a result. b. Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered. 3. If the queue is empty, every node on the graph has been examined – quit the search and return “not found”. 4. If the queue is not empty, repeat from Step 2. Note: Using a stack instead of a queue would turn this algorithm into a depth-first search. 
Here is the Breadth first search c++ program : #include <iostream> #include <ctime> using namespace std; struct node { int info; node *next; }; class Queue { private: node *front; node *rear; public: Queue(); ~Queue(); bool isEmpty(); void enqueue(int); int dequeue(); void display(); }; void Queue::display(){ node *p = new node; p = front; if(front == NULL){ cout<<“\nNothing to Display\n”; }else{ while(p!=NULL){ cout<<endl<<p->info; p = p->next; } } } Queue::Queue() { front = NULL; rear = NULL; } Queue::~Queue() { delete front; } void Queue::enqueue(int data) { node *temp = new node(); temp->info = data; temp->next = NULL; if(front == NULL){ front = temp; }else{ rear->next = temp; } rear = temp; } int Queue::dequeue() { node *temp = new node(); int value; if(front == NULL){ cout<<“\nQueue is Emtpty\n”; }else{ temp = front; value = temp->info; front = front->next; delete temp; } return value; } bool Queue::isEmpty() { return (front == NULL); } //Class Graph represents a Graph [V,E] having vertices V and edges E.// class Graph { private: int n; /// n is the number of vertices in the graph int **A; /// A stores the edges between two vertices public: Graph(int size = 2); ~Graph(); bool isConnected(int, int); void addEdge(int u, int v); void BFS(int ); }; Graph::Graph(int size) { int i, j; if (size < 2) n = 2; else n = size; A = new int*[n]; for (i = 0; i < n; ++i) A[i] = new int[n]; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) A[i][j] = 0; } Graph::~Graph() { for (int i = 0; i < n; ++i) delete [] A[i]; delete [] A; } // Checks if two given vertices are connected by an edge @param u vertex @param v vertex @return true if connected false if not connected // bool Graph::isConnected(int u, int v) { return (A[u-1][v-1] == 1); } // @param u vertex @param v vertex // void Graph::addEdge(int u, int v) { A[u-1][v-1] = A[v-1][u-1] = 1; } // performs Breadth First Search // void Graph::BFS(int s) { Queue Q; /** Keeps track of explored vertices */ bool *explored = new bool[n+1]; /** Initailized all vertices as unexplored */ for (int i = 1; i <= n; ++i) explored[i] = false; /** Push initial vertex to the queue */ Q.enqueue(s); explored[s] = true; /** mark it as explored */ cout << “Breadth first Search starting from vertex “; cout << s << ” : ” << endl; /** Unless the queue is empty */ while (!Q.isEmpty()) { /** Pop the vertex from the queue */ int v = Q.dequeue(); /** display the explored vertices */ cout << v << ” “; /** From the explored vertex v try to explore all the connected vertices */ for (int w = 1; w <= n; ++w) /** Explores the vertex w if it is connected to v and and if it is unexplored */ if (isConnected(v, w) && !explored[w]) { /** adds the vertex w to the queue */ Q.enqueue(w); /** marks the vertex w as visited */ explored[w] = true; } } cout << endl; delete [] explored; } int main() { /** Creates a graph with 12 vertices */ Graph g(12); /** Adds edges to the graph */ g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(3, 4); g.addEdge(3, 6); g.addEdge(4 ,7); g.addEdge(5, 6); g.addEdge(5, 7); clock_t t1; t1 = clock(); /** Explores all vertices findable from vertex 1 */ g.BFS(1); float diff = (double)(clock() – t1)/CLOCKS_PER_SEC ; cout <<endl<< “The time taken for Breadth first search: “<< diff << endl; }
|
