Graph Data Structure & Algorithms

Go to Problems

Example implementation of BFS and DFS

DFS :
Algorithmic Steps

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

Based upon the above steps, the following Java code shows the implementation of the DFS algorithm:


        public void dfs() {
            //DFS uses Stack data structure
            Stack s = new Stack();
            s.push(this.rootNode);
            rootNode.visited = true;
            printNode(rootNode);
            while(!s.isEmpty()) {
                Node n = (Node)s.peek();
                Node child = getUnvisitedChildNode(n);  // Essentially this function goes through the neighbors of n, and finds the one with node.visited = false
                if(child != null) {
                    child.visited = true;
                    printNode(child); // print the node as you like. 
                    s.push(child);
                }
                else {
                    s.pop();
                }
            }
            //Clear visited property of nodes
            clearNodes();
        }
BFS
Algorithmic Steps

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

Based upon the above steps, the following Java code shows the implementation of the BFS algorithm:

        public void bfs() {
            //BFS uses Queue data structure
            Queue q = new LinkedList();
            q.add(this.rootNode);
            printNode(this.rootNode);
            rootNode.visited = true;
            while(!q.isEmpty()) {
                Node n = (Node)q.remove();
                Node child = null;
                while((child = getUnvisitedChildNode(n)) != null) {
                    child.visited = true;
                    printNode(child);
                    q.add(child);
                }
            }
            //Clear visited property of nodes
            clearNodes();
        }

Serious about Learning Programming ?

Learn this and a lot more with Scaler Academy's industry vetted curriculum which covers Data Structures & Algorithms in depth.

Graph Data Structure & Algorithms Problems

Graph adhoc
Problem Score Companies Time Status
Convert Sorted List to Binary Search Tree 300
44:59
Graph hashing
Problem Score Companies Time Status
Clone Graph 500 57:22
lock
Topic Bonus
Bonus will be unlocked after solving min. 1 problem from each bucket