相邻节点迭代器

图论中最常见的操作就是遍历邻边，通过一个顶点遍历相关的邻边。邻接矩阵的遍历邻边的时间复杂度为 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 ;
}
...

邻接表迭代：

...
// 返回图中一个顶点的所有邻边
// 由于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 ) ;
}

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 ;
    }
}

（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 ] ;
    }
}