数据结构教学中图论的基本概念及应用

数据结构教学中图论的基本概念及应用

张泽清

滇西应用技术大学

在本文中，我们讨论了计算机数据结构中与图论[1][2][3][4]有关的几个问题，其中主要包括并查集以及最小生成树。在解决这些问题之前，要先介绍一些关于图的基本术语和概念。此外，还本文还系统地介绍了如何将图结构作为抽象数据结构来实现，特别是介绍了两种常见的实现方式：邻接矩阵和邻接表。

1.概述

图结构被用来解决许多问题，是一种强大的方式。图（Graph）[5][6][7]被定义为G=（V，E）。也就是说，一个图是由一个顶点集V（Vertex）和一个边集E（Edge）组成。边集合E中的一个元素是顶点集V中的某一对顶点（u，v）。由于V和E都是有限集合，它们的模数表示为v=|V|和e=|E|，它们的模数通常用于分析算法的复杂性。

  根据边的集合E中的元素（u，v）是否有序，图被分为无向图和有向图。在无向图中，每条边都没有方向，边（u，v）只是表示存在一条连接在顶点u和顶点v之间的边。而在有向图中，每条边都有一个方向，边（u，v）表示存在一条从顶点u指向顶点v的有向边。

如果存在一条边e = (u, v)，那么顶点u和顶点v就被称为互为相邻（adjacent）；而顶点u和顶点v都与边e有关（incident）。在无向图中，与一个顶点相关的边的数量成为该点的度（degree）。对于一条边e=（u，v），e是u的出边（outgoing edge），e也是v的入边（incoming edge），与一个顶点相关的出线数被称为该点的出度，与一个顶点相关的入线数成为该点的入度。如果为图上的边添加代表某种实际意义的数值，那么称这些数值为边的权，称包含这样的带权边的图为带权图。

1.1邻接矩阵

邻接矩阵（adjacency matrix）是实现图结构的最直接的方法。它用一个二位矩阵来表示图的信息，二维矩阵中的每个单元格都表示一对顶点之间的相邻关系，因此被称为邻接矩阵。

对于非加权图，可以用matrix[u][v]的1或0来表示u和v之间是否存在边；对于加权图，可以用matrix[u][v]的1或0来表示u和v之间是否存在边。邻接矩阵的原理很容易理解，使用起来也很简单。在确定一对顶点之间是否存在关系时，只需要访问二维数组中的相关单元格，这样就不太费时。然而，相邻矩阵也有一些缺点。例如，如果需要遍历与某个顶点相邻的所有顶点，就需要一次性遍历二维数组中某一行的所有元素，并通过它们的值来确定它们是否相邻；也就是说，即使只有一个点与之相邻，也需要花费大量时间来遍历该行的所有数组单元，这对时间的利用效率较低。同时，当使用邻接矩阵来报告一个有n个顶点的图时，空间复杂度为O(n2)。如果所代表的图是一个稀疏的图，那么该矩阵将是一个稀疏的矩阵，大量的空间将被浪费掉。因此，只有当表示的图是一个密集图，并且需要经常确定某个顶点对是否相邻时，使用邻接矩阵才更合适。

1.2邻接表

邻接矩阵效率低下的主要原因是矩阵对应中大量单元的边不存在，这是由于最初分配空间的静态空间管理策略造成的。为了提高效率，可以使用动态分配的链表来代替静态空间分配。这就是邻接表（adjacency list）的概念。邻接表为图中的每个顶点创建一个链接表，报告与该顶点相邻的所有顶点及其相关信息。

邻接表对于搜索与特定顶点相邻的顶点非常有效。 与邻接矩阵不同，邻接表不需要扫描不相关的顶点，要扫描的顶点数量就是有效顶点的数量，节省时间。 同时，其空间负责O（n+e），与邻接矩阵相比，空间利用率很高。 然而，与邻接矩阵相比，当需要确定顶点u和v之间是否存在关系时，邻接表就变得很麻烦，需要扫描u和v的所有相邻顶点来确定它们之间是否存在关系。 因此，对于那些需要大量扫描相邻顶点而很少确定两个顶点之间关系的问题，使用邻接表是合适的。

虽然访问一条边的效率不高，但邻接表适合于处理与一个顶点相关的所有边的批处理。 大多数图论算法是以批处理的形式运作的。 因此，总体而言，邻接表比邻接矩阵更有效率。

2.并查集

本节讨论了并查集Union Find，这是图论问题中常用的一种数据结构。并查集是用来处理一些不交集（Disjoint）的合并和查询的。它有两个功能：第一，确定任何两个元素是否属于同一个集合，第二，根据需要合并不同的集合。

首先，集合在逻辑上表示为一个树状结构，每个节点都指向它的父节点，书中的元素没有任何顺序，只要它们在同一棵树上，就属于同一个集合。

有两种合并集合的操作，即（Find）和合并（Union）。

①查找：确定一个元素属于哪个集合。这种方法是在树上查找，直到找到它所跟随的节点，然后根据节点是否相同来确定两个元素是否属于同一个集合。

②合并：将两个子集合并为同一个集。这种方法涉及使一棵树成为另一棵树的子树，从而使两棵树成为一棵更大的树。

