4

タイトルが少し乱雑であることは知っていますが、それをよりよく説明する方法がわかりません。

私がやろうとしていること：

テキストファイルで見つかったグラフを使用して、頂点Aから頂点Bまでの最短経路（頂点の最小量）を見つけて印刷します。

注：ダイクストラ法ではなく、幅優先探索を使用します。

私が持っているもの：

グラフにBFSを適用する実用的なアルゴリズムですが、実際に最短経路を印刷する良い方法はありません。

最短経路の頂点と、アルゴリズムを介して実行されるが最短経路ではない頂点を区別するのに苦労しています。

例：0と4の間の最短パスを見つけます。0は1,2と3に接続します。1は4に接続します。私のパスは[0,1、1ではなく[0,1,2,3,4]になります。 4]。

同じ質問をしているスレッドや、これを含むBFSのウォークスルーを見つけることができなかったので、これを実際よりもはるかに難しくしているのかどうかわかりません。

編集：興味があるかもしれない人のためのコード（私がサークルを避けているかどうかはまったくわかりませんか？）

編集2：スタックへのパスを保存する方法を変更しました。

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];

    q.add(v);
    Stack<Integer> path = new Stack<Integer>();
    while(q.peek() != null) {
        runBFS(q.poll(),w,visited,q,path);
    }
    return path.toString();
} 

private void runBFS(int v, int w, boolean[] visited, Queue<Integer> q, Stack<Integer> path) {
    if(visited[v]) {
    }
    else if(v == w) {
        path.add(v);
        q.clear();
    }
    else {
        path.add(v);
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
                q.add(vi.next());
        }
    }
}

変数とメソッドの説明：

v=原点

w=ターゲット頂点

g=グラフ

vi=vの近傍を反復処理する通常の反復子

読んでくれてありがとう！

4

4 に答える 4

10

頂点ごとに特定のパスフィールドが必要になります。そうすれば、選択したパスを追跡できるため、短いパスが見つかります。訪問した頂点を格納するためにブール配列を使用したのと同じように、文字列配列を使用します。

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];
    String[] pathTo = new String[g.numVertices()];

    q.add(v);
    pathTo[v] = v+" ";
    while(q.peek() != null) {
        if(runBFS(q.poll(),w,visited,q,pathTo))
        break;
    }
    return pathTo[w];
}

private boolean runBFS(int v, int w, boolean[] visited, Queue<Integer> q, String[] pathTo) {
    if(visited[v]) {
    }
    else if(v == w)
        return true; 
    }
    else {
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
            int nextVertex = vi.next();
            pathTo[nextVertex] = pathTo[v] + nextVertex + " ";
            q.add(nextVertex);
        }
    }
    return false;
}
于 2011-03-28T20:03:18.963 に答える
6

アシスタントが提案し、O（n ^ 2）ストレージスペースを使用しないもう1つのコンパクトな（スペース単位の）ソリューションは、各ノードに、元のノードのみを格納させることです。これは、visited-listを整数配列（int[] visited）に変更することで実行できます。

ステップ1：訪問済みリストを初期化して、すべての要素が'-1'「未訪問」になるようにします

ステップ2：最初のノードをそれ自体が訪問したものとしてマークしますvisited[v] = v;

BFSを実行します（次の変更を加えて、実行します）。

v-> v_nextから移動する場合：

if(visited[v_next] == -1)
{
  visited[v_next] = v;
  q.put(v_next);
}
// else skip it, it's already been visited

このように、wに到達できる場合、visited [w]は、そのノードからのノードを保存します。そのノードから、vまでさかのぼって、最後に逆の順序で印刷できます。（これは、スタックまたは再帰的な印刷方法のいずれかを使用して行われます。）

それが理にかなっていることを願っています。:)

于 2011-03-31T15:20:10.310 に答える
3

頂点をBFSキューに保存するときは、到達したパスのコピーも保存する必要があります。これにより、頂点がデキューされると利用できるようになります。現在のように、コードはキューに入れられた頂点にいかなる種類のパス情報も保持しません。アクセスしたノードのリストのみを保持します。

たとえば、並行して処理される別のキューを使用して、現在のパスを保存し、検索する次の頂点をデキューしたときに復元することができます。

于 2011-03-28T20:09:33.263 に答える
1

現在のノードをスタックにプッシュし、宛先に到達したらスタック全体を出力する必要があります。

于 2011-03-28T18:45:39.463 に答える