数学和计算机科学板块_辛酸网

数据结构与算法11

图

  图是最为一般化的数据结构，在图中的结点通常而言不止有一个前驱，也不只有一个后继。那什么是图呢？图就是一堆结点放在那，拿边连起来，这就是图的定义，就这么简单。所以前面说的什么线性表和树都是特殊的图。图中结点相连的东西就是边。边要是有方向，这图就是有向图，没方向的，就叫无向图；如果沿着边去走，能遍历所有的结点，也就是说所有的结点整体上都连起来了，那就是连通图；在不考虑方向的情况下，沿着边走能全都遍历完，这叫弱连通图；考虑方向了还能走完的，就是强连通图。所有的强连通图都是弱连通图，虽然这话很难听，但它是真的。 这话我好像在第1页说过

  图中结点所关联的边的数量叫做度，有向图中的边是带箭头的，所以从这个结点出来的边数叫出度，箭头指向这个结点的边数就是入度。沿着边上能走的方向走，走过的结点序列叫路径，走过的边数叫路径的长度，要是经过的结点不重复，那这便是简单路径。走一遭又回到起点的路径叫圈（也叫回路），结点不重复的圈叫简单回路（也叫简单环），在一个结点上直接指向自身的边叫自环。

图中的边也叫弧，有时边上会有一个属性值叫作权，相应的图就是带权图。

  有的图里，两个结点之间若有边相连，则只有一条边连着，但在某些图里两个结点之间相连的边可能不止一条。那么这些边就被称为多重边，相应的图被称为是多重图。

  把图中的一部分拿出来，这部分就是子图，剩下的是补图。子图内要是包含了所有结点那就叫生成子图。要是把一部分结点拿出来，顺便把这些结点内部相关联的边也拿出来，就是导出子图。

可达矩阵

  如何存储图中的内容呢？图中的最核心存在是结点而不是边，要知道，在图中删去一个结点，与之相关联的边也就没了，但是删去边，与之关联的结点还会存在。所以一般来说人们对图的存储也是以结点为核心的。图的矩阵存储就是将结点放在一个数组里，这个数组竖着写一遍，再横着写一遍，交叉而为矩阵，曰邻接矩阵。矩阵中的第i行j列元素表示第i个和第j个结点之间的边之情况。例如一个边不带权重的图，我们在矩阵元素里第i行j列元素为1表示第i个和第j个结点之间有边，0表示无边。这样那些结点相互之间能直接过去就一目了然。现在请看某有向图的邻接矩阵：

$\left[\begin{array}{cccc}1& 0& 1& 1\\ 0& 1& 0& 1\\ 1& 1& 1& 0\\ 1& 1& 0& 1\end{array}\right]$

  因为所有结点都可以到达自身，所以主对角线上全是1。那么问题来了，什么时候第i个结点能走两步到达第j个结点呢？如果存在结点结点k，使得，第一步第i个结点能去第k个结点，并且下一步从第k结点能一步到位前往第j结点，那我们就说第i结点可以走两步到达第j结点。那如果要找从第i到第j的长度为3的路径呢？那我们就得找结点k、m，使得i→k→m→j这三步都能一步到位。从第i结点的角度看，得找到这么一个第k结点，从第k结点角度看还得找这么一个第m结点……也就是说，要找从第i结点到第j结点的n步的路径，就得找出那么(n-1)个中间站。

  所以怎么找呢？只有0和1的邻接矩阵是看有没有一步到位的过去。显然如果矩阵中第i行里面，第k个数为1，那就说明以第i结点为起点第i结点可以一步到第k结点。当然，此处的第k结点只要找到那么一个就够啦。而如果矩阵中第j列的第k个数为1，那就说明以第j结点为终点，第k结点能一步到位。

$\left[\begin{array}{cccc}1& 0& 1& 1\\ 0& 1& 0& 1\\ 1& 1& 1& 0\\ -& ^& -& -\\ 1& 1& 0& 1\end{array}\right]\times \left[\begin{array}{ccccc}1& 0& 1& |& 1\\ 0& 1& 0& >& 1\\ 1& 1& 1& |& 0\\ 1& 1& 0& |& 1\end{array}\right]$

见上，矩阵中第2行第1列为1表示2号结点可一步到1号结点，而第1行第3列表示1号结点能一步前往3号结点。
这里形成路径2→1→3，所以2→3是两步可达的（在此编号自0始）

  看到了吗？怎么找到两步可达呢？答案是逻辑上的矩阵乘法：将只有0和1用于表示是否一步可达的邻接矩阵，进行平方即可。这里的抽象乘法是逻辑与，抽象加法是逻辑或，学过密码学的应该知道这就是有限域GF(2)上的抽象代数运算。

  推广一下，三个这样的邻接矩阵相乘就知道能不能三步过去，四个相乘就明白可否四部过去……只是一旦n步可达，那么给你(n+1)步的机会是肯定足够过去的。所以你可以反复进行矩阵乘法，最后你会发现乘法的结果矩阵会祛瘀稳定保持不变。这个最后的结果矩阵就是可达矩阵，它告诉我们从一个结点出发一直走能去什么地方。

图的矩阵和邻接表存储

  先前扯了半天可达矩阵，现在讨论范围扯回来，看看如何用矩阵存储矩阵。

  刚才说了对于无权有向图可以有邻接矩阵表示，那么无向无权图呢？其实也一样。但无向图下a要是能去b，b也一定能去a，所以无向图的邻接矩阵一定是对称矩阵。无权图的邻接矩阵，1表示有边，0是没边，而在有权图中则更为具体，矩阵中元素可以直接记载这条边的权重。如果在一个表示图中不同结点表示了不同地点，而边的权重用于表示公路或铁路等物理上的距离，那么一旦两地实际上不是直接相通，我们可以在对应矩阵中设这条边的权重为正无穷（千万不能设为负数，要不然后面的算法几乎都废了）。正无穷，无限远嘛，到不了的嘛。

  邻接表同样是经典的图之存储方式。它是先将结点放在一个数组里，结点内设有一个指针域，这个指针域里指向一条链表，链表内每一元素表示与图中该结点相关联的一条边，链表元素内有一个data记载了这条边关联的另一个结点之数组内下标。链表元素的next指向下一条与当前结点关联的边，要是没边了就是NULL。某有向图的邻接表见下

下标	图中结点	边的记载
0	a	1→2→4→NULL
1	b	2→4→NULL
2	c	3→NULL
3	d	0→1→2→NULL
4	e	0→3→NULL
...	...	...

  从邻接表中我们获悉，自a出发可一步至bce三者，而c只能一步到d。因为一个结点通向自身属于废话，链表就不予记载。这还是以起点的角度画的邻接表，链表内都写上了终点的下标。也有人做出来以终点之视角的邻接表，那样的话链表内就会写上起点的下标了。这还是有向图，如果是无向图的画，一个结点中边上既是起点又是终点，你就会发觉在邻接表内这条边中两个链表里一共出现两次。

辛酸网 ©版权所有