• 图的基本概念参阅：https://blog.csdn.net/qq_41453285/article/details/104151973
• 图的描述：
  • 无权图最常用的描述方法都是基于邻接的方式：邻接矩阵、邻接链表、邻接数组
  • 有权图也使用无权图的描述方法，只需要将无权图稍做修改就可以了（详细见下面介绍）
• 本文是概念讲述，编码实现参阅下一篇文章：https://blog.csdn.net/qq_41453285/article/details/104465857

一、无权图描述之邻接矩阵

邻接矩阵的定义

• 一个n顶点图G=(V,E)的邻接矩阵是一个n*n的矩阵（假设是A），其中每个元素都是0或1.假设V={1,2,3,...,n}
• 如果G是一个无向图，则元素的定义如下：

• 如果G是有向图，那么其中的元素定义如下：

• 根据上面的两个公式，可以得到下面的结论：

• 下面是一些无向图与有向图以及它们的邻接矩阵定义：

将邻接矩阵映射到数组

• 方法一：利用A(i,j)=1，当且仅当a[i][j]是true，1<=i<=n，1<=j<=n，因此n*n的邻接矩阵需要映射到一个(n+1)*(n+1)的布尔型数组中，此时需要字节
• 方法二：利用A(i,j)=1，当且仅当a[i-1]a[j-1]是true，1<=i<=n，1<=j<=n，因此n*n的邻接矩阵需要映射到一个n*n的布尔型数组中，此时需要字节，比方法一减少了2n+1字节
• 方法三：
  • 根据定义我们知道，所有对侥幸元素都是0而不需要存储，因此可以对角线元素去掉，进一步减少n字节的存储空间，压缩之后可以得到一个上（或下）三角矩阵
  • 缺陷：压缩之后虽然减少了存储空间，但是代价不小，因为定点的外部索引和在图中的内部描述不匹配。这样一来，不仅代码容易出错，而且访问边的时间也会增加。因此我们不建议这种做法
  • 例如把上面的三个邻接矩阵去掉对角线元素之后，如下图所示（阴影部分是原邻接矩阵的下三角部分）

• 方法四：
  • 无向图邻接矩阵是对称的，因此只需要存储上三角（或下三角）的元素，所以可以使用邻接矩阵来实现，此时所需空间仅为()/2字节，这对大型图来说是很有意义的
  • 邻接矩阵参阅：https://blog.csdn.net/qq_41453285/article/details/103258171

复杂度分析

• 使用邻接矩阵时，要确定邻接至或邻接于一个给定节点的集合需要用时Θ(n)。然而，增加或删除一条边仅需用时Θ(1)

二、无权图描述之邻接链表

• 一个顶点i的邻接表是一个线性表，它包含所有邻接于顶点i的顶点。在一个图的邻接表描述中，图的每一个顶点都有一个邻接表。当邻接表用链表表示时，就是邻接链表

邻接链表的描述

• 我们假设使用数组aList来描述所有的邻接表
• aList[i].firstNode指向顶点i的邻接表的第一个顶点
• 如果x指向链表aList[i]的一个顶点，那么(i,x->element)是图的一条边，其中element的数据类型是整型int
• 下图是一些无向图与有向图以及它们对应的邻接链表的描述：

复杂度分析

• 一个指针和一个整数各需要4字节的存储空间，因此用邻接链表描述一个n顶点的图需要8(n+1)字节存储n+1个firstNode指针和aList链表的listSize域，需要4*2*m字节存储m个链表节点，每个链表节点的两个域next和element各需要4字节，其中对于无向图m=2e，对于无向图m=3（其中e是边数）
• 当e远远小于时，邻接链表比邻接矩阵需要更少的空间。例如，一个e=n的有向图，用邻接链表描述需要16n+8字节，用压缩的邻接链表矩阵描述需要字节。因此，当e=n>=17时，邻接链表描述所需空间更少
• 在邻接链描述中，确定邻接于顶点i的顶点需要用时Θ(邻接于顶点i的顶点数)。插入或删除一条边(i,j)的用时，对无向图是，对无向图是

三、无权图描述之邻接数组

• 一个顶点i的邻接表是一个线性表，它包含所有邻接于顶点i的顶点。在一个图的邻接表描述中，图的每一个顶点都有一个邻接表。当邻接表用数组表示时，就是邻接数组

邻接数组的描述

• 方法一：用下图所示的邻接数组来表示，其中每一个索引处都是一个数组

• 方法二：使用二维数组来表示，假设是aList[][]，其中aList[i]容量等于顶点i的邻接表长度

复杂度分析

• 邻接数组比邻接链表少用4m字节，因为不需要next指针域（这样的指针域有m个）
• 而大部分的图操作，无论是邻接链表还是用邻接数组，其渐近时间复杂性是相同的。但是根据以往的实验，我们认为，对大部分的图操作，邻接数组的用时要少于邻接链表

• 注意：对邻接矩阵和邻接表所做的空间需求分析是渐近分析，而实际的实现所需空间可能要多一些，因为实际的代码可能要存储诸如顶点和边的个数，这些量在我们的分析中没有考虑

四、有权图的描述

• 将无权图的描述进行扩充就可以得到加权图的描述

邻接矩阵描述

• 用成本邻接矩阵C描述加权图，如果C(i,j)的权，那么它的使用方法和邻接矩阵的使用方法一样
• 在这种描述中，因为矩阵中的值代表的是权值，因此不能单单使用0来描述不存在的边，在实际编程中可以给不存在的边指定一个很大的值（这个很大的值可以用变量noEdge来命名）
• 下图是三个加权图以及邻接矩阵的描述：

邻接链表描述

• 因为有了权值，所以链表的元素有两个域vertex和weight，分别表示节点的编号与节点的权值
• 下图是对于一个无向加权图的描述

邻接数组描述

• 原理与邻接链表相似，只是元素使用数对(vertex,weight)表示。不再讲述