Table of contents


Given problem

Assuming that we have a graph that is described in a below image.

   1
 /   \
2     3
|  \  |
4 -- 5
 \  /
  6


Definition of Graph

  1. Use adjacency list version

     public class ALGraph {
     private ArrayList<List<Node>> graphs;

     public ALGraph(int capacity) {
         this.graphs = new ArrayList<>(capacity);
         for (int i = 0; i < capacity; ++i) {
             this.graphs.add(new LinkedList<>());
         }
     }

     public List<Node> getNodesWith(int vertex) {
         return this.graphs.get(vertex);
     }

     /**
     * an edge from u vertex to v vertex and vice versa
     *
     * @param u
     * @param v
     */
     public void addEdge(Node u, Node v) {
         Objects.requireNonNull(u);
         Objects.requireNonNull(v);

         this.graphs.get(u.value).add(v);
         this.graphs.get(v.value).add(u);
     }

     public void display() {
         int len = this.graphs.size();
         for (int i = 1; i < len; ++i) {
             List<Node> nodes = this.graphs.get(i);

             System.out.println("Vertex " + i + " connect with: ");
             for (Node node : nodes) {
                 System.out.print(" --> " + node.value + " ");
             }

             System.out.println();
         }
     }
 }

 public class Demo {
     public static void main(String[] args) {
         int capacity = 7;
         ALGraph graph = initALGraph(capacity);
         boolean[] visited = new boolean[capacity];

         dfs(graph, visited, new Node(1));
     }

     public static ALGraph initALGraph(int capacity) {
         ALGraph graph = new ALGraph(capacity);

         graph.addEdge(new Node(1), new Node(2));
         graph.addEdge(new Node(1), new Node(3));
         graph.addEdge(new Node(2), new Node(4));
         graph.addEdge(new Node(2), new Node(5));
         graph.addEdge(new Node(3), new Node(5));
         graph.addEdge(new Node(4), new Node(5));
         graph.addEdge(new Node(4), new Node(6));
         graph.addEdge(new Node(5), new Node(6));
         return graph;
     }
 }

  2. Using adjacency matrix version

     public class AMGraph {
     private int[][] graph;
     private int capacity;

     public AMGraph(int capacity) {
         this.capacity = capacity;
         this.graph = new int[capacity][capacity];
     }

     public int getCapacity() {
         return this.capacity;
     }

     public boolean isAnEdge(int u, int v) {
         return this.graph[u][v] == 1;
     }

     public void addEdge(int u, int v) {
         this.graph[u][v] = 1;
         this.graph[v][u] = 1;
     }

     public void display() {
         for (int i = 1; i < this.capacity; ++i) {
             System.out.println("Vertex " + i + " connect with: ");

             for (int j = 1; j < this.capacity; ++j) {
                 if (this.graph[i][j] == 1) {
                     System.out.print(" --> " + j + " ");
                 }
             }

             System.out.println();
         }
     }
 }

 public class Demo {
     public static void main(String[] args) {
         int capacity = 7;
         AMGraph graph = new AMGraph(capacity);
         boolean[] visited = new boolean[capacity];

         dfs(graph, visited, 1);
     }

     public void initAMGraph(int capacity) {
         AMGraph graph = new AMGraph(capacity);

         graph.addEdge(1, 2);
         graph.addEdge(1, 3);
         graph.addEdge(2, 4);
         graph.addEdge(2, 5);
         graph.addEdge(3, 5);
         graph.addEdge(4, 5);
         graph.addEdge(4, 6);
         graph.addEdge(5, 6);
         return graph;
     }
 }


Using recursive version

  1. In adjacency list version

     /**
 * Using recursive version
 *
 * Result: 1 --> 2 --> 4 --> 5 --> 3 --> 6
 *
 * @param graph
 * @param visited
 * @param node
 */
 public static void dfs(ALGraph graph, boolean[] visited, Node node) {
     Objects.requireNonNull(node);

     if (visited[node.value]) {
         return;
     }

     visited[node.value] = true;
     System.out.print("" + node.value + " --> ");

     List<Node> nodes = graph.getNodesWith(node.value);
     for (Node tmpNode : nodes) {
         dfs(graph, visited, tmpNode);
     }
 }

    The dfs in the recursive version is as same as the source code in Preorder traversal in Binary Tree.

    Using a boolean array - visited to mark nodes that is iterated. It makes us do not touch it in twice times.

  2. In adjacency matrix version

     public static void dfs(AMGraph graph, boolean[] visited, int node) {
     System.out.print("" + node + " --> ");
     visited[node] = true;

     for (int i = 1; i < graph.getCapacity(); ++i) {
         if (graph.isAnEdge(node, i) && !visited[i]) {
             dfs(graph, visited, i);
         }
     }
 }


Using iterative version

  1. In adjacency list version

     public static void dfsUnRecursive(ALGraph graph, boolean[] visited) {
     Stack<Node> stkNodes = new Stack<>();
     stkNodes.push(new Node(1));

     while (!stkNodes.isEmpty()) {
         Node topNode = stkNodes.pop();

         // prepare for the node iterate in twice times
         if (!visited[topNode.value]) {
             visited[topNode.value] = true;
             System.out.print("" + topNode.value + " --> ");
         }

         List<Node> childNodes = graph.getNodesWith(topNode.value);
         for (Node tmpNode : childNodes) {
             if (!visited[tmpNode.value]) {
                 stkNodes.push(tmpNode);
             }
         }
     }
 }


Applications of DFS

  • Minimum spanning tree

  • Detecting cycle in the graph

  • Find path between the two vertices

  • Topological sorting

  • Check bipartite graph

  • Find the strongly connected components

  • Maze solution


Wrapping up