无向图，是指在图中的每条边都是无向的，无向图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领域），这样看来的话，我们可以借鉴一下先人们的解决思路，我们可以先将完整的图使用邻接链表存储，然后仅仅对点与点之间的联系使用临接矩阵进行存储，这样的话，我们就可以兼顾两者的优点，代价就是多一点空间存储邻接矩阵。到这里就结束了，整个文章就一句话总结：中庸之道。
网友评论