Algorithm: Depth First Search in Java

Graph as you must be aware is used to represent network. Network could be of any type:

1. Your friends network
2. Your work Network
3. Communication Network
4. Commute Network

As every network has nodes (src and destination) and we may have a way to reach from one to another (edge of the network).

Depth First Search as name suggest, will try to reach the last reachable node first then it retrace back and go again deep, so basically searching across the depth of each node.

for below graph breadth first search will go in below order, if our root node is 3.

3 -> 4 -> 0 -> 1 -> 2 -> 5

For the graph creation please visit:

https://maddy4java.blogspot.com/2019/11/algorithm-graph-representation.html

And for complete code: Github link

package madwani.sushil.Graph;
import madwani.sushil.model.Graph;
import madwani.sushil.model.Node;
import madwani.sushil.service.GraphService;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class DFS {

    List<Node> nodes = new ArrayList<>();
    // to keep track of nodes which are visited
    HashMap<Node, Boolean> visited = new HashMap<>();
    public void dfs(Graph g){

        if(g.getAdjacencyMap() !=null) {

            // read all the nodes
            nodes = new ArrayList<>(g.getAdjacencyMap().keySet());
            // initialize all nodes as false for visited
            initializeVisited();
            // actual algo
            // root node to start the bfs, push to queue
            Node root = new Node(1,"zero");
            doDfs(g, root);
        }
    }

    private void doDfs(Graph g, Node root) {

       // mark node as visited
        visited.put(root, true);
        // print for visibility
        System.out.print(root.getN() + " -> ");
        // for each node visit adjacent and do the above recursively
        for (Node n : g.getAdjacencyMap().get(root)) {
            if(!visited.containsKey(n) || !visited.get(n)){
                doDfs(g,n);
            }
        }

    }

    public void initializeVisited() {
        for(Node n: nodes) {
            visited.put(n, false);
        }
    }

    public static void main(String[] args) {
        GraphService service = new GraphService();
        List<Graph> graphs = service.getSampleGraphs();
        DFS dfs = new DFS();
        dfs.dfs(graphs.get(0));
    }

}