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));
    }

}

Algorithm: Graph Representation in Java Code

Suppose you have below graph , which you wanted to represent in your program. How ?

There are multiple ways to represent, but most used are:

1. Adjacency matrix

2. Adjacency list.

I will show you how can we represent the above graph using adjacency list:

First of all what does adjacency list means ? it simply is the representation where each nodes neighbors will be stored in list.

Means against each node which has the neighbor we will have linked list 

node 0 will have list of (1, 2)

node 1 will have list of (2,4,3)

so basically in java we can have a Map<Node, LinkedList<Node>> to represent the graph.

Here is the code below:

Github link

package madwani.sushil.model;

import java.util.HashMap;

import java.util.LinkedList;

public class Graph {

    private HashMap<Node, LinkedList<Node>> adjacencyMap;

    private boolean directed;

    public Graph(boolean directed) {

        this.directed = directed;

        adjacencyMap = new HashMap<>();

    }

    public HashMap<Node, LinkedList<Node>> getAdjacencyMap() {

        return adjacencyMap;

    }

    public void setAdjacencyMap(HashMap<Node, LinkedList<Node>> adjacencyMap) {

        this.adjacencyMap = adjacencyMap;
    }

}

package madwani.sushil.model;

public class Node {

    int n;
    String name;

    public Node(int n, String name) {
        this.n = n;
        this.name = name;
    }
   

    public int getN() {
        return n;
    }

    public String getName() {
        return name;
    }
}

package madwani.sushil.service;
import madwani.sushil.model.Graph;
import madwani.sushil.model.Node;
import java.util.HashMap;
import java.util.LinkedList;

public class GraphService {

    public static void main(String[] args) {

        GraphService service = new GraphService();

        service.print(service.getSampleGraph());
    }

    public void addEdge(Graph graph, Node src, Node dest) {

        HashMap<Node, LinkedList<Node>> adjMap = graph.getAdjacencyMap();

        LinkedList<Node> nodes = adjMap.get(src);

        if(nodes == null){

            nodes = new LinkedList<>();

            nodes.add(dest);

        }

        if(!nodes.contains(dest)) {

            nodes.add(dest);
        }

        adjMap.put(src,nodes);

        graph.setAdjacencyMap(adjMap);

    }

    public void print(Graph graph){

        for (Node n: graph.getAdjacencyMap().keySet()){

            LinkedList<Node> list = graph.getAdjacencyMap().get(n);

            if(list !=null && list.size()!=0) {

                System.out.print( n.getN() + " -> ");

                list.stream().forEach(e-> System.out.print(e.getN() + " -> "));

                System.out.print("null");

                System.out.println();

            }

        }

    }

    public Graph getSampleGraph(){

        Graph g = new Graph(false);

        Node _0 = new Node(0,"zero");

        Node _1 = new Node(1,"one");

        Node _2 = new Node(2,"two");

        Node _3 = new Node(3,"three");

        Node _4 = new Node(4,"four");

        Node _5 = new Node(5,"five");

        addEdge(g,_0,_1);

        addEdge(g,_0,_2);

        addEdge(g,_1,_3);

        addEdge(g,_1,_2);

        addEdge(g,_1,_4);

        addEdge(g,_2,_4);

        addEdge(g,_2,_3);

        addEdge(g,_4,_5);

        return g;

    }

}

Code Output:

0 -> 1 -> 2 -> null

2 -> 4 -> 3 -> null

1 -> 3 -> 2 -> 4 -> null

4 -> 5 -> null

Process finished with exit code 0