図論応用編

前回は編図の基本的な構造方法を書いて、図のこのような強大なデータ構造を運用して、また実際の応用の中の多くの問題を解決することができて、今日この編は主にいくつかのよくある応用を整理します
一、経路問題
経路問題は図の処理分野で非常に重要である.私たちが最もよく見られる迷路を歩くのは、典型的な道を探す問題です.ここでは主に深さ優先と広さ優先アルゴリズムの2つの方式を用いて経路探索を行い,この2つの探索アルゴリズムは多くのデータ構造において重要な運用があり,前に書いた二叉探索ツリーにおける層序遍歴で広さ優先アルゴリズムを用いたが,ここでは詳細に紹介する.
1.深さ優先探索経路
まずは深さ優先で、よりイメージアップするために、下図を直接見ます![][1]
ここでは頂点1を出発点とし,4を終点とする.一人が終点まで行くと仮定して、1から3つの経路があり、まず5への経路に沿って遍歴し、1->5->9->8の順で、それから道がないことに気づいたら、前の頂点に戻り、頂点5までここにもう1つの道があることに気づいたら、この道に沿って歩き続け、5->3->6、結局道がなくなったら、起点に戻り、別の道に沿って歩き続ける......1->2->4、見ると、これでゴールに直行して、いくつかの道を回ってやっとゴールを見つけて、その心は本当に興奮しています!本題に戻って、この具体的な実装を見て、booleanタイプの変数で頂点を遍歴したかどうかをマークし、intタイプの変数で始点から頂点までの既知のパス上の最後の頂点を表すことができます.図の基本構造については、私が前に書いた[図論基礎編][2]を参考にすることができます.

/**
 *            
 * @author Legend
 */
public class DepthFirstPaths {

    private boolean[] marked; //         dfs
    private int[] edgeTo; //                      
    private final int s; //   
    //      
    public DepthFirstPaths(Graph G,int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G,s);
    }
    //        
    private void dfs(Graph G,int v) {
        marked[v] = true;
        //      v    
        for (int w : G.adj(v)) {  
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G,w);  //          
            }
        }
    }
   //     s v   
    public boolean hasPathTo(int v) {
        return marked[v];
    }
   // s v   
    public Iterable PathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack path = new Stack<>();
        for (int i = v;i != s;i = edgeTo[i]) {
            path.push(i);
        }
        path.push(s);
        return path;
    }
}

各パスを正確に知るために、ここでは開始点から1つの頂点までの既知のパス上の最後の頂点を記録するためにedgeTo変数を作成し、edgeTo[w]=vはwからvまでのパスを表す.さらにPathToメソッドを見て,まずsからvへの経路があるかどうかを判断し,ないとnullに戻る.次に、Stackタイプのオブジェクトpathをインスタンス化し、順次遍歴し、パス上の各頂点をpushし、最後にpush頂点でpathを返します.
2.広さ優先探索経路
広さ優先はその名の通り,広さの遍歴を優先し,全過程が拡散した.ここはやはり上の図を使って、见やすいように、やはり写真をここに置いてください.[][3] [1]: http://img.mukewang.com/59fb24c20001780108340606.png [2]: http://blog.cspojie.cn/2017/10/20/%E5%9B%BE%E8%AE%BA-%E 5%9 F%BA%E 7%A 1%80%E 7%AF%87/#more、ここでは直接Graphで表し、具体的には以下のコードを見てみましょう[3]:http://img.mukewang.com/59fd753d0001780108340606.pngそれとも前のシナリオで、頂点1から1に隣接する頂点2,5,3を巡回し、頂点2から2に隣接する頂点を右に巡回し、頂点1を巡回したので、ここでは頂点7と頂点4を巡回し、そのまま終点に着くだけです.これは特殊な場合、先に別の頂点を巡回した場合、では、ほとんどの道を歩いてからゴールを見つけることができます.ここでは多くは言わないが、具体的な実装に重点を置いて、ここでは抽象的なデータ構造--キューで実現し、まずキューを作成し、それから起点マークをキューに挿入し、キューが空でなければ現在の頂点をキューからポップアップし、その後、この頂点に隣接する頂点を順次遍歴し、これらの頂点マークをキューに追加する.次に、次の頂点を同じ方法でキューからポップアップし、キューが空になるまで隣接する頂点を巡回します.では、具体的には次のコードを見てみましょう.

