Breadth First Search (BFS) - Graphs

In BFS, there is a notion of starting vertex. BFS visits all the vertices of a connected graph, and in the process of doing so it labels all the vertices with a distance value, which is equal to the length of the shortest path from the starting vertex to all the other vertices.

BFS starting at vertex s, partitions the graph into levels: s itself, the nodes at distance 1 from it, the nodes at distance 2 from it, and so on. A convenient way to compute distances from s to the other vertices is to proceed level by level. Once we have picked out the nodes at distance 0, 1, 2, . . . , d, the ones at d + 1 are easily determined: they are precisely the as-yet-unseen nodes that are adjacent to the level at distance d. This suggests an iterative algorithm in which two level are active at any given time: some level d, which has been fully identified, and d + 1, which is being discovered by scanning the neighbors of level d.

Algorithm:

Let V and E denote the set of vertices and edges of a graph G.

s = starting vertex.

dist[] = distance of vertices from s
BFS(G, V, E, s) :

Input: Graph G = (V, E), directed or undirected; vertex s ∈ V

Output: For all vertices u reachable from s, dist(u) is set to the distance from s to u.

for all u ∈ V : dist(u) = ∞

visited[s] = true;

dist[s] = 0;

Q.push(s);

while (!Q.empty()) :

int v = Q.front();

Q.pop();

for all vertices w adjacent to v :

if(!visited[w]) :

Q.push(w);

visited[w] = true;

dist[w] = dist[v] + 1;

Implementation:

/*

* BFS.cpp

*

* Created on: Feb 14, 2015

* Author: CodingTonic

*/

#include <iostream>

#include <list>

#include <queue>

using namespace std;

#define INF 100

// Structure for a graph node or vertex

struct Node

{

    int vert;

    int weight; /* Useful for weighted graphs, set to 1 here */

    Node(int _v, int _w = 1): vert(_v), weight(_w){}

};

class Graph

{

    int numVert; /* number of vertices in graph */

    list<Node> *adjList;

public:

    // Constructor for Graph class

    Graph(int nV): numVert(nV)

    {

        adjList = new list<Node>[nV];

    }

    // Destructor for Graph class

    ~Graph()

    {

        delete []adjList;

    }

    void AddEdge(int u, int v, int w = 1)

    {

        adjList[u].push_back(Node(v, w));

    }

    // Main function for Breadth-first traversal of Graph

    void BFS(int s, int num, bool bVisited[], int dist[])

    {

        queue<int> Q;

        Q.push(s);

        dist[s] = 0;

        bVisited[s] = true;

        while(!Q.empty())

        {

            int v = Q.front();

            Q.pop();

            list<Node>::iterator it;

            for(it = adjList[v].begin(); it != adjList[v].end(); it++)

            {

                if(!bVisited[it->vert])

                {

                    Q.push(it->vert);

                    bVisited[it->vert] = true;

                    dist[it->vert] = dist[v] + 1;

                }

            }

        }

    }

};

// main function

int main(int argc, char* argv[])

{

    Graph G(5);

    G.AddEdge(0, 1);

    G.AddEdge(1, 0);

    G.AddEdge(0, 3);

    G.AddEdge(3, 0);

    G.AddEdge(1, 2);

    G.AddEdge(2, 1);

    G.AddEdge(1, 3);

    G.AddEdge(3, 1);

    G.AddEdge(2, 4);

    G.AddEdge(4, 2);

    G.AddEdge(3, 2);

    G.AddEdge(2, 3);

    G.AddEdge(3, 4);

    G.AddEdge(4, 3);

    bool visited[5] = {false, false, false, false, false};

    int dist[5] = {INF, INF, INF, INF, INF};

    G.BFS(0, 5, visited, dist);

    for(int i=0; i<5; i++)

    {

        cout << "visited[" << i << "] = " << visited[i] << ", dist[" << i << "] = " << dist[i] << endl;

    }

    return (0);

}

/*         

 *  [0]-------[1]---------[2]

 *     \        |        / |

 *      \       |       /  |

 *       \      |      /   |

 *        \     |     /    |

 *         \    |    /     |

 *          \   |   /      |

 *           \  |  /       |

 *            [3]---------[4]

 */

Output:
visited[0] = 1, dist[0] = 0
visited[1] = 1, dist[1] = 1
visited[2] = 1, dist[2] = 2
visited[3] = 1, dist[3] = 1
visited[4] = 1, dist[4] = 2