使用BFS和DFS查找圖表中兩個節點之間的路徑

Question

我正在關注以下鏈接。

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

其中pathTo方法是這樣的

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

其中pathTo方法是這樣的

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; 
} 

我的疑問是，爲什麼for (x = v; distTo[x] != 0; x = edgeTo[x])是用於BFS和DFS中的for (int x = v; x != s; x = edgeTo[x])。如果我在BFS的pathTo方法中使用x != s而不是distTo[x] != 0，會出現什麼問題？

Answer 1

你的觀察是正確的，條件x != s和distTo[x] != 0是可以互換的。原因是distTo[s]是0，所以當我們遇到source vertex時循環中斷。因此，當我們遇到source vertex時打破循環，這兩個條件中的任何一個都會起作用。