/**
 *
 *         
 * @author Legend
 **/

public class BreadthFirstPaths {

    private boolean[] marked;
    private int[] edgeTo;
    private final int s;
    public BreadthFirstPaths(Graph G,int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        try {
            bfs(G,s);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    private void bfs(Graph G,int s) throws InterruptedException {
        Queue queue = new Queue();
        marked[s] = true;
        queue.enqueue(s);
        while ( !queue.isEmpty() ) {
            int v = queue.dequeue(); //           
            for (int w : G.adj(v)) { //            
                if ( !marked[w] ) {
                    edgeTo[w] = v; //             
                    marked[w] = true; //             
                    queue.enqueue(w);
                }
            }
        }
    }
    public boolean hasPathTo(int v) {
        return marked[v];
    }
    public Iterable pathTo(int v) {
        if ( !hasPathTo(v) ) {
            return null;
        }
        Stack path = new Stack<>();
        for (int i = 0;i != s;i =edgeTo[i] ){
            path.push(i);
        }
        path.push(s);
        return path;
    }
}

ここでもpathTo法を用いているが,頂点と経路のマーキング過程と深さ優先探索経路は同じであり,ここでは多くは言わない.
れんけつぶんもんだい
1.紹介
連通成分も比較的よく見られる問題であり,主に任意の2つのノードの接続状態を判断するために用いられ,特にネットワーク接続と回路接続を検出するための問題では広く用いられている.
2.基本実現
何も言うことはありませんが、ここでは深さ優先の方法を使って、比較的簡単で、直接コードをつけます.

/**
 *                
 *
 * @author Legend
 * @create 2017-11-01 8:23
 **/

public class CC {
    private int count;
    private boolean marked[];
    private int[] id;

    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int s = 0;s < G.V();s++) {
            if (!marked[s]) {
                dfs(G,s);
                count++;
            }
        }
    }
    private void dfs(Graph G,int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G,w);
            }
        }
    }
    //            
    public boolean isConnected(int v,int w) {
        return id[v] == id[w];
    }
    // v          （0~count-1）
    public int id(int v) {
        return id[v];
    }
    //        
    public int count() {
        return count;
    }
}

にしょくもんだい
1.紹介
図のすべての頂点を2色でシェーディングして、任意のエッジの2つの端点の色が異なるようにすることができるかどうかは、現在の図が二分図であるかどうかに等しい.二叉木は実は特殊な図なので、この問題があります.
2.基本実現
具体的な実装は1つのboolタイプの変数で2色を表すことができ,直接構造方法の中で循環することができ,ここでも深さ優先の方式を用いる.まず、現在のノードが遍歴されているかどうかを判断し、遍歴されていないかどうかを判断します.すなわち、bool型変数でtrueとマークし、このノードに接続されたノードを遍歴し、このノードと隣接するノードを異なる色に塗ります.そして判断してまずコードを見てみましょう

/**
 *     
 *
 * @author Legend
 * @create 2017-11-01 9:17
 **/

public class TwoColor {
    private boolean[] marked; //          
    private boolean[] color; //       
    private boolean isTwoColorable = true; //     2     
    public TwoColor(Graph G) {
        marked = new boolean[G.V()];
        color = new boolean[G.V()];
        for (int s = 0;s < G.V();s++) {
            if (!marked[s]) {
                dfs(G,s);
            }
        }
    }
    private void dfs(Graph G,int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                color[w] = !color[v];
                dfs(G,w);
            } else if (color[w] == color[v]) {
                isTwoColorable = false;
            }
        }
    }
    public boolean isBipartite() {
        return isTwoColorable;
    }
}

この2つの頂点の色が同じであれば、いずれかの辺の2つの端点の色が異なるようにすることはできないが、この図は二分図ではないので、二分図であれば、いずれかの1つの端点の2つの端点の肯定的な色が異なると考えてみよう.巡回するたびに現在の頂点と接続頂点に2つの異なる色がマークされているため、この頂点に複数の隣接頂点があり、これらの隣接頂点にエッジが接続されている場合、2つの色が同じになるに違いない.このような図は自然に二分図ではない.
このブログは主に図論のいくつかの応用問題を整理しているので、これらの問題の最適化には重点ではなく、興味のある人は自分で資料を調べることができ、図論応用編は一時的にここに着いた.ps:このblogの先発lenged's blog