隣接ノードイテレータ
グラフ理論で最も一般的な操作は隣接エッジを走査することです。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;
}
...
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];
}
...
// グラフ内の頂点のすべての隣接エッジを返す
// 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);
}
* グラフの抽象インターフェース
*/
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;
}
}
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];
}
}
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];
}
}