图论基础

图的表示有两种：

邻接矩阵（Adjacency Matrix）和邻接表（Adjacency Lists）

1、邻接表适合表示稀疏图（Sparse Graph）
稀疏图，顶点的个数大于边的个数，邻接表更节约空间

邻接表无向图的表达方式如下：

image.png

邻接表的有向图的表达方式如下：

image.png

2、邻接矩阵适合表示稠密图（Dense Graph）
稠密图 和完全图

邻接矩阵可以表示有向图和无向图
无向图

image.png

有向图

image.png

邻接矩阵完整代码如下：

// 稠密图 - 邻接矩阵
public class DenseGraph {

    private int nodeCount;  // 节点数
    private int edgeCount;  // 边数
    private boolean directed;   // 是否为有向图
    private boolean[][] matrix;      // 图的具体数据

    public DenseGraph(int nodeCount, boolean directed) {
        this.nodeCount = nodeCount;
        this.edgeCount = 0;
        this.directed = directed;
        // g初始化为n*n的布尔矩阵, 每一个matrix[i][j]均为false, 表示没有任和边
        // false为boolean型变量的默认值
        this.matrix = new boolean[nodeCount][nodeCount];
    }

    //返回节点个数
    public int getNodeCount() {
        return nodeCount;
    }

    //返回边的个数
    public int getEdgeCount() {
        return edgeCount;
    }


    public void addEdge(int v, int w) {
        if (v < 0 || v > nodeCount || w < 0 || w > nodeCount) {
            throw new IllegalArgumentException("参数不合法！");
        }

        if (hasEdge(v, w)) {
            return;
        }
        matrix[v][w] = true;
        edgeCount++;

        if (directed) {
            return;
        }

        matrix[w][v] = true;
    }


    public boolean hasEdge(int v, int w) {
        if (v < 0 || v > nodeCount || w < 0 || w > nodeCount) {
            throw new IllegalArgumentException("参数不合法！");
        }

        return matrix[v][w];
    }

}

邻接表完整代码如下：

// 稀疏图 - 邻接表
public class SparseGraph {

    private int nodeCount;  // 节点数
    private int edgeCount;  // 边数
    private boolean direct; // 是否为有向图
    private Vector<Integer>[] graphList; // 图的具体数据


    public SparseGraph(int nodeCount, boolean direct) {
        this.nodeCount = nodeCount;
        this.direct = direct;
        this.edgeCount = 0;

        // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
        this.graphList = new Vector[nodeCount];
        for (int i = 0; i < nodeCount; i++) {
            this.graphList[i] = new Vector<>();
        }
    }


    //返回节点个数
    public int getNodeCount() {
        return this.nodeCount;
    }

    //返回边数
    public int getEdgeCount() {
        return this.edgeCount;
    }

    //向图中添加一个边
    public void addEdge(int v, int w) {
        if (v < 0 || v > nodeCount || w < 0 || w > nodeCount) {
            throw new IllegalArgumentException("index is out of bound");
        }
        this.graphList[v].add(w);
        edgeCount++;

        if (direct || v == w) {
            return;
        }
        this.graphList[w].add(v);

    }

    //验证图中是否有从v到w的边
    public boolean hasEdge(int v, int w) {
        if (v < 0 || v > nodeCount || w < 0 || w > nodeCount) {
            throw new IllegalArgumentException("index is out of bound");
        }

        Vector<Integer> vector = this.graphList[v];
        for (int i = 0; i < vector.size(); i++) {
            if (vector.elementAt(v) == w) {
                return true;
            }
        }

        return false;
    }
}