Graph BFS DFS Java

http://www.sanfoundry.com/java-program-traverse-graph-using-bfs/
http://www.codeproject.com/Articles/32212/Introduction-to-Graph-with-Breadth-First-Search-BF
BFS

1. Step 1: Push the root node in the Queue.
2. Step 2: Loop until the queue is empty.
3. Step 3: Remove the node from the Queue.
4. Step 4: If the removed node has unvisited child nodes, mark them as visited and insert the unvisited children in the queue.

If we somehow want to to use BFS to iterate all nodes, just add a wrapper with a for loop that wil check whether node is visited, if not call bfs(node).

public class BFS
{
    private Queue<Integer> queue;
    public BFS()
    {
        queue = new LinkedList<Integer>();
    }
    public void bfs(int adjacency_matrix[][], int source)
    {
        int number_of_nodes = adjacency_matrix[source].length - 1;

        int[] visited = new int[number_of_nodes + 1];
        int i, element;

        visited[source] = 1;
        queue.add(source);

        while (!queue.isEmpty())
        {
            element = queue.remove();
            i = element;
            System.out.print(i + "\t");
            while (i <= number_of_nodes)
            {
                if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
                {
                    queue.add(i);
                    visited[i] = 1;
                }
                i++;
            }
        }
    }
}
Also check http://massivealgorithms.blogspot.com/2014/07/depth-first-traversal-for-graph.html
DFS

1. Step 1: Push the root node in the Stack.  
2. Step 2: Loop until stack is empty. 
3. Step 3: Peek the node of the stack.  
4. Step 4: If the node has unvisited child nodes, get the unvisited child node, mark it as traversed and push it on stack.   
5. Step 5: If the node does not have any unvisited child nodes, pop the node from the stack.

private Stack<Integer> stack;

public DFS()
{
    stack = new Stack<Integer>();
}

public void dfs(int adjacency_matrix[][], int source)
{
    int number_of_nodes = adjacency_matrix[source].length - 1;

    int visited[] = new int[number_of_nodes + 1];
    int element = source;
    int i = source;
    System.out.print(element + "\t");
    visited[source] = 1;
    stack.push(source);

    while (!stack.isEmpty())
    {
        element = stack.peek();
        i = element;
  while (i <= number_of_nodes)
  {
          if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
      {
                stack.push(i);
                visited[i] = 1;
                element = i;
                i = 1;
                System.out.print(element + "\t");
          continue;
            }
            i++;
  }
        stack.pop();
    }
}
http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

class Graph

{

    int V;    // No. of vertices

    list<int> *adj;    // Pointer to an array containing adjacency lists

    void DFSUtil(int v, bool visited[]);  // A function used by DFS

}

void Graph::DFSUtil(int v, bool visited[])

{

    // Mark the current node as visited and print it

    visited[v] = true;

    cout << v << " ";

    // Recur for all the vertices adjacent to this vertex

    list<int>::iterator i;

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

        if(!visited[*i])

            DFSUtil(*i, visited);

}

// The function to do DFS traversal. It uses recursive DFSUtil()

void Graph::DFS()

{

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

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

        visited[i] = false;

    // Call the recursive helper function to print DFS traversal

    // starting from all vertices one by one

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

        if(visited[i] == false)

            DFSUtil(i, visited);

}

http://www.algolist.net/Algorithms/Graph/Undirected/Depth-first_search

enum VertexState {

          White, Gray, Black 

      }

     

      public void DFS()

      {

            VertexState state[] = new VertexState[vertexCount];

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

                  state[i] = VertexState.White;

            runDFS(0, state);

      }

     

      public void runDFS(int u, VertexState[] state)

      {

            state[u] = VertexState.Gray;

            for (int v = 0; v < vertexCount; v++)

                  if (isEdge(u, v) && state[v] == VertexState.White)

                        runDFS(v, state);

            state[u] = VertexState.Black;

      }

http://www.cs.toronto.edu/~heap/270F02/node36.html

      DFS(G,v)   ( v is the vertex where the search starts )
         Stack S := {};   ( start with an empty stack )
         for each vertex u, set visited[u] := false;
         push S, v;
         while (S is not empty) do
            u := pop S;
            if (not visited[u]) then
               visited[u] := true;
               for each unvisited neighbour w of u
                  push S, w;
            end if
         end while
      END DFS()

What happens if our original graph  isn't connected? Then DFS(G,v) won't visit any vertices that aren't connected to its starting point. You'll need an outer loop that iterates over unvisited vertices, and then calls DFS(G,V).