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

[Anonymous]

Я пытаюсь использовать DFS и BFS, чтобы найти все простые пути длиной до заданного k, начинающиеся с заданной вершины ориентированного графа. Никакие циклы не допускаются.
Мой код выглядит следующим образом, и я проверил, что оба алгоритма дают правильные результаты.
Я определяю график class и поместите в этот класс код 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 vertexList;
private Map 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 edgeList = this.vertexAdj.get(startVertex);

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

public List getVertexList() {
return vertexList;
}

// Version of DFS
public Map findAllPathsUpToLengthByDFS(Vertex start, int k) {
boolean[] visited = new boolean[vertexList.size()];
List path = new ArrayList();
Map 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 path, Map 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  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 findAllPathsUpToLengthByBFS(Vertex start, int k) {
Map allPaths = new HashMap();
Queue queue = new LinkedList();

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

while (!queue.isEmpty()) {
List 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  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  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);
}
}

Класс Edge:

Код: Выделить всё

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 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 allPaths = graph.findAllPathsUpToLengthByBFS(start, k);
//  Map allPaths = graph.findAllPathsUpToLengthByBFS(start, k);
Long t2 = System.currentTimeMillis();
System.out.println("Running time: " + (t2 - t1) + "ms");
}

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

Подробнее здесь: https://stackoverflow.com/questions/786 ... th-of-them