第二节 图的存储方式

链表

  我们在第三章对数据结构的简单了解中学习了,图和树可以使用链表来进行存储。参考第六节 数据结构基础(2)树、二叉树和图。虽然链表能够很方便地,在逻辑上对图进行定义和运算,但是我们知道,在比赛中我们的时间是有限的。如果花大量的时间去构建一个模型,然后针对这个模型的各种运算进行编写会耗费大量的时间。这个时候,我们就需要一个简单的数学模型,来处理这些数据。

图的矩阵表示

  在数学上,我们经常用矩阵来表示一个图。我们知道,图是由它们的顶点和他们之间的邻接关系来唯一确定的。这个时候我们只需要两个矩阵,一个用来存放他们的定点,另一个来存放他们之间的关系。

  举个例子:在上一节中,我们接触到了一个非常经典的七桥问题的图。

  图中的三个点我们分别命名为:

A
B    D
C

  这时,我们可以用一个矩阵V来表示这个图中的点。V={A,B,C,D}那怎么来表示他们之间的联系呢?我们用另一个矩阵M,如果两个点之间是相连的,我们就让m^ij=m^ji=1。如果它们之间没有联系,则m^ij=m^ji=inf。那么,
M=

A B C D
A 0 1 inf 1
B 1 0 1 1
C inf 1 0 1
D 1 1 1 0

  如果这是个有向图,我们可以根据行和列来确定出发和到达的定点;如果这是个对路径长度有要求的图,就比如在计算最短路径的时候,我们可以将矩阵中的数据改为两个点之间的距离。

  在编程的时候,我们可以使用数组来存放这样的矩阵。既方便计算,也能够精确表示。在今后的学习中,我们大多数时候都会使用这种方法来表示和运算。