相邻节点迭代器
图论中最常见的操作就是遍历邻边,通过一个顶点遍历相关的邻边。邻接矩阵的遍历邻边的时间复杂度为 O(V),邻接表可以直接找到,效率更高。
邻接矩阵迭代:
...
public Iterable < Integer > adj ( int v ) {
assert v >= && v < n ;
Vector < Integer > adjV = new Vector < Integer > ( ) ;
for ( int i = ; i < n ; i ++ )
if ( g [ v ] [ i ] )
adjV. add ( i ) ;
return adjV ;
}
...
public Iterable < Integer > adj ( int v ) {
assert v >= && v < n ;
Vector < Integer > adjV = new Vector < Integer > ( ) ;
for ( int i = ; i < n ; i ++ )
if ( g [ v ] [ i ] )
adjV. add ( i ) ;
return adjV ;
}
...
邻接表迭代:
...
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制,返回一个Vector不会带来额外开销,
public Iterable < Integer > adj ( int v ) {
assert v >= && v < n ;
return g [ v ] ;
}
...
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制,返回一个Vector不会带来额外开销,
public Iterable < Integer > adj ( int v ) {
assert v >= && v < n ;
return g [ v ] ;
}
...
对于这两种图的表达方式我们可以抽象出一个接口,生成这一套算法的框架,而不用去考虑底层是邻接表还是邻接矩阵。
本小节写了一个测试用例 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/yssmx/graph/DenseGraphIterater.java 文件代码:
package
yssmx.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 >= ;
this . n = n ;
this . m = ;
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 >= && v < n ;
assert w >= && 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 >= && v < n ;
assert w >= && w < n ;
return g [ v ] [ w ] ;
}
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制,返回一个Vector不会带来额外开销,
public Iterable < Integer > adj ( int v ) {
assert v >= && v < n ;
Vector < Integer > adjV = new Vector < Integer > ( ) ;
for ( int i = ; 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 >= ;
this . n = n ;
this . m = ;
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 >= && v < n ;
assert w >= && 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 >= && v < n ;
assert w >= && w < n ;
return g [ v ] [ w ] ;
}
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制,返回一个Vector不会带来额外开销,
public Iterable < Integer > adj ( int v ) {
assert v >= && v < n ;
Vector < Integer > adjV = new Vector < Integer > ( ) ;
for ( int i = ; i < n ; i ++ )
if ( g [ v ] [ i ] )
adjV. add ( i ) ;
return adjV ;
}
}
(2)邻接表迭代
src/yssmx/graph/SparseGraphIterater.java 文件代码:
package
yssmx.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 >= ;
this . n = n ;
this . m = ; // 初始化没有任何边
this . directed = directed ;
// g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
g = ( Vector < Integer > [ ] ) new Vector [ n ] ;
for ( int i = ; 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 >= && v < n ;
assert w >= && 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 >= && v < n ;
assert w >= && w < n ;
for ( int i = ; 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 >= && 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 >= ;
this . n = n ;
this . m = ; // 初始化没有任何边
this . directed = directed ;
// g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
g = ( Vector < Integer > [ ] ) new Vector [ n ] ;
for ( int i = ; 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 >= && v < n ;
assert w >= && 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 >= && v < n ;
assert w >= && w < n ;
for ( int i = ; 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 >= && v < n ;
return g [ v ] ;
}
}