Graph Traversal: Program to traverse a graph using depth first search (dfs) technique

Depth First Search

Depth first search is a traversal algorithm for graph or tree type of data structures. In traversal, we visit each node or vertice of the graph or tree. DFS is one way of traversing the nodes in a graph or tree. 

DFS follows a particular order of visiting nodes in a graph:

• We start with any node from the graph. Its know as root node or start node. Lets name it n1
• We then visit one of the neighbor nodes of n1. Lets call it n2 (here n1 is parent node of n2)
• We then pick one of the neighbor node of n2 and visit it
• This way we traverse by going in depth of a particular node
• When we reach an already visited node, we search for another neighbor of parent node and try to go in its depth
• While doing this we need to make sure we are not visiting an already visited node, and for this while visiting a node, we mark the node visited by capturing it in a map or similar data structure where we can refer in constant time whether a node is visited or not
• Once all the nodes are visited using above approach we have completed the dfs traversal for that graph

Java Code

    import java.io.*;
    import java.util.*;
    
    class GraphDFS{
        
        private HashSet visitedTracking = new HashSet();
        private LinkedList queue = new LinkedList();
    
        static class Node{
    
            private int id;
            LinkedList adjacent = new LinkedList();
    
            private Node(int id){
                this.id = id;
            }
    
        }
     
        //Function to add an edge into the graph
        public void addEdge(Node a, Node b)
        {
            a.adjacent.add(b);
            b.adjacent.add(a); 
        }
    
        public void traverseDFS(Node root){
            
            if(root == null){
                return ;
            }
    
            visitedTracking.add(root.id);
            System.out.println(root.id);
    
            for(Node child : root.adjacent){
                if(!visitedTracking.contains(child.id)){
                    traverseDFS(child);
                }
            }
        }
    
        public static void main(String args[]){
    
            GraphDFS gS = new GraphDFS();
        
            Node a1 = new Node(1);
            Node a2 = new Node(2);
            Node a3 = new Node(3);
            Node a4 = new Node(4);
            Node a7 = new Node(7);
            Node a9 = new Node(9);
            Node a12 = new Node(12);
            Node a5 = new Node(5);
            Node a8 = new Node(8);
            Node a6 = new Node(6);
    
            gS.addEdge(a1,a9);
            gS.addEdge(a1,a3);
            gS.addEdge(a1,a4);
            gS.addEdge(a3,a7);
            gS.addEdge(a7,a2);
            //gS.addEdge(a2,a4);
            gS.addEdge(a2,a6);
            gS.addEdge(a4,a5);
            gS.addEdge(a4,a12);
            gS.addEdge(a6,a8);
    
            gS.traverseDFS(a4); // traversing the graph using dfs technique from node 4
    
        }
    }

Output

4
1
9
3
7
2
6
8
5
12