グラフアルゴリズムシリーズ: 計算グラフにおける最短経路

[[398324]]

この記事はWeChatの公開アカウント「Beta Learns JAVA」から転載したもので、著者はSilently9527です。この記事を転載する場合は、Beta Learning JAVA パブリックアカウントにお問い合わせください。

序文

前の 2 つの記事では、深さ優先探索を使用して、グラフ内の頂点 v から頂点 w までのパスを見つけることができました。ただし、深さ優先探索は頂点の入力に大きく関係しており、見つかったパスは必ずしも最短ではありません。通常、map 関数など、グラフ内の最短パスを見つける必要があることがよくあります。ここでは幅優先探索アルゴリズムを使用する必要があります

幅優先探索

以前に定義されたパス検索APIを引き続き使用します

パブリッククラスPaths{
    パス(グラフ グラフ、 int s); 
     
    boolean hasPathTo( int v); // s->v からのパスがあるかどうかを判定する
     
    Iterable< Integer > pathTo( int v); //パスが存在する場合はパスを返す
}

幅優先探索では、最短経路を見つけるために、再帰を使用してそれを達成するのではなく、開始点の順序ですべての頂点をトラバースする必要があります。アルゴリズムの考え方は次のとおりです。

マークされているが、隣接リストがまだ走査されていない頂点を格納するためにキューを使用します。
キューから次の頂点vを取り出してマークする
vに隣接するマークされていない頂点をすべてキューに追加します。

このアルゴリズムでは、パスを保存するために、エッジ配列 edgeTo[] を使用し、親リンクツリーを使用して、ルートノードから接続されているすべての頂点までの最短パスを表す必要があります。

パブリッククラスBreadthFirstPaths {
    プライベートブール値 marked[];
    プライベートint []エッジTo;
    プライベートint s;
    プライベート Queue< Integer > queue = new LinkedListQueue<>(); 
 
パブリックBreadthFirstPaths(グラフグラフ、 int s) {
        this.s = s;
        this.marked = 新しいブール値[graph.V()];
        this.edgeTo = 新しいint [graph.V()]; 
 
        bfs(グラフ, s);
    } 
 
    プライベートvoid bfs(グラフグラフ、 int s) {
        this.marked[s] = true ;
        this.queue.enqueue(s);
        while (!this.queue.isEmpty()) {
整数v = this.queue.dequeue();
 ( int w : graph.adj(v))の場合{
                if (!this.marked[w]) {
                    this.marked[w] = true ;
                    this.edgeTo[w] = v;
                    this.queue.enqueue(w);
                }
            }
        } 
 
 
    } 
 
パブリックブール値hasPathTo( int v) {
 this.marked[v]を返します。
    } 
 
パブリックイテラブル<整数> pathTo( int v) {
        （！hasPathTo（v））の場合{
            新しい IllegalStateException をスローします ( "s は v に到達できません" );
        }
        Stack<整数> stack = new LinkedListStack<>();
        スタックをプッシュします。
        (edgeTo[v] != s) の間 {
            スタックをプッシュします(edgeTo[v]);
            v = エッジ[v];
        }
        スタックをプッシュします。
スタックを返します。
    }
 }

次の図を列としてとらえ、幅優先探索の軌跡を見てみましょう。

ユニットテストコード:

 @テスト
パブリックボイドテスト（）{
    グラフ graph = new Graph(8);
    グラフにエッジを追加します。(0, 1);
    グラフにエッジを追加します(0, 2);
    グラフにエッジを追加します(0, 5);
    グラフにエッジを追加します。(1, 3);
    グラフにエッジを追加します。
    グラフにエッジを追加します(4, 3);
    グラフにエッジを追加します(5, 3);
    グラフにエッジを追加します(6, 7); 
 
    BreadthFirstPaths パス = new BreadthFirstPaths(graph, 0);
    システム.out.println (paths.hasPathTo(5));
    System.out.println (paths.hasPathTo(2)) ;
    システム.out.println (paths.hasPathTo(6)); 
 
    paths.pathTo(5).forEach(System.out:: print );
    System.out.println( ) ;
    paths.pathTo(4).forEach(System.out:: print );
    System.out.println( ) ;
    paths.pathTo(2).forEach(System.out:: print );
    System.out.println( ) ;
    paths.pathTo(3).forEach(System.out:: print ); 
 
 }

実行結果は、私たちが分析した走行軌跡と一致しています。

シンボル図

最近の記事で学んだグラフアルゴリズムはすべて、数値を頂点として使用しています。これは、数値を使用してこれらのアルゴリズムを実装するのが非常に簡単で便利だからです。ただし、実際のシナリオでは、地図上の場所や映画と俳優の関係など、数値ではなく文字が頂点として使用されることがよくあります。

実際のシナリオに対応するには、数字と文字列のマッピングを作成する必要があります。このとき、前回の記事で実装したマップ（マップはバイナリツリー、赤黒木、ハッシュテーブルなどを通じて実装されます。興味のある学生は調べることができます）を考え、Mapを使用して文字列と数字のマッピング関係を維持します。

パブリックインターフェースSymbolGraph {
    boolean contains (String key ); //頂点が存在するかどうかを判断します
 
整数  index (String key ); //名前で対応するデジタル頂点を返す
 
    String name ( int v); //デジタル頂点を通じて対応する文字名を返す
 
    グラフ graph();
 }

実装のアイデア:

マップを使用して文字列と数値のマッピングを保存します。キーは文字列、値は数値です。
配列を使用して、数値から文字列へのマッピングを逆にします。配列の添え字は数値の頂点に対応し、値は文字列名に対応します。
構築されたグラフの頂点と辺が、a、b、c、d\nb、a、h、l、p\ng、s、z などの文字列で表されるとします。\n で区切られた各セグメントの最初の文字列は頂点 v を表し、次の文字列は頂点 v に接続された隣接頂点を表します。

実際のプロセスは、特定の状況に応じて決定されます。必ずしもこの種類の文字列である必要はありません。データベースまたはネットワーク要求から取得できます。

コードは次のように実装されます。

パブリッククラスSymbolGraph {
    プライベート Map<String, Integer > map = new RedBlack23RedBlackTreeMap<>();
    プライベートString[]キー;
    プライベートグラフグラフ; 
 
パブリックシンボルグラフ(文字列テキスト) {
        Arrays.stream(text.split( "\n" )).forEach(行 -> {
            文字列[]を分割 = line.split( "," );
 ( int i = 0; i < split.length; i++) {
                map.put([i], i);
            }
        }); 
 
        this.keys = 新しい文字列[ map.size ()];
        map.keys().forEach(キー-> {
            this.keys[this.map.get( key )] =キー;
        }); 
 
        this.graph = 新しいグラフ(this.keys.length);
        Arrays.stream(text.split( "\n" )).forEach(行 -> {
            文字列[]を分割 = line.split( "," );
分割されたマップを0に分割します。
 ( int i = 1; i < split.length; i++) {
                this.graph.addEdge(v, this.map.get(split[i]));
            }
        }); 
         
    } 
 
パブリックブール値には(文字列キー)が含まれます。
 map.contains (キー)を返します。
    } 
 
公共 整数 インデックス(文字列キー) {
 map.get(キー)を返します。
    } 
 
パブリック文字列名( int  索引） {
 this.keys[インデックス]を返します。
    } 
 
パブリックグラフグラフ() {
 this.graphを返します。
    } 
 
公共 静的void main(String[] args) {
        システム.out .println(Arrays.toString( "323\n2323" .split( "\n" )));
    }
 }