0

私は以下のリンクに従っています。BFSとDFSを使用してグラフ内の2つのノード間のパスを見つける

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を使用すると、何が問題になりますか?

答えて

0

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

+0

kありがとう!!!!!!!!! –