Java数据结构之图：概念、存储结构与代码实现

/**
 * 无向图的表示
 */
import java.util.Queue;
import java.util.ArrayDeque;

public class Graph {
    // 顶点数目
    private final int V;
    // 边的数目
    private int E;
    // 邻接表，使用ArrayDeque作为队列实现
    private Queue<Integer>[] adj;

    /**
     * 创建一个包含V个顶点但不包含边的图
     * @param V 顶点数量
     */
    public Graph(int V) {
        this.V = V;
        this.E = 0;
        // 创建泛型数组需进行强制转换
        this.adj = new Queue[V];
        // 初始化每个顶点对应的邻接队列
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new ArrayDeque<>();
        }
    }

    /**
     * 向图中添加一条边 v-w
     * 无向图需在v和w之间双向添加
     * @param v 顶点v
     * @param w 顶点w
     */
    public void addEdge(int v, int w) {
        // 把w添加到v的链表中
        adj[v].add(w);
        // 把v添加到w的链表中
        adj[w].add(v);
        // 边的总数加1
        E++;
    }

    /**
     * 获取图中顶点的数量
     * @return 顶点数
     */
    public int V() {
        return V;
    }

    /**
     * 获取图中边的数量
     * @return 边数
     */
    public int E() {
        return E;
    }

    /**
     * 返回与顶点v相邻的所有顶点
     * @param v 目标顶点
     * @return 邻接点队列
     */
    public Queue<Integer> adj(int v) {
        return adj[v];
    }
}