BFSとDFSを使用してグラフ内の2つのノード間のパスを見つける

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のようなものです：for (x = v; distTo[x] != 0; x = edgeTo[x])である理由この

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

私の疑問があるようpathTo方法があるhttp://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BreadthFirstPaths.java.html

BFSおよびDFS内のfor (int x = v; x != s; x = edgeTo[x]) BFSのpathToメソッドでdistTo[x] != 0の代わりにx != sを使用すると、何が問題になりますか？

Answer 1

あなたの所見は、条件x != sとdistTo[x] != 0は互換性があります。理由はdistTo[s]は0なので、source vertexに出会うとループが壊れます。したがって、source vertexに遭遇したときにループを解除するには、2つの条件のいずれかが機能します。