Tag: breadth first search

This is similar to what I was doing when I was researching DFS (Depth First Search), which you can see below here I posted a link to my other posting.

Alright so hopefully the DFS algorithm makes sense. It’s very simple once you got it. Once you got it, you got it!

Breadth First Search is a little bit trickier, but don’t worry. It’s still easy to learn. For BFS, it might be implemented like this:

vector<string> breadthFirstSearch(vector<string> *array) {
    queue<Node*> q;
		array->push_back(name);
		q.push(this);
		
		while (!q.empty())
		{
			Node* n = q.front();
			q.pop();
			
			for (int i = 0; i < n->children.size(); i++)
			{
				if (count(array->begin(), array->end(), n->children[i]->name) == 0)
				{
					array->push_back(n->children[i]->name);
					q.push(n->children[i]);
				}
			}
		}
			
    return *array;
  }

In the above sample, this method will essentially print out all of the children of a graph in breadth first search. That is, level by level. However, in a real situation, you would simply return the node when you find what you are looking for.