1. package com.company;
2.  
3. import java.util.ArrayDeque;
4. import java.util.Deque;
5.  
6. class DFS {
7.     // tablica krawedzi ktora jest
8. // przechowuje wierzcholki z ktorych mozna sie dostac do biezacego
9. // okreslonego indeksem tablicy
10.     private int[] edgeTo;
11.     // tablica odwiedzonych wierzcholkow
12.     private boolean[] marked;
13.     // wierzcholek zrodlowy, z ktorego rozpoczynamy przeszukiwanie
14.     private final int source;
15.  
16.     public DFS(Graph graph, int source) {
17.         this.source = source;
18.         edgeTo = new int[graph.getNumberOfVertices()];
19.         marked = new boolean[graph.getNumberOfVertices()];
20.         dfs(graph, source);
21.     }
22.  
23.     /**
24.      *
25.      * @param vertex
26.      *            indeks wierzcholka dla ktorego ma byc sprawdzenie istnienia
27.      *            sciezki
28.      * @return true jesli istnieje sciezka z wierzcholka zrodlowego danego w
29.      *         konstruktorze do wierzcholka {@code vertex}
30.      */
31.     public boolean hasPathTo(int vertex) {
32.         return marked[vertex];
33.     }
34.  
35.     /**
36.      *
37.      * @param vertex
38.      *            docelowy wierzcholek
39.      * @return stos wierzcholkow prowadzacych ze zrodal {@code source} do celu
40.      *         {@code vertex} jesli sciezka nie istnieje zwracana jest pusta
41.      *         kolekcja
42.      */
43.     public Iterable<Integer> getPathTo(int vertex) {
44.         Deque<Integer> path = new ArrayDeque<Integer>();
45. // jesli nie istnieje sciezka zwroc pusta sciezke
46.         if (!hasPathTo(vertex)) {
47.             return path;
48.         }
49. // dopoki istnieje wierzcholek dodawaj go do stosu
50.         for (int w = vertex; w != source; w = edgeTo[w]) {
51.             path.push(w);
52.         }
53. // dodaj na koniec krawedz zrodlowa
54.         path.push(source);
55.         return path;
56.     }
57.  
58.     public void dfs(Graph graph, int vertex) {
59. // oznaczamy wierzcholek jako odwiedzony
60.         marked[vertex] = true;
61. // dla kazdego sasiedniego wierzcholka jesli nie jest oznaczony
62. // wywolujemy rekurencyjnie metode dfs, ktora odwiedzi wierzchoki i
63. // zapisze trase
64.         for (int w : graph.getAdjacencyList(vertex)) {
65.             if (!marked[w]) {
66.                 edgeTo[w] = vertex;
67.                 dfs(graph, w);
68.             }
69.         }
70.     }
71. }
72.