然而，采用这种没有任何约束的合并策略可能会引起某些众所周知的问题。如前所述，对集合的操作主要是通过寻找树的根节点实现的。合并集中最重要的操作是找到一个结点所在的树的根结点，方法是不断寻找该结点的父结点，直到找到一个不存在父结点的结点，这就是根结点。这个过程所花费的时间与该结点到树根的距离有关，也就是与树的高度有关。在合并两棵树的过程中，如果不采取任何行动就简单地合并两棵树，树的高度可能会逐渐增加，找到根节点所需的时间也会逐渐增加，在极端情况下，树可能会退化成一个单链表，在这个表上找到根节点将非常耗时。树的不同形状对查找的效率有很大影响。

为了避免因树的退化而造成额外的时间消耗，合并两棵树不应该听之任之，而是应该加入某些约束和优化，以保持树的高度尽可能低。这可以通过寻找特定结点的根而将其与根结点之间的所有结点直接指向根节点来实现，这个过程被称为路径压缩。

路径压缩的工作完成后，树的形状发生了很大的变化，比如树的高度大大降低，而树所代表的集合信息却没有变化，所以在保证集合信息不变的情况下，其结构得到了极大的优化，为后续的查找工作节省了大量的时间。

此外，在合并两棵树时，高度较低的树总是作为高度较高的树的子树被合并。因为影响查找效率的是树的高度，所以高度较低的书作为高度较高的树的子树时，不会增加合并后的树的高度，从而提高后续查找的效率。

3.最小生成树

本节讨论了图论中的一个经典问题，即最（Minimum Spanning Tree, MST）。在一个无向连通图G(V, E)中，如果存在一个包含原图所有顶点和部分边的连接子图，且该子图中没有循环回路，则称该连接子图为原图的生成树。在一个加权的无向连接图中，所有生成树中边权之和最小的树（或几棵）被称为无向图的最小生成树。

最小生成树问题在现实生活中有着广泛的应用。例如，在通信基站之间建立一条通信电缆，使所有基站能够直接或间接地相互通信，所需的最小光缆长度是多少？要使用最小生成树来解决实际问题，必须学会如何解决连通图的最小生成树。

有许多构建最小生成树的算法，最常见的是Kruskal的算法和Prim的算法。由于篇幅所限，这里介绍的是Kruskal算法。

克鲁斯卡算法的原理是：在一个需要求解的连通图中，任意选择一些点属于集合A，其余的点属于集合B，最小生成树必须有一条权重最小的边，这条边的两个顶点分别属于集合A和B的边（即连接这两个集合的边）。

这个命题可以用反转法来证明：让连接顶点集A和顶点集B的边中权重最小的一条边为e，图中的最小生成树都不包含这条边，但在任何最小生成树中，一定有一条连接集A和集B的边（如果没有，那么这两个集就不相连，如果大于一条，就有一个循环）。但在任何最小生成树中，一定有一条连接集合A和集合B的边（如果没有，则这两个集合不相连，如果大于一条边，则有一个循环），让这条边为e1。根据命题，我们知道e的重量不大于e1的重量。如果用边e替换e1，替换后的子图仍然是原图的生成树，生成树的权重是原最小生成树的权重减去e1的权重 加上e的权重，不会大于原最小生成树，与假设矛盾，原命题被证明。

Kruskal算法得步骤如下：

①初始所有顶点属于孤立得集合。

②按照边权递增得顺序遍历所有边，若遍历到的边的两个顶点仍属于不同的集合（该边即为连通这两个集合的边中权值最小的那条），则确定该边为最小生成树上的一条边，并将该边两个顶点分属的集合合并。

③遍历完所有边后，若原图连通，则被选取的边喝所有顶点构成最小生成树，若原图不连通，最小生成树不存在。

如以上步骤所示，在用Kruskal算法求解最小生成树的过程中会涉及大量的集合操作，恰好可以使用上衣节中讨论的并查集来实现这些操作。

Kruskal算法步骤如下。

① 最初，所有顶点都属于一个孤立的集合。

②如果所遍历的边的两个顶点仍然属于不同的集合（该边是两个集合中权重最低的一个），则确定该边为最小生成树中的一条边，并将该边的两个顶点所属的集合合并。

③在遍历了所有的边之后，如果原图是连接的，所选的边喝所有的顶点形成最小生成树，如果原图不连接，最小生成树不存在。

④如上述步骤所示，使用Kruskal算法求解最小生成树时涉及大量的集合操作，使用上一节讨论的并查集来实现这些操作是合适的。

参考文献：

[1] Berge, Claude, Théorie des graphes et ses applications, Collection Universitaire de Mathématiques II, Paris: Dunod, 1958. English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.

[2] Biggs, N.; Lloyd, E.; Wilson, R., Graph Theory, 1736–1936, Oxford University Press, 1986.

[3] Bondy, J.A.; Murty, U.S.R., Graph Theory, Springer, 2008, ISBN 978-1-84628-969-9.

[4] Chartrand, Gary, Introductory Graph Theory, Dover, 1985, ISBN 0-486-24775-9.

[5] Gibbons, Alan, Algorithmic Graph Theory, Cambridge University Press, 1985.

[6] Golumbic, Martin, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.

[7] Harary, Frank, Graph Theory, Reading, MA: Addison-Wesley, 1969.