Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. Typically, in graph the problem is to find path between two nodes of the graph (e.g., Austin  and Washington). There are two different methods for graph search: Breadth-First-Search (BFS) which search the siblings first and then moves on to find child or Depth-First-Search (DFS) which searches the child nodes first and then searches the siblings.

Breadth-First Search

A Breadth-first search (BFS) is technique for traversing a graph. BFS visits the sibling nodes before visiting the child nodes. Usually a queue is used in the search process.

  • “Explore” a graph, turning it into a tree
  • Builds a tree over the graph
  • Pick a source vertex to be the root
  • Find (“discover”) its children, then their children and so on.
We will associate vertex “colors” to guide the algorithm where white vertices have not been discovered.
All vertices start out white. Grey vertices are discovered but not fully explored. They may be adjacent to white vertices. Black vertices are discovered and fully explored. They are adjacent only to black and gray vertices. Explore vertices by scanning adjacency list of grey vertices
BFS(s) // s is the source vertex
	 Q = {s};		// Q is a queue; initialized to s
    while (Q not empty) {
        u = Dequeue(Q);
        for each v  u->adj {
           if (v->color == WHITE){
                v->color = GREY;
                //v->d = u->d + 1;
                u->child[i] = v;
                Enqueue(Q, v);
        u->color = BLACK;

Breadth-First Example

Tagged with: C/C++ languageData structures

One Response to Graph search in C++

  1. Anonymous says:

    thanks! :)

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.