图的表示

图的表示(图的存储)：

• 邻接矩阵(Adjacency Matrix)
• 邻接表(Adjacency Lists)

邻接矩阵

邻接矩阵适合表示稠密图 (Dense Graph)

稠密图：边比较多的图

稠密图--邻接矩阵的实现

public class DenseGraph {

    private int n; //节点数
    private int m; // 边数
    private boolean directed; // 是否为有向图
    private boolean[][] g;  // 图的具体数据

    // 构造函数
    public DenseGraph(int n, boolean direction) {
        assert n >= 0;
        this.n = n;
        this.m = 0;
        this.directed = direction;
        // g初始化为n*n的不二矩阵，每一个g[i][j]均为false，表示没有任何边
        // 默认为false
        g = new boolean[n][n];
    }

    // 返回节点个数
    public int V() {
        return this.n;
    }
    // 返回边的个数
    public int E() {
        return this.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];
    }
}

邻接表

邻接表适合表示稀疏图 (Sparse Graph)

稀疏图：边比较少的图

稀疏图--邻接表的实现

public class SparseGraph {
    private int n;  // 节点数
    private int m;  // 边数
    private boolean directed;  //是否为有向图
    private Vector<Integer>[] g; // 图的具体数据
    // 构造函数
    public SparseGraph(int n, boolean directed) {
        assert n >= 0;
        this.n = n;
        this.m = 0;    // 初始化没有任何边
        this.directed = directed;
        // g初始化为n个空的vector，表示每一个g[i]都为空，即没有任何边
        g = 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;
    }
}