Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Breadth First Search and Depth First Search in C++
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
class Node{
char value;
vector<Node> children;
public:
Node(char c){
value = c;
}
void addChild(Node n){
children.push_back(n);
return;
}
void addChild(char n){
Node foo(n);
children.push_back(foo);
}
char getValue(){
return value;
}
vector<Node> getChildren(){
return children;
}
bool isLeaf(){
return children.size()==0;
}
bool operator==(Node b){
return b.value==value;
}
};
void construct(Node *r)
{
string foo;
cout<<"Enter children for "<< r->getValue() <<" (-1 for leaf)"<<endl;
cin>>foo;
if(foo == "-1")
return;
else{
for(int i = 0; i < foo.length(); i++)
{
Node t(foo[i]);
construct(&t);
r->addChild(t);
}
}
}
string breadthFirstSearch(Node root, Node goal)
{
std::queue<Node> Q;
std::vector<Node> children;
string path = "";
Q.push(root);
while(!Q.empty())
{
Node t = Q.front();
path += t.getValue();
Q.pop();
if(t == goal){
return path;
}
children = t.getChildren();
for (int i = 0; i < children.size(); ++i)
{
Q.push(children[i]);
}
}
return path;
}
string depthFirstSearch(Node root, Node goal)
{
std::stack<Node> Q;
std::vector<Node> children;
string path = "";
Q.push(root);
while(!Q.empty())
{
Node t = Q.top();
path += t.getValue();
Q.pop();
if(t == goal){
return path;
}
children = t.getChildren();
std::reverse(children.begin(),children.end());
for (int i = 0; i < children.size(); ++i){
Q.push(children[i]);
}
}
return path;
}
int main(int argc, char** args)
{
char r;
cout<<"Enter root node"<<endl;
cin>>r;
Node root(r);
construct(&root);
cout<<"Enter Node to search for: ";
cin>>r;
cout<<endl;
cout<<"BFS Traversal: "<<breadthFirstSearch(root, Node(' '))<<endl;
cout<<"BFS Search Path: "<<breadthFirstSearch(root, Node(r))<<endl<<endl;
cout<<"DFS Traversal: "<<depthFirstSearch(root, Node(' '))<<endl;
cout<<"DFS Search Path: "<<depthFirstSearch(root, Node(r))<<endl;
return 0;
}
@bdawco

This comment has been minimized.

Copy link

bdawco commented Apr 22, 2016

Hi I need help!!
can any body explain me the DSF program?

@asam139

This comment has been minimized.

Copy link

asam139 commented Feb 4, 2018

Perfect!!! Thanks so much +1:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.