图的邻接表表示（Java完整实现）

图的邻接矩阵表示法虽然有很多优点，但对于稀疏图来说，用邻接矩阵表示会造成存储空间的浪费。

邻接表（Adjacency List）表示法实际上是一种链式存储结构。它克服了邻接矩阵的弊病，基本思想是只存储顶点相关联的信息，对于图中存在的边信息进行存储，不相邻接的顶点信息则不保留。

在邻接表中，对于图中的每个顶点建立一个带头结点的边链表，如第 i 个单链表中的结点则表示依附于顶点 vi 的边。每个边链表的头结点又构成一个表头结点表。因此，一个 n 个顶点的图的邻接表表示法由表头结点和边表结点两个部分构成。

表头结点和边表结点的存储结构如下图所示。


表头结点由两个域组成：数据域和指针域。其中，数据域用来存放顶点信息，指针域用来指向边表中的第一个结点。通常情况下，表头结点采用顺序存储结构实现，这样可以随机地访问任意顶点。

边表结点由 3 个域组成：邻接点域、数据域和指针域。其中，邻接点域表示与相应的表头顶点邻接点的位置，数据域存储与边或弧的信息，指针域用来指示下一个边或弧的结点。


上图所示的 G1 和 G2 用邻接表表示如下图所示。


对于下面的带权图：


用邻接表表示如下图所示：


图的邻接表存储结构描述如下：

class ArcNode // 边结点的类型定义
{
    int adjvex;       // 弧指向的顶点的位置
    ArcNode nextarc;  // 指示下一个与该顶点相邻接的顶点
    String info;      // 与弧相关的信息
    ArcNode(int adjvex)
    {
        this.adjvex = adjvex;
        this.nextarc = null;
    }
}

class VNode // 头结点的类型定义
{
    String data;      // 用于存储顶点
    ArcNode firstarc; // 指向第一个与该顶点邻接的顶点
    VNode(String data) {
        this.data = data; // 用于存储顶点
        this.firstarc = null; // 指向第一个与该顶点邻接的顶点
    }
}

class AdjGraph // 图的类型定义
{
    final int MAXSIZE = 20;
    VNode vertex[];   // 图的顶点数目、弧的数目
    int vexnum, arcnum;
    GKind kind;
    AdjGraph()
    {
        vertex = new VNode[MAXSIZE];
        vexnum = 0;
        arcnum = 0;
        kind = GKind.UG;
    }
}

若无向图 G 中有 n 个顶点和 e 条边，则图采用邻接表表示，需要 n 个头结点和 2e 个表结点。在 e 远小于 n(n-1)/2 时，采用邻接表表示显然要比采用邻接矩阵表示更节省空间。

在图的邻接表存储结构中，表头结点并没有存储顺序的要求。某个顶点的度正好等于该顶点对应链表的结点个数。在有向图的邻接表存储结构中，某个顶点的出度等于该顶点对应链表的结点个数。为了方便求某个顶点的入度，需要建立一个有向图的逆邻接表，也就是为每个顶点 vi 建立一个以 vi 为弧头的链表。图 2 中有向图 G1 的逆邻接表如下图所示。


【实例】编写算法，采用邻接表创建一个无向图 G。

class AdjGraph // 图的类型定义
{
    final int MAXSIZE = 20;
    VNode vertex[]; // 图的顶点数目、弧的数目
    int vexnum, arcnum; // 图的顶点数目、弧的数目
    GKind kind;
    AdjGraph()
    {
        vertex = new VNode[MAXSIZE];
        vexnum = 0;
        arcnum = 0;
        kind = GKind.UG;
    }
    public void CreateGraph() // 采用邻接表存储结构，创建无向图 G
    {
        System.out.println("请输入无向图 G 的顶点数,弧数(以空格分隔)：");
        Scanner sc = new Scanner(System.in);
        String str[] = sc.nextLine().split(" ");
        vexnum = Integer.parseInt(str[0]);
        arcnum = Integer.parseInt(str[1]);
        System.out.println("请输入" + vexnum + "个顶点的值：");
        String vname[] = sc.nextLine().split(" ");
        int k = 0;
        for (String v : vname) {
            VNode vtex = new VNode(v);
            vertex[k++] = vtex;
        }
        System.out.println("请输入弧尾和弧头(以空格分隔)：");
        for (k = 0; k < arcnum; k++) // 建立边链表
        {
            String v[] = sc.nextLine().split(" ");
            int i = LocateVertex(v[0]);
            int j = LocateVertex(v[1]);
            // 以 j 为入边、i 为出边创建邻接表
            ArcNode p = new ArcNode(j);
            p.nextarc = vertex[i].firstarc;
            vertex[i].firstarc = p;
            // 以 i 为入边、j 为出边创建邻接表
            p = new ArcNode(i);
            p.nextarc = vertex[j].firstarc;
            vertex[j].firstarc = p;
        }
        kind = GKind.UG;
    }
    public int LocateVertex(String v) // 在顶点向量中查找顶点 v, 若找到，则返回在向量中的序号, 否则返回-1
    {
        for (int i = 0; i < vexnum; i++) {
            if (vertex[i].data.equals(v))
                return i;
        }
        return -1;
    }
    public void DisplayGraph() // 图的邻接表存储结构的输出
    {
        System.out.print(vexnum + " 个顶点: ");
        for (int i = 0; i < vexnum; i++)
            System.out.print(vertex[i].data + " ");
        System.out.println("\n" + (arcnum * 2) + " 条边:");
        for (int i = 0; i < vexnum; i++) {
            ArcNode p = vertex[i].firstarc; // 将 p 指向边表的第一个结点
            while (p != null) // 输出无向图的所有边
            {
                System.out.print(vertex[i].data + "-" + vertex[p.adjvex].data + " ");
                p = p.nextarc;
            }
            System.out.println();
        }
    }
    public static void main(String args[])
    {
        System.out.println("创建一个无向图 G: ");
        AdjGraph N = new AdjGraph();
        N.CreateGraph();
        System.out.println("输出图的顶点和弧: ");
        N.DisplayGraph();
    }
}

程序的运行结果如下：

创建一个无向图G：
请输入无向图G的顶点数,弧数(以空格分隔)：
4 5
请输入4个顶点的值：
A B C D
请输入弧尾和弧头(以空格分隔)：
A B
A D
B C
B D
C D
输出图的顶点和弧：
4个顶点：
A B C D
10条边：
A→D A→B
B→D B→C B→A
C→D C→B
D→C D→B D→A