Breadth First Search - BFS | mymagnadata

http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
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.
Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.

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);

            }

        }

    }

}

https://gist.github.com/gennad/791932
public class Node {
public String data; // data element
public boolean visited=false; // flag to track the already visited node
public List adjacentNodes = new LinkedList(); // adjacency list

public Node(String data){
this.data = data;
}

public void addAdjacentNode(final Node node){
adjacentNodes.add(node);
node.adjacentNodes.add(this);
}

}
public void breadthFirstTraversal(Node rootNode){
Queue q = new LinkedList();
q.add(rootNode);
rootNode.visited=true;
while(!q.isEmpty()){
Node n = (Node)q.poll();
System.out.print(n.data + " ");
for(Node adj : n.adjacentNodes){
if(!adj.visited){
adj.visited=true;
q.add(adj);
}
}
}

}

- enqueue the start node to a Queue
- make the start node as visited
- while queue is not empty
  - dequeue the node lets say u
  - print or whatever you want to
  - for every adjacent node v of u
      - if v is not already visited
          - mark v as visited
          - enqueue v to the Queue


Read full article from Breadth First Search – BFS | mymagnadata