Simple DFS

scratch_22.java

import java.util.*;

/**
 * Implements a simple depth-first search for a graph.
 * Limitations: does not handle a disconnected graph; does not handle cases where a vertix has multiple edges towards 
 * another given vertix; each vertix is defined by its index rather than by its value.
 */
class Scratch {
    public static void main(String[] args) {
        Scratch app = new Scratch();
        Graph g = app.setupGraph();

        app.DFS(g, 2);
        System.out.println();
    }

    public void DFS(Graph g, int currentVertix) {
        g.visited.put(currentVertix, true);
        System.out.print(currentVertix + " ");

        List<Integer> edgesForCurrentVertix = g.edges.get(currentVertix);
        for (int i = 0; i < edgesForCurrentVertix.size(); i++) {
            int currentEdge = edgesForCurrentVertix.get(i);
            if (!g.visited.get(currentEdge)) {
                DFS(g, currentEdge);
            }
        }
    }

    public Graph setupGraph() {
        /*Graph g = new Graph(4);
        g.addEdge(0, new int[] {1, 2});
        g.addEdge(1, new int[] {2});
        g.addEdge(2, new int[] {0, 3});
        g.addEdge(3, new int[] {3});*/
        Graph g = new Graph(4);
        g.addEdge(0, new int[] {1, 2});
        g.addEdge(1, new int[] {2, 3});
        g.addEdge(2, new int[] {0});
        g.addEdge(3, new int[] {3});
        return g;
    }
}

class Graph {
    private int numberOfVertices;
    //key: vertix index (let's say vertices are defined by their (unique) index and not by a (possibly duplicate) value)
    // value: vertices towards which this one points
    public Map<Integer, List<Integer>> edges = new HashMap<>();
    public Map<Integer, Boolean> visited = new HashMap<>();

    public Graph(int numberOfVertices) {
        this.numberOfVertices = numberOfVertices;
        for (int i = 0; i < numberOfVertices; i++) {
            visited.put(i, false);
        }
    }

    public void addEdge(int vertix, int... destinationVertices) {
        for (int i = 0; i < destinationVertices.length; i++) {
            List<Integer> currentEdges = this.edges.get(vertix);
            if (currentEdges == null) {
                //initialise
                currentEdges = new ArrayList<>();
                this.edges.put(vertix, currentEdges);
            }
            currentEdges.add(destinationVertices[i]);
            this.edges.put(vertix, currentEdges);
        }
    }
}