Почему BFS работает намного быстрее, чем DFS, когда я реализую их оба?

Я пытаюсь использовать DFS и BFS, чтобы найти все простые пути длиной до заданного k, начиная с заданной вершины ориентированного графа. Никакие циклы не допускаются.

Мой код выглядит следующим образом, и я проверил, что оба алгоритма дают правильные результаты.

Я определяю класс графа и помещаю в этот класс код BFS и DFS. В нужном мне графе около 190 000 вершин и 2 500 000 ребер. Средняя исходящая степень каждой вершины равна 105:

public class AdjGraph {
    private int V; // sum of vertices
    private int E; // sum of edges
    private List<Vertex> vertexList;
    private Map<Vertex, List<Edge>> vertexAdj;
    
    public AdjGraph() {
        this.V = 0;
        this.E = 0;
        this.vertexList = new ArrayList<>();
        this.vertexAdj = new HashMap<>();
    }

    public void addVertex(Vertex v) {
        this.vertexList.add(v);
        this.vertexAdj.put(v, new ArrayList<>());
        this.V++;
    }

    public void addEdge(Edge e) {
        Vertex startVertex = e.getStartVertex();
        List<Edge> edgeList = this.vertexAdj.get(startVertex);

        if (!edgeList.contains(e)) {
            edgeList.add(e);
            this.vertexAdj.put(startVertex, edgeList);
        }
    }

    public List<Vertex> getVertexList() {
        return vertexList;
    }

    // Version of DFS
    public Map<Integer, List<List<Vertex>>> findAllPathsUpToLengthByDFS(Vertex start, int k) {
        boolean[] visited = new boolean[vertexList.size()];
        List<Vertex> path = new ArrayList<>();
        Map<Integer, List<List<Vertex>>> allPaths = new HashMap<>();
        findAllPathsUpToLengthByDFSUtil(start, k, visited, path, allPaths);
        return allPaths;
    }

    // Used by the function findAllPathsUpToLengthByDFS(...)
    private void findAllPathsUpToLengthByDFSUtil(Vertex u, int k, boolean[] visited, List<Vertex> path, Map<Integer, List<List<Vertex>>> allPaths) {
        // Mark the current node as visited and store in path
        visited[vertexList.indexOf(u)] = true;
        path.add(u);

        // If current path length exceeds k, backtrack
        if (path.size() - 1 > k) {
            visited[vertexList.indexOf(u)] = false;
            path.remove(path.size() - 1);
            return;
        }

        // If current path length is within k, add it to allPaths
        int pathLength = path.size() - 1;
        if (pathLength <= k) {
            allPaths.computeIfAbsent(pathLength, x -> new ArrayList<>()).add(new ArrayList<>(path));
        }

        // Recur for all the vertices adjacent to this vertex
        for (Edge edge : vertexAdj.get(u)) {
            Vertex v = edge.getEndVertex();
            if (!visited[vertexList.indexOf(v)]) {
                findAllPathsUpToLengthByDFSUtil(v, k, visited, path, allPaths);
            }
        }

        // Remove current vertex from path and mark it as unvisited
        path.remove(path.size() - 1);
        visited[vertexList.indexOf(u)] = false;
    }

    // Version of BFS
    public Map<Integer, List<List<Vertex>>> findAllPathsUpToLengthByBFS(Vertex start, int k) {
        Map<Integer, List<List<Vertex>>> allPaths = new HashMap<>();
        Queue<List<Vertex>> queue = new LinkedList<>();

        // Initialize the queue with the start vertex
        List<Vertex> startPath = new ArrayList<>();
        startPath.add(start);
        queue.add(startPath);

        while (!queue.isEmpty()) {
            List<Vertex> path = queue.poll();
            Vertex last = path.get(path.size() - 1);

            // Add the path to allPaths if its length is within k
            int pathLength = path.size() - 1;
            if (pathLength <= k) {
                allPaths.computeIfAbsent(pathLength, x -> new ArrayList<>()).add(new ArrayList<>(path));
            }

            // If the path length is already k, no need to explore further
            if (pathLength < k) {
                // Explore the neighbors of the last vertex in the path
                for (Edge edge : vertexAdj.get(last)) {
                    Vertex next = edge.getEndVertex();
                    if (!path.contains(next)) { // Avoid cycles
                        List<Vertex> newPath = new ArrayList<>(path);
                        newPath.add(next);
                        queue.add(newPath);
                    }
                }
            }
        }

        return allPaths;
    }
}

Класс вершины:

public class Vertex {
    // The origin names are not id1 and id2.
    // I change them for simplicity.
    private String id1;
    private String id2;

    public Vertex() {
    }

    public Vertex(String id1, String id2) {
        this.id1 = id1;
        this.id2 = id2;
    }

    // Getters and Setters

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }

        Vertex other = (Vertex) obj;

        return id1.equals(other.id1) && id2.equals(other.id2);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id1, id2);
    }
}

Класс края:

public class Edge {
    private Vertex startVertex;
    private Vertex endVertex;

    public Edge(Vertex startVertex, Vertex endVertex) {
        this.startVertex = startVertex;
        this.endVertex = endVertex;
    }

    // Getters for startVertex and endVertex
    public Vertex getStartVertex() {
        return startVertex;
    }

    public Vertex getEndVertex() {
        return endVertex;
    }

    @Override
    public boolean equals(Object obj) {

        if (this == obj) {
            return true;
        }

        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }

        Edge other = (Edge) obj;

        return Objects.equals(startVertex, other.startVertex) &&
                Objects.equals(endVertex, other.endVertex);
    }

    @Override
    public int hashCode() {
        return Objects.hash(startVertex, endVertex);
    }
}

Вот пример. Объем данных в этом примере относительно невелик, поэтому разница во времени выполнения неочевидна. Когда график большой, разница очевидна. На моем графике BFS работает 2 мс, а DFS — 15 с при k = 1:

public static void main(String[] args) {
    AdjGraph graph = new AdjGraph();

    for (int i = 0; i < 1000; i++) {
        Vertex v = new Vertex(String.valueOf(i), String.valueOf(i));
        graph.addVertex(v);
    }

    List<Vertex> vertexList = graph.getVertexList();
    for (int i = 0; i < vertexList.size(); i++) {
        for (int j = 0; j < vertexList.size(); j++) {
            if (j != i) {
                graph.addEdge(new Edge(vertexList.get(i), vertexList.get(j)));
            }
        }
    }

    Vertex start = vertexList.get(0); // Start node
    int k = 1; // Maximum path length

    Long t1 = System.currentTimeMillis();
    Map<Integer, List<List<Vertex>>> allPaths = graph.findAllPathsUpToLengthByBFS(start, k);
//  Map<Integer, List<List<Vertex>>> allPaths = graph.findAllPathsUpToLengthByBFS(start, k);
    Long t2 = System.currentTimeMillis();
    System.out.println("Running time: " + (t2 - t1) + "ms");
}

Удивительно, но BFS намного быстрее, чем DFS. Кто-нибудь знает, почему? Может быть, это потому, что в DFS слишком много повторяющихся вычислений? Как я могу их оптимизировать?

Спасибо!