Depth first search in graph

Problem

Finding a vertex (node) in a graph based on depth first traversal.

Use-cases

• Finding a file within a hard drive in a file system where you know the file you search for lies somewhere deep inside.
• Path finding between vertices.

Solution

• Can be implemented using stack or recursion (which internally uses run time stack segment)

Implementation

• Language – Java 8.
• Stack based implementation. Leveraged Stack collection from JDK.
• Implemented for directed graph. Deals with cycles in the graph.
• Time complexity – O(V+E). V – Number of vertices (nodes). E – Number of edges.

package com.computepatterns.algorithms.graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

import com.computepatterns.algorithms.graph.model.Edge;
import com.computepatterns.algorithms.graph.model.Graph;
import com.computepatterns.algorithms.graph.model.Vertex;

/**
 * Depth first search for directed graph.
 * Follows the depth first traversal.
 * Similar to implementation in tree but graph may have cycles.
 * Stack or recursion can be used. Here stack is used.
 *
 * @see <a href="http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/">Geek for Geeks</a>
 */
public class DepthFirstSearch {
    /**
     * Exception thrown when the search key is not found.
     */
    class VertexNotFound extends Exception{
        VertexNotFound(String msg){
            super(msg);
        }
    }

    /**
     * Input graph
     */
    private Graph graph;

    public DepthFirstSearch(Graph graph) {
        this.graph = graph;
    }

    /**
     * Find the vertex which has the given search key
     * @param startingNode Starting vertex for traversal.
     * @param searchValue Search key
     * @return The vertext with the value.
     * @throws VertexNotFound When search key is not found.
     */
    public Vertex findVertex(Vertex startingNode, int searchValue) throws VertexNotFound{

        Stack<Vertex> stack = new Stack<>();
        stack.push(startingNode);

        while(!stack.isEmpty()){
           Vertex currentNode = stack.pop();
            // Mark the traversed node to deal with cycles.
            currentNode.setVisited(true);
            System.out.println(currentNode.getName());

            if(currentNode.getValue() == searchValue){
                return  currentNode;
            }

           for(Vertex vertex :findNeighbors(currentNode)){
               if(!vertex.isVisited())
               stack.push(vertex);
           }
        }
        throw new VertexNotFound("Vertex with search key is not found.");
    }

    /**
     * Find the neighbors of the current vertex.
     * @param currentNode
     * @return
     */
    private List<Vertex> findNeighbors(Vertex currentNode) {
        return graph.getEdges().stream().filter(edge -> edge.getSource().equals(currentNode))
                .map(edge -> edge.getDestination()).collect(Collectors.toCollection(ArrayList::new));

    }

    public static void main(String[] args) {

       /* List<Vertex> vertices = new ArrayList<>();
        Vertex vertexA = new Vertex("A", "A");
        vertexA.setValue(5);
        vertices.add(vertexA);

        Vertex vertexB = new Vertex("B", "B");
        vertexB.setValue(10);
        vertices.add(vertexB);

        Vertex vertexC = new Vertex("C", "C");
        vertexC.setValue(15);
        vertices.add(vertexC);

        Vertex vertexD = new Vertex("D", "D");
        vertexD.setValue(20);
        vertices.add(vertexD);

        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge("1", vertexA, vertexB, 0 ));
        edges.add(new Edge("1", vertexB, vertexD, 0 ));
        edges.add(new Edge("1", vertexA, vertexC, 0 ));
        edges.add(new Edge("1", vertexC, vertexD, 0 ));
        */


        //Input graph - http://d1gjlxt8vb0knt.cloudfront.net//wp-content/uploads/DFS.jpg
        // Above pic with added edge from vertex 3 - vertex 4 (new one).

        List<Vertex> vertices = new ArrayList<>();
        Vertex v0 = new Vertex("0","0");
        v0.setValue(0);
        vertices.add(v0);
        Vertex v1 = new Vertex("1", "1");
        v1.setValue(1);
        vertices.add(v1);
        Vertex v2 = new Vertex("2", "2");
        v2.setValue(2);
        vertices.add(v2);
        Vertex v3 = new Vertex("3", "3");
        vertices.add(v3);
        v3.setValue(3);
        Vertex v4 = new Vertex("4", "4");
        vertices.add(v4);
        v4.setValue(4);

        List<Edge> edges = new ArrayList<>();
        Edge e0 = new Edge("0", v0, v1, 0);
        edges.add(e0);
        Edge e1 = new Edge("0", v0, v2, 0);
        edges.add(e1);
        Edge e2 = new Edge("0", v2, v0, 0);
        edges.add(e2);
        Edge e3 = new Edge("0", v1, v2, 0);
        edges.add(e3);
        Edge e4 = new Edge("0", v2, v3, 0);
        edges.add(e4);
        Edge e5 = new Edge("0", v3, v3, 0);
        edges.add(e5);
        Edge e6 = new Edge("0", v3, v4, 0);
        edges.add(e6);

        Graph graph = new Graph(vertices, edges);
        try {
            Vertex vertex = new DepthFirstSearch(graph).findVertex(v2, 1);
            System.out.printf("Search key found in vertex - %s", vertex.getId());

        } catch (VertexNotFound vertexNotFound) {
            vertexNotFound.printStackTrace();
        }
    }
}

Link to github code.

References

• https://en.wikipedia.org/wiki/Depth-first_search
• http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/