存储无向图的邻接矩阵和邻接链表

无向图，是指在图中的每条边都是无向的，无向图G=<V,E>，其中V是非空集合，称为顶点集，E是V中元素构成的无序二元组的集合，成为边集。

图1

如图所示，这是一张无向图

如果我们需要存储这份图，通过邻接矩阵，我们将上图表示为 ：

      A          B         C        D          E         F        G

A    0          0         1         0          1         0        0

B    0          0         0         0          0         1        0 

C    1          0         0         0          1         0        0

D   0          0         0         0          0         0        1

E    1          0         1         0          0         0        0

F    0          1         0         0          0         0        1

G   0          1         0         1          0         1        0    

从这张表中，我们可以发现，无向图的邻接矩阵是根据正对角线对称的，这种情况是因为无向图不区分方向。

有了这样一个邻接矩阵后。我们就可通过矩阵，可以得到那两个顶点之间存在一条边，甚至可以通过邻接矩阵去验证一张图是否为邻接矩阵。

但是，邻接矩阵只能对简单的图进行表示，即图的边和点没有什么特殊含义，那么，如果又这样一张图：

图2

在图中，我们可以知道这是一张无向加权图，现在如果我们需要表示这样一张图，该采用什么样的数据结构呢？

或许你可以说，我还是用邻接矩阵来存储数据，存储方式如下：

       a          b         c         d          e         f        

a    0          20         1       0        10         9       

b    20         0         5         6         0         11        

c    0           5         0         6          0         0        

d   0           6         6         0          18         14        

e    10         0        0         18         0         10        

f    9           11         0         14          10         0        

这样的话，邻接矩阵存储的值就有了多重含义，不仅仅表示两个顶点之间存在关系，还知道了存在什么样的关系，但是，情况是会不断复杂的，当我们每条边的含义不仅仅只有权重，还有了最大流通量，最小流通量等属性时，而且当我们的顶点也具有了相应的属性时（如权重），邻接矩阵就不在适用于这样的情况下了，那么，这个时候我们需要用什么样的数据结构来应对，能让它能面对复杂的情况呢？

这个时候，我们就可以考虑邻接链表了：

图3

这是一张用于表示无向图的邻接链表，图中先将所有的顶点一次标了序号0,1,2,3，接着再链接到的节点中用标号来表示下一个节点是哪个节点，因为是无向图，所以存在重复的部分，当这个无向图的顶点需要增加新的属性时，我们只需要对节点添加一个属性即可，这样看来的话，可扩展性显然是比临街矩阵要好的，有些人可能会有这样一个疑惑，这邻接链表还是不能解决边属性增加的问题啊？针对这个问题，我们来看看下面这张图:

图4

这张图中，邻接链表中的节点多了一个属性专门用来存储边值，这样看来的话，无论是点对象的属性增加还是变得属性增加，我们都可以通过邻接链表来实现了。

但是，真正使用过相关数据结构的朋友就会发现一个问题，当在处理问题时，可能我们经常需要获取一条边来进行操作，但是在只有一个顶点的情况下，针对邻接链表获取一条边是一件很痛苦的事情，每一次获取我们都需要遍历所有与该顶点相连的边，这样的话是很消耗时间和内存的，但是邻接矩阵虽然可以随机访问，但是他不能处理复杂的业务，那究竟该怎么办呢？

纵观计算机历史中，这样的问题我们遇到了很多，向计算机操作系统的页面置换算法，调度算法等，都是有连个互相在对立方面具有优势的情况（A精通A领域，但不熟悉B领域；B精通B领域，但不熟悉A领域），这样看来的话，我们可以借鉴一下先人们的解决思路，我们可以先将完整的图使用邻接链表存储，然后仅仅对点与点之间的联系使用临接矩阵进行存储，这样的话，我们就可以兼顾两者的优点，代价就是多一点空间存储邻接矩阵。到这里就结束了，整个文章就一句话总结：中庸之道。