使用图结构表示的数据元素之间虽然具有“多对多”的关系，但是同样可以采用领接矩阵存储(即顺序存储)，也就是使用数组有效地存储图。
使用数组存储图时，需要使用两个数组，一个数组存放图中顶点本身的数据（一维数组），另外一个数组用于存储各顶点之间的关系（二维数组）。
不同类型的图，存储的方式略有不同，根据图有无权，可以将图划分为两大类：图和网 。
图，包括无向图和有向图；网，是指带权的图，包括无向网和有向网。
存储方式的不同，指的是：在使用二维数组存储图中顶点之间的关系时，如果顶点之间存在边或弧，在相应位置用 1 表示，反之用 0 表示；如果使用二维数组存储网中顶点之间的关系，顶点之间如果有边或者弧的存在，在数组的相应位置存储其权值；反之用 0 表示。
例如下图（B） 为无向图，各顶点没有权值，所以如果两顶点之间有关联，相应位置记为 1 ；反之记为 0 。构建的二维数组如图 2 所示。
图2 无向图对应的二维数组arcs
在此二维数组中，每一行代表一个顶点，依次从 V1 到 V5 ，每一列也是如此。比如 arcs[0] [1] = 1 ，表示 V1 和 V2 之间有边存在；而 arcs[0] [2] = 0，说明 V1 和 V3 之间没有边。
对于无向图来说，二维数组构建的二阶矩阵，实际上是对称矩阵，在存储时就可以采用压缩存储的方式存储下三角或者上三角。
通过二阶矩阵，可以直观地判断出各个顶点的度，为该行（或该列）非 0 值的和。例如，第一行有两个 1，说明 V1 有两个边，所以度为 2。
例如，下图中的有向图（A）时，对应的二维数组如图 3 所示：
图 3 有向图对应的二维数组arcs
例如，arcs[0] [1] = 1 ，证明从 V1 到 V2 有弧存在。且通过二阶矩阵，可以很轻松得知各顶点的出度和入度，出度为该行非 0 值的和，入度为该列非 0 值的和。
例如，V1 的出度为第一行两个 1 的和，为 2 ； V1 的入度为第一列中 1 的和，为 1 。所以 V1 的出度为 2 ，入度为 1 ，度为两者的和 3 。
如下，带权无向图中
其对应的二维数组表示为：
在此二维数组中，每一行代表一个顶点，依次从a 到 e ，每一列也是如此。当i=j时，值为0，所以不难发现该二维数组构建的矩阵为对称矩阵。
此中，arc[0] [1]=6 =arc[1] [0] ，值6表示a到b（同样b到a）的权值
如下，带权有向图
其对应的二维数组，类比带权无向图：
邻接表既适用于存储无向图，也适用于存储有向图。
先普及一个"邻接点"的概念。在图中，如果两个点相互连通，即通过其中一个顶点，可直接找到另一个顶点，则称它们互为邻接点。
邻接指的是图中顶点之间有边或者弧的存在。
邻接表存储图的实现方式:
给图中的各个顶点独自建立一个链表，用节点存储该顶点，用链表中其他节点存储各自的领接点。
与此同时，为了便于管理这些链表，通常会将所有链表的头节点存储到数组中（也可以用链表存储）。也正因为各个链表的头节点存储的是各个顶点，因此各链表在存储临界点数据时，仅需存储该邻接顶点位于数组中的位置下标即可。
例如，存储图 1a) 所示的有向图，其对应的邻接表如图 1b) 所示：
图 1 邻接表存储有向图
拿顶点 V1 来说，与其相关的邻接点分别为 V2 和 V3，因此存储 V1 的链表中存储的是 V2 和 V3 在数组中的位置下标 1 和 2。
从图 1 中可以看出，存储各顶点的节点结构分为两部分，数据域和指针域。数据域用于存储顶点数据信息，指针域用于链接下一个节点，如图 2 所示：
图 2 邻接表节点结构
在实际应用中，除了图 2 这种节点结构外，对于用链接表存储网（边或弧存在权）结构，还需要节点存储权的值，因此需使用图 3 中的节点结构：
图 3 邻接表存储网结构使用的节点
使用邻接表计算无向图中顶点的入度和出度会非常简单，只需从数组中找到该顶点然后统计此链表中节点的数量即可。
而使用邻接表存储有向图时，通常各个顶点的链表中存储的都是以该顶点为弧尾的邻接点，因此通过统计各顶点链表中的节点数量，只能计算出该顶点的出度，而无法计算该顶点的入度。
对于利用邻接表求某顶点的入度，有两种方式：
图 4 逆邻接表示意图
对于具有 n 个顶点和 e 条边的无向图，邻接表中需要存储 n 个头结点和 2e 个表结点。在图中边或者弧稀疏的时候，使用邻接表要比邻接矩阵更加节省空间。
与邻接表不同，十字链表法仅适用于储有向图和有向网。不仅如此，十字链表法还改善了邻接表计算图中顶点入度的问题。
图 1 十字链表中首元节点结构示意图
从图 1 可以看出，首元节点中有一个数据域和两个指针域（分别用 firstin 和 firstout 表示）：
由此可以看出，十字链表实质:
为每个顶点建立两个链表，分别存储以该顶点为弧头的所有顶点和以该顶点为弧尾的所有顶点。
注意，存储图的十字链表中，各链表中首元节点与其他节点的结构并不相同，图 1 所示仅是十字链表中首元节点的结构，链表中其他普通节点的结构如图 2 所示：
图 2 十字链表中普通节点的结构示意图
从图 2 中可以看出，十字链表中普通节点的存储分为 5 部分内容，它们各自的作用是：
比如说，用十字链表存储图 3a) 中的有向图，存储状态如图 3b) 所示：
图 3 十字链表存储有向图示意图
以图 3 中的顶点 V1 来说，通过构建好的十字链表得知，以该顶点为弧头的顶点只有存储在数组中第 3 位置的 V4（因此该顶点的入度为 1），而以该顶点为弧尾的顶点有两个，分别为存储数组第 1 位置的 V2 和第 2 位置的 V3（因此该顶点的出度为 2）。
对于图 3 各个链表中节点来说，由于表示的都是该顶点的出度或者入度，因此没有先后次序之分。
在实际使用时，如果想对图中某顶点进行实操（修改或删除），由于邻接表中存储该顶点的节点有两个，因此需要操作两个节点。为了提高在无向图中操作顶点的效率，我们就要学习一种新的适用于存储无向图的方法——邻接多重表。
注意：邻接多重表仅适用于存储无向图或无向网。
图 1 邻接多重表各首元节点的结构示意图
图 1 中各区域及其功能为：
从图 1 可以看到，邻接多重表采用与邻接表相同的首元节点结构。但各链表中其他节点的结构与十字链表中相同，如图 2 所示：
图 2 邻接多重表中其他节点结构
图 2 节点中各区域及功能如下：
综上所述，如果我们想使用邻接多重表存储图 3a) 中的无向图，则与之对应的邻接多重表如图 3b) 所示：
图 3 无向图及其对应的邻接多重表
从图 3 中，可直接找到与各顶点有直接关联的其他顶点。比如说，与顶点 V1 有关联的顶点为存储在数组下标 1 处的 V2 和数组下标 3 处的 V4，而与顶点 V2 有关联的顶点有 3 个，分别是 V1、V3 和 V5。
原文：https://www.cnblogs.com/wangzheming35/p/12724958.html