Breadth First Traversal for a Graph - GeeksforGeeks

Breadth First Traversal for a Graph - GeeksforGeeks
readth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree (See mthod 2 of this post). The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.

http://algs4.cs.princeton.edu/41undirected/BreadthFirstPaths.java.html

    private void bfs(Graph G, int s) {
        Queue<Integer> q = new Queue<Integer>();
        for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY;
        distTo[s] = 0;
        marked[s] = true;
        q.enqueue(s);

        while (!q.isEmpty()) {
            int v = q.dequeue();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    distTo[w] = distTo[v] + 1;
                    marked[w] = true;
                    q.enqueue(w);
                }
            }
        }
    }

https://gist.github.com/gennad/791932

 public void bfs()


 {


  // BFS uses Queue data structure


  Queue queue = new LinkedList();


  queue.add(this.rootNode);


  printNode(this.rootNode);


  rootNode.visited = true;


  while(!queue.isEmpty()) {


   Node node = (Node)queue.remove();


   Node child=null;


   while((child=getUnvisitedChildNode(node))!=null) {


    child.visited=true;


    printNode(child);


    queue.add(child);


   }


  }


  // Clear visited property of nodes


  clearNodes();


 }

We can add another loop which will check all nodes, is not visited, call BFS(node).

void Graph::BFS(int s)

{

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

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

        visited[i] = false;

 

    // Create a queue for BFS

    list<int> queue;

 

    // Mark the current node as visited and enqueue it

    visited[s] = true;

    queue.push_back(s);

 

    // 'i' will be used to get all adjacent vertices of a vertex

    list<int>::iterator i;

 

    while(!queue.empty())

    {

        // Dequeue a vertex from queue and print it

        s = queue.front();

        cout << s << " ";

        queue.pop_front();

 

        // Get all adjacent vertices of the dequeued vertex s

        // If a adjacent has not been visited, then mark it visited

        // and enqueue it

        for(i = adj[s].begin(); i != adj[s].end(); ++i)

        {

            if(!visited[*i])

            {

                visited[*i] = true;

                queue.push_back(*i);

            }

        }

    }

}

Read full article from Breadth First Traversal for a Graph - GeeksforGeeks