Depth First Search [DFS]

Graph traversal algorithms are also called graph search algorithm.

Two such algorithms for traversing the graphs :

• Depth First Search [DFS]
• Breadth First Search [BFS]

Depth First Search [DFS]:

DFS algorithm works in a manner similar to a preorder traversal of the trees.

We encountered the following types of edge:

• Tree edge: encounter new vertex.
• Back edge: from descendant to ancestor.
• Forward edge: from ancestor to descendant.
• Cross edge: between a tree or subtree.

To track the vertices two colours are enough:

• false → Vertex is unvisited.
• true  → Vertex is visited.

Source code in Java:

import java.util.LinkedList;

import java.util.Iterator;

/**

 *

 * @author Rohan

 */

public 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.

    }

    

    void DFSUtil(int j,boolean visited[])

    {

        // Mark the current node as visited and print it

        visited[j] = true;

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

        // Recur for all the vertices adjacent to this vertex

        Iterator<Integer> i = adj[j].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(int i)

    {

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

        DFSUtil(i, visited);

    }

    

    public static void main(String args[])

    {

        Graph g = new Graph(4);

        g.addEdge(0, 1);

        g.addEdge(0, 2);

        g.addEdge(1, 2);

        g.addEdge(2, 0);

        g.addEdge(2, 3);

        g.addEdge(3, 3);

        System.out.println("Following is Depth First Traversal "+

                           "(starting from vertex 2)");

        g.DFS(2);

    }

}

Output:

Following is Depth First Traversal (starting from vertex 2)

2 0 1 3

Explanation: