隣接ノードイテレータ

グラフ理論で最も一般的な操作は隣接エッジを走査することです。1つの頂点を通じて関連する隣接エッジを走査します。隣接行列の隣接エッジ走査の時間計算量は O(V) ですが、隣接リストでは直接見つけることができ、効率が高いです。

隣接行列の反復:

...
public Iterable<Integer> adj(int v) {
    assert v >= 0 && v < n;
    Vector<Integer> adjV = new Vector<Integer>();
    for(int i = 0 ; i < n ; i ++ )
        if( g[v][i] )
            adjV.add(i);
    return adjV;
}
...

隣接リストの反復:

...
// グラフ内の頂点のすべての隣接エッジを返す
// Javaは参照メカニズムを使用するため、Vectorを返しても追加のオーバーヘッドは発生しません。
public Iterable<Integer> adj(int v) {
    assert v >= 0 && v < n;
    return g[v];
}
...

これら2つのグラフ表現に対して、インターフェースを抽象化してこのアルゴリズムの枠組みを生成できます。底层が隣接リストか隣接行列かを考慮する必要はありません。

この節ではテストケース GraphReadTest を作成し、抽象インターフェースを呼び出してグラフの表示を実現します。read パッケージで確認できます。

/**
* グラフの抽象インターフェース
 */

public interface Graph {
    public int V();
    public int E();
    public void addEdge( int v , int w );
    boolean hasEdge( int v , int w );
    void show();
    public Iterable<Integer> adj(int v);
}

Java サンプルコード

ソースパッケージのダウンロード:Download

(1)隣接行列の反復

src/サンプル/graph/DenseGraphIterater.java ファイルコード:

package サンプル.graph;

import java.util.Vector;

/**
* 隣接行列の反復
 */

public class DenseGraphIterater {
    // ノード数
    private int n;
    // エッジ数
    private int m;
    // 有向グラフかどうか
    private boolean directed;
    // グラフの具体的なデータ
    private boolean[][] g;

    // コンストラクタ
    public DenseGraphIterater( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;
        this.directed = directed;
        // gはn*nのブール行列に初期化され、各g[i][j]はfalseで、辺が存在しないことを示します
        // falseはboolean型変数のデフォルト値です
        g = new boolean[n][n];
    }
    // ノード数を返す
    public int V(){ return n;}
    // エッジ数を返す
    public int E(){ return m;}

    // グラフにエッジを追加する
    public void addEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        if( hasEdge( v , w ) )
            return;
        g[v][w] = true;
        if( !directed )
            g[w][v] = true;
        m ++;
    }

    // グラフにvからwへのエッジがあるかどうかを検証する
    boolean hasEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        return g[v][w];
    }
    // グラフ内の頂点のすべての隣接エッジを返す
    // Javaは参照メカニズムを使用するため、Vectorを返しても追加のオーバーヘッドは発生しません。
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        Vector<Integer> adjV = new Vector<Integer>();
        for(int i = 0 ; i < n ; i ++ )
            if( g[v][i] )
                adjV.add(i);
        return adjV;
    }
}

(2)隣接リストの反復

src/サンプル/graph/SparseGraphIterater.java ファイルコード:

package サンプル.graph;

import java.util.Vector;

/**
* 隣接リストの反復
 */

public class SparseGraphIterater {

    private int n;  // ノード数
    private int m;  // エッジ数
    private boolean directed;    // 有向グラフかどうか
    private Vector<Integer>[] g; // グラフの具体的なデータ

    // コンストラクタ
    public SparseGraphIterater( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;    // エッジなしで初期化
        this.directed = directed;
        // gはn個の空のvectorに初期化され、各g[i]が空であることを示し、つまりエッジが存在しないことを意味します
        g = (Vector<Integer>[])new Vector[n];
        for(int i = 0 ; i < n ; i ++)
            g[i] = new Vector<Integer>();
    }
    public int V(){ return n;} // ノード数を返す
    public int E(){ return m;} // エッジ数を返す

    // グラフにエッジを追加する
    public void addEdge( int v, int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        g[v].add(w);
        if( v != w && !directed )
            g[w].add(v);

        m ++;
    }

    // グラフにvからwへのエッジがあるかどうかを検証する
    boolean hasEdge( int v , int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v].elementAt(i) == w )
                return true;
        return false;
    }

    // グラフ内の頂点のすべての隣接エッジを返す
    // Javaは参照メカニズムを使用するため、Vectorを返しても追加のオーバーヘッドは発生しません。
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        return g[v];
    }
}
その他の拡張