Depth First Search Algorithm implementation in Java.

Graph with it’s adjacency list representation.

Depth First Search(DFS) Algorithm is used for the graph traversal and it internally uses a stack which follows LIFO(Last In First Out) principle. In DFS we are trying to go away from the starting source vertex into the graph as deep as possible until we have to backtrack to the preceding vertex.

Initially all the vertices are marked unvisited(false). The DFS algorithm starts at the vertex u in the graph. By starting at vertex u it considers the edges from u to other vertices. If the edge leads to an already visited vertex, then backtrack to current vertex u. If the edge leads to an unvisited vertex, then go to that vertex and start processing from that vertex. This means the new vertex becomes current vertex. Follow this procedure until we reach dead-end. At this point start backtracking.

Code :

import java.util.*;
class Graph {

    private int V;
    private LinkedList<Integer> adj[];

    Graph(int v)
    {
        V=v;
        adj=new LinkedList[v];
        for(int i=0;i<v;i++)
        {
            adj[i]=new LinkedList();
        }
    }

    void addEdge(int v,int w)
    {
        adj[v].add(w);
    }
    void DFS(int v)
    {
        boolean visited[]= new boolean[V];

        DFS1(v,visited);
    }

    void DFS1(int v, boolean visited[])
    {
        visited[v]=true;
        System.out.print(v+" -> ");

        Iterator<Integer> i = adj[v].listIterator();
        while(i.hasNext())
        {
            int n = i.next();
            if(!visited[n]) {
                DFS1(n,visited);
            }
        }
    }

    public static void main(String arg[]) {
        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);

        g.DFS(2);//source
    }

}

Time Complexity : O(V + E)

Applications :

1- Topological Sorting

2-Detection of Cycle in Graph

3-For unweighted graph, DFS produces minimum spanning tree.

Thanks for reading! 🙂

Video Link (Hindi) : https://www.youtube.com/watch?v=vlKl-rHzpFs&lc=z22qixea4sbpgrxbt04t1aokgajxoanftpn5bm2x34ribk0h00410

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website at WordPress.com
Get started
%d bloggers like this: