Depth First Traversal for a Graph | GeeksforGeeks

http://www.geeksforgeeks.org/iterative-depth-first-traversal/

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal (DFS) of a tree. 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.

Also check http://massivealgorithms.blogspot.com/2014/12/bfs-dfs-java.html
Depth First Traversal for a Graph | GeeksforGeeks
To avoid processing a node more than once, we use a boolean visited array. 
http://www.cs.ucf.edu/~dmarino/progcontests/modules/graph1/DFS_BFS.java
http://cs-people.bu.edu/kvodski/teaching/spring10/solutions/DFS.java
DFS for all nodes:

 void DFS()
 {
  boolean[] V=new boolean[N]; // a visited array to mark which vertices have been visited while doing the DFS
  int numComponets=0; // the number of components in the graph
  // do the DFS from each node not already visited
  for (int i=0; i<N; ++i)
   if (!V[i])
   {
    ++numComponets;
    System.out.printf("Starting a DFS for component %d starting at node %d%n",numComponets,i);
    
    DFS(i,V);
   }
 }
 void DFS(int at, boolean[] V)
 {
  // mark that we are visiting this node
  V[at]=true;
  for (int i=0; i<N; ++i)
   if (G[at][i] && !V[i])
   {
    System.out.printf("Going to node %d...",i);
    DFS(i,V);
   }
 }

https://github.com/lgrcyanny/Algorithm/blob/master/src/com/algorithm/graph/GraphDFS.java
Java code http://algs4.cs.princeton.edu/41undirected/DepthFirstSearch.java.html

public class DepthFirstSearch {
    private boolean[] marked;    // marked[v] = is there an s-v path?
    private int count;           // number of vertices connected to s
     * @param s the source vertex
     */
    public DepthFirstSearch(Graph G, int s) {
        marked = new boolean[G.V()];
        dfs(G, s);
    }
    // depth first search from v
    private void dfs(Graph G, int v) {
        count++;
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
    }

}
Iterative Version
http://algs4.cs.princeton.edu/41undirected/NonrecursiveDFS.java
http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Graph/dfs.html
http://stackoverflow.com/questions/21508765/how-to-implement-depth-first-search-for-graph-with-non-recursive-aprroach

void dfs(GraphNode node) {
    // sanity check
    if (node == null) {
        return;
    }
    // use a hash set to mark visited nodes
    Set<GraphNode> set = new HashSet<GraphNode>();

    // use a stack to help depth-first traversal
    Stack<GraphNode> stack = new Stack<GraphNode>();
    stack.push(node);

    while (!stack.isEmpty()) {
        GraphNode curr = stack.pop();

        // current node has not been visited yet
        if (!set.contains(curr)) {
            // visit the node
            // ...

            // mark it as visited
            set.add(curr);
        }

        for (int i = 0; i < curr.neighbors.size(); i++) {
            GraphNode neighbor = curr.neighbors.get(i);
            // this neighbor has not been visited yet
            if (!set.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
}

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

public void dfs() {


// DFS uses Stack data structure


Stack stack = new Stack();


stack.push(this.rootNode);


rootNode.visited=true;


printNode(rootNode);


while(!stack.isEmpty()) {


Node node = (Node)s.peek();


Node child = getUnvisitedChildNode(n);


if(child != null) {


child.visited = true;


printNode(child);


s.push(child);


}


else {


s.pop();


}


}


// Clear visited property of nodes


clearNodes();


}

We can avoid using recursion by pushing active nodes onto a stack

    dfs()
    {
       pick a node x....
       push(x);
       visited[x] = true;

       while ( stack != empty )
       {
          n = node at stack top (peek only);

   nextNode = an unvisited node adjacent to n;

   if ( nextNode exists )
   {
      visited[nextNode] = true;

      push(nextNode);               // Process this node first
          }
   else
   {  /* -----------------------------------------------------
         Node at top of stack has no unvisited neighbor nodes
  ----------------------------------------------------- */     
      pop();       // Move on to the next node on the stack
          } 
       }
    }

public class NonrecursiveDFS {
    private boolean[] marked;  // marked[v] = is there an s-v path?
    public NonrecursiveDFS(Graph G, int s) {
        marked = new boolean[G.V()];

        // to be able to iterate over each adjacency list, keeping track of which
        // vertex in each adjacency list needs to be explored next
        Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()];
        for (int v = 0; v < G.V(); v++)
            adj[v] = G.adj(v).iterator();

        // depth-first search using an explicit stack
        Stack<Integer> stack = new Stack<Integer>();
        marked[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int v = stack.peek();
            if (adj[v].hasNext()) {
                int w = adj[v].next();
                if (!marked[w]) {
                    // discovered vertex w for the first time
                    marked[w] = true;
                    // edgeTo[v] = w;
                    stack.push(w);
                }
            }
            else {
                // v's adjacency list is exhausted
                stack.pop();
            }
        }
    }

}
http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

class Graph

{

    private int V;   // No. of vertices

 

    // Array  of lists for Adjacency List Representation

    private LinkedList<Integer> adj[];

 

    // Constructor

    Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

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

            adj[i] = new LinkedList();

    }

 

    //Function to add an edge into the graph

    void addEdge(int v, int w)

    {

        adj[v].add(w);  // Add w to v's list.

    }

 

    // A function used by DFS

    void DFSUtil(int v,boolean visited[])

    {

        // Mark the current node as visited and print it

        visited[v] = true;

        System.out.print(v+" ");

 

        // Recur for all the vertices adjacent to this vertex

        Iterator<Integer> i = adj[v].listIterator();

        while (i.hasNext())

        {

            int n = i.next();

            if (!visited[n])

                DFSUtil(n,visited);

        }

    }

 

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

    void DFS()

    {

        // Mark all the vertices as not visited(set as

        // false by default in java)

        boolean visited[] = new boolean[V];

 

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

    }

}

class Graph

{

    int V;    // No. of vertices

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

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

}

// DFS traversal of the vertices reachable from v. It uses recursive DFSUtil()

void Graph::DFS(int v)

{

    // 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

    DFSUtil(v, visited);

}

Iterative Depth First Traversal of Graph

// prints all not yet visited vertices reachable from s

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

{

    // Create a stack for DFS

    stack<int> stack;

 

    // Mark the current node as visited and push it

    visited[s] = true;

    stack.push(s);

 

    // 'i' will be used to get all adjacent vertices

    // of a vertex

    list<int>::iterator i;

 

    while (!stack.empty())

    {

        // Pop a vertex from stack and print it

        s = stack.top();

        cout << s << " ";

        stack.pop();

 

        // Get all adjacent vertices of the popped vertex s

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

        // visited and push it to the stack

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

        {

            if (!visited[*i])

            {

                visited[*i] = true;

                stack.push(*i);

            }

        }

    }

}

 

// prints all vertices in DFS manner

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;

 

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

        if (!visited[i])

           DFSUtil(i, visited);

}

Breadth First Traversal for a Graph

    // prints BFS traversal from a given source s

    void BFS(int s)

    {

        // Mark all the vertices as not visited(By default

        // set as false)

        boolean visited[] = new boolean[V];

 

        // Create a queue for BFS

        LinkedList<Integer> queue = new LinkedList<Integer>();

 

        // Mark the current node as visited and enqueue it

        visited[s]=true;

        queue.add(s);

 

        while (queue.size() != 0)

        {

            // Dequeue a vertex from queue and print it

            s = queue.poll();

            System.out.print(s+" ");

 

            // Get all adjacent vertices of the dequeued vertex s

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

            // visited and enqueue it

            Iterator<Integer> i = adj[s].listIterator();

            while (i.hasNext())

            {

                int n = i.next();

                if (!visited[n])

                {

                    visited[n] = true;

                    queue.add(n);

                }

            }

        }

    }

Read full article from Depth First Traversal for a Graph | GeeksforGeeks