Finden von Pfad zwischen zwei Knoten in einem Diagramm mit BFS und DFS

Question

Ich folge folgenden Links.

DFS: http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/DepthFirstPaths.java.html

wo pathto Methoden wie diese

public Iterable<Integer> pathTo(int v) { 
    validateVertex(v); 
    if (!hasPathTo(v)) return null; 
    Stack<Integer> path = new Stack<Integer>(); 
    for (int x = v; x != s; x = edgeTo[x]) 
     path.push(x); 
    path.push(s); 
    return path; 
} 

BFS: http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BreadthFirstPaths.java.html

wo pathto Verfahren wie dieses

public Iterable<Integer> pathTo(int v) { 
    validateVertex(v); 
    if (!hasPathTo(v)) return null; 
    Stack<Integer> path = new Stack<Integer>(); 
    int x; 
    for (x = v; distTo[x] != 0; x = edgeTo[x]) 
     path.push(x); 
    path.push(x); 
    return path; 
} 

Meine Zweifel

ist deshalb for (x = v; distTo[x] != 0; x = edgeTo[x]) ist in BFS und verwendet for (int x = v; x != s; x = edgeTo[x]) in DFS. Was wird schief gehen, wenn ich x != s anstelle von in BFS pathTo Methode verwende?

Answer 1

Sie haben Recht, dass die Bedingungen x != s und distTo[x] != 0 austauschbar sind. Der Grund ist distTo[s] ist 0, so Schleife bricht, wenn wir die source vertex begegnen. Um die Schleife zu unterbrechen, wenn wir auf source vertex treffen, wird eine der beiden Bedingungen funktionieren.