圖的表示有兩種：

鄰接矩陣（Adjacency Matrix）和鄰接表（Adjacency Lists）

1、鄰接表適合表示稀疏圖（Sparse Graph）
稀疏圖，頂點(diǎn)的個(gè)數(shù)大于邊的個(gè)數(shù)晤郑，鄰接表更節(jié)約空間

鄰接表無向圖的表達(dá)方式如下：

image.png

鄰接表的有向圖的表達(dá)方式如下：

image.png

2渴语、鄰接矩陣適合表示稠密圖（Dense Graph）
稠密圖 和完全圖

鄰接矩陣可以表示有向圖和無向圖
無向圖

image.png

有向圖

image.png

鄰接矩陣完整代碼如下：

// 稠密圖 - 鄰接矩陣
public class DenseGraph {

    private int nodeCount;  // 節(jié)點(diǎn)數(shù)
    private int edgeCount;  // 邊數(shù)
    private boolean directed;   // 是否為有向圖
    private boolean[][] matrix;      // 圖的具體數(shù)據(jù)

    public DenseGraph(int nodeCount, boolean directed) {
        this.nodeCount = nodeCount;
        this.edgeCount = 0;
        this.directed = directed;
        // g初始化為n*n的布爾矩陣, 每一個(gè)matrix[i][j]均為false, 表示沒有任和邊
        // false為boolean型變量的默認(rèn)值
        this.matrix = new boolean[nodeCount][nodeCount];
    }

    //返回節(jié)點(diǎn)個(gè)數(shù)
    public int getNodeCount() {
        return nodeCount;
    }

    //返回邊的個(gè)數(shù)
    public int getEdgeCount() {
        return edgeCount;
    }


    public void addEdge(int v, int w) {
        if (v < 0 || v > nodeCount || w < 0 || w > nodeCount) {
            throw new IllegalArgumentException("參數(shù)不合法皮官！");
        }

        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("參數(shù)不合法！");
        }

        return matrix[v][w];
    }

}

鄰接表完整代碼如下：

// 稀疏圖 - 鄰接表
public class SparseGraph {

    private int nodeCount;  // 節(jié)點(diǎn)數(shù)
    private int edgeCount;  // 邊數(shù)
    private boolean direct; // 是否為有向圖
    private Vector<Integer>[] graphList; // 圖的具體數(shù)據(jù)


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

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


    //返回節(jié)點(diǎn)個(gè)數(shù)
    public int getNodeCount() {
        return this.nodeCount;
    }

    //返回邊數(shù)
    public int getEdgeCount() {
        return this.edgeCount;
    }

    //向圖中添加一個(gè)邊
    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);

    }

    //驗(yàn)證圖中是否有從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;
    }
}