首页 > 编程笔记 > Java笔记 阅读：14

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

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

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

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

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


图 1 表头结点和边表结点的存储结构

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

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


图 2 有向图G1与无向图G2

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


图 3 图的邻接表表示

对于下面的带权图：


图 4 带权图的邻接矩阵表示

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


图 5 图的邻接表表示

图的邻接表存储结构描述如下： 
  1. class ArcNode // 边结点的类型定义
  2. {
  3.     int adjvex;       // 弧指向的顶点的位置
  4.     ArcNode nextarc;  // 指示下一个与该顶点相邻接的顶点
  5.     String info;      // 与弧相关的信息
  6.     ArcNode(int adjvex)
  7.     {
  8.         this.adjvex = adjvex;
  9.         this.nextarc = null;
  10.     }
  11. }
  12.  
  13. class VNode // 头结点的类型定义
  14. {
  15.     String data;      // 用于存储顶点
  16.     ArcNode firstarc; // 指向第一个与该顶点邻接的顶点
  17.     VNode(String data) {
  18.         this.data = data; // 用于存储顶点
  19.         this.firstarc = null; // 指向第一个与该顶点邻接的顶点
  20.     }
  21. }
  22.  
  23. class AdjGraph // 图的类型定义
  24. {
  25.     final int MAXSIZE = 20;
  26.     VNode vertex[];   // 图的顶点数目、弧的数目
  27.     int vexnum, arcnum;
  28.     GKind kind;
  29.     AdjGraph()
  30.     {
  31.         vertex = new VNode[MAXSIZE];
  32.         vexnum = 0;
  33.         arcnum = 0;
  34.         kind = GKind.UG;
  35.     }
  36. }
若无向图 G 中有 n 个顶点和 e 条边，则图采用邻接表表示，需要 n 个头结点和 2e 个表结点。在 e 远小于 n(n-1)/2 时，采用邻接表表示显然要比采用邻接矩阵表示更节省空间。

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


图 6 有向图G1的逆邻接表

【实例】编写算法，采用邻接表创建一个无向图 G。 
  1. class AdjGraph // 图的类型定义
  2. {
  3.     final int MAXSIZE = 20;
  4.     VNode vertex[]; // 图的顶点数目、弧的数目
  5.     int vexnum, arcnum; // 图的顶点数目、弧的数目
  6.     GKind kind;
  7.     AdjGraph()
  8.     {
  9.         vertex = new VNode[MAXSIZE];
  10.         vexnum = 0;
  11.         arcnum = 0;
  12.         kind = GKind.UG;
  13.     }
  14.     public void CreateGraph() // 采用邻接表存储结构，创建无向图 G
  15.     {
  16.         System.out.println("请输入无向图 G 的顶点数,弧数(以空格分隔)：");
  17.         Scanner sc = new Scanner(System.in);
  18.         String str[] = sc.nextLine().split(" ");
  19.         vexnum = Integer.parseInt(str[0]);
  20.         arcnum = Integer.parseInt(str[1]);
  21.         System.out.println("请输入" + vexnum + "个顶点的值：");
  22.         String vname[] = sc.nextLine().split(" ");
  23.         int k = 0;
  24.         for (String v : vname) {
  25.             VNode vtex = new VNode(v);
  26.             vertex[k++] = vtex;
  27.         }
  28.         System.out.println("请输入弧尾和弧头(以空格分隔)：");
  29.         for (k = 0; k < arcnum; k++) // 建立边链表
  30.         {
  31.             String v[] = sc.nextLine().split(" ");
  32.             int i = LocateVertex(v[0]);
  33.             int j = LocateVertex(v[1]);
  34.             // 以 j 为入边、i 为出边创建邻接表
  35.             ArcNode p = new ArcNode(j);
  36.             p.nextarc = vertex[i].firstarc;
  37.             vertex[i].firstarc = p;
  38.             // 以 i 为入边、j 为出边创建邻接表
  39.             p = new ArcNode(i);
  40.             p.nextarc = vertex[j].firstarc;
  41.             vertex[j].firstarc = p;
  42.         }
  43.         kind = GKind.UG;
  44.     }
  45.     public int LocateVertex(String v) // 在顶点向量中查找顶点 v, 若找到，则返回在向量中的序号, 否则返回-1
  46.     {
  47.         for (int i = 0; i < vexnum; i++) {
  48.             if (vertex[i].data.equals(v))
  49.                 return i;
  50.         }
  51.         return -1;
  52.     }
  53.     public void DisplayGraph() // 图的邻接表存储结构的输出
  54.     {
  55.         System.out.print(vexnum + " 个顶点: ");
  56.         for (int i = 0; i < vexnum; i++)
  57.             System.out.print(vertex[i].data + " ");
  58.         System.out.println("\n" + (arcnum * 2) + " 条边:");
  59.         for (int i = 0; i < vexnum; i++) {
  60.             ArcNode p = vertex[i].firstarc; // 将 p 指向边表的第一个结点
  61.             while (p != null) // 输出无向图的所有边
  62.             {
  63.                 System.out.print(vertex[i].data + "-" + vertex[p.adjvex].data + " ");
  64.                 p = p.nextarc;
  65.             }
  66.             System.out.println();
  67.         }
  68.     }
  69.     public static void main(String args[])
  70.     {
  71.         System.out.println("创建一个无向图 G: ");
  72.         AdjGraph N = new AdjGraph();
  73.         N.CreateGraph();
  74.         System.out.println("输出图的顶点和弧: ");
  75.         N.DisplayGraph();
  76.     }
  77. }
程序的运行结果如下： 
创建一个无向图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

相关文章