2.8　图结构

图（Graph）结构也是一种非线性数据结构，图结构在实际生活中具有丰富的例子。例如，通信网络、交通网络、人际关系网络等都可以归结为图结构。图结构的组织形式要比树结构更为复杂，因此，图结构对存储和遍历等操作具有更高的要求。

2.8.1　什么是图结构

前面介绍的树结构的一个基本特点是数据元素之间具有层次关系，每一层的元素可以和多个下层元素关联，但是只能和一个上层元素关联。如果将此规则进一步扩展，也就是说，每个数据元素之间可以任意关联，这就构成了一个图结构。正是这种任意关联性导致了图结构中数据关系的复杂性。研究图结构的一个专门理论工具便是图论。

典型的图结构，如图2-26所示。一个典型的图结构包括如下内容。

・顶点（Vertex）：图中的数据元素。

・边（Edge）：图中连接这些顶点的线。

所有的顶点构成一个顶点集合，所有的边构成边集合，一个完整的图结构由顶点集合和边集合组成。图结构在数学上一般记为以下形式：

G=（V，E）

或者

G=（V（G），E（G））

其中，V（G）表示图结构中所有顶点的集合，顶点可以用不同的数字或者字母来表示。E（G）是图结构中所有边的集合，每条边由所连接的两个顶点表示。

注意：图结构中顶点集合V（G）必须为非空，即必须包含一个顶点。而图结构中边集合E（G）可以为空，此时表示没有边。

例如，对于图2-26所示的图结构，其顶点集合和边集合如下：

V（G）={V1，V2，V3，V4，V5，V6}

E（G）={（V1，V2），（V1，V3），（V1，V5），（V2，V4），（V3，V5），（V4，V5），（V4，V6），（V5，V6）}

2.8.2　图的基本概念

图论是专门研究图结构的一个理论工具。为了讲解和读者理解的方便，这里简单介绍一些基本的图结构概念。

1）无向图

如果一个图结构中，所有的边都没有方向性，那么这种图便称为无向图。典型的无向图，如图2-27所示。由于无向图中的边没有方向性，这样，在表示边的时候对两个顶点的顺序没有要求。例如，顶点V1和顶点V5之间的边，可以表示为（V1，V5），也可以表示为（V5，V1）。

对于图2-27所示的无向图，对应的顶点集合和边集合如下：

V（G）={V1，V2，V3，V4，V5}

E（G）={（V1，V2），（V1，V5），（V2，V4），（V3，V5），（V4，V5），（V1，V3）}

2）有向图

如果一个图结构中，边有方向性，那么这种图便称为有向图。典型的有向图，如图2-28所示。由于有向图中的边有方向性，这样，在表示边的时候对两个顶点的顺序有要求。并且，为了同无向图区分，采用尖括号表示有向边。例如，<V3，V4>表示从顶点V3到顶点V4的一条边，而<V4，V3>表示从顶点V4到顶点V3的一条边。<V3，V4>和<V4，V3>表示的是两条不同的边。

对于图2-28所示的有向图，对应的顶点集合和边集合如下：

V（G）={V1，V2，V3，V4，V5，V6}

E（G）={<V1，V2>，<V2，V1>，<V2，V3>，<V3，V4>，<V4，V3>，<V4，V5>，<V5，V6>，<V6，V4>，<V6，V2>}

3）顶点的度（Degree）

连接顶点的边的数量称为该顶点的度。顶点的度在有向图和无向图中具有不同的表示。对于无向图，一个顶点V的度比较简单，其是连接该顶点的边的数量，记为D（V）。例如，在图2-27所示的无向图中，顶点V4的度为2，而V5的度为3。

对于有向图要稍复杂些，根据连接顶点V的边的方向性，一个顶点的度有入度和出度之分。

・入度是以该顶点为端点的入边数量，记为ID（V）。

・出度是以该顶点为端点的出边数量，记为OD（V）。

因此，有向图中，一个顶点V的总度便是入度和出度之和，即D（V）=ID（V）+OD（V）。例如，在图2-28所示的有向图中，顶点V3的入度为2，出度为1，因此，顶点V3的总度为3。

4）邻接顶点

邻接顶点是指图结构中一条边的两个顶点。邻接顶点在有向图和无向图中具有不同的表示。对于无向图，邻接顶点比较简单。例如，在图2-27所示的无向图中，顶点V1和顶点V5互为邻接顶点，顶点V2和顶点V4互为邻接顶点等。另外，顶点V1的邻接顶点有顶点V2、顶点V3和顶点V5。

对于有向图要稍复杂些，根据连接顶点V的边的方向性，两个顶点分别称为起始顶点（起点或始点）和结束顶点（终点）。有向图的邻接顶点分为如下两类。

・入边邻接顶点：连接该顶点的边中的起始顶点。例如，对于组成<V1，V2>这条边的两个顶点，V1是V2的入边邻接顶点。

・出边邻接顶点：连接该顶点的边中的结束顶点。例如，对于组成<V1，V2>这条边的两个顶点，V2是V1的出边邻接顶点。

5）无向完全图

如果在一个无向图中，每两个顶点之间都存在一条边，那么这种图结构称为无向完全图。典型的无向完全图，如图2-29所示。

理论上可以证明，对于一个包含N个顶点的无向完全图，其总的边数为N（N-1）/2。

6）有向完全图

如果在一个有向图中，每两个顶点之间都存在方向相反的两条边，那么这种图结构称为有向完全图。典型的有向完全图，如图2-30所示。

理论上可以证明，对于一个包含N个顶点的有向完全图，其总的边数为N（N-1），无向完全图的两倍。

7）子图

子图的概念类似子集合，由于一个完整的图结构包括顶点和边，因此，一个子图的顶点和边都应该是另一个图结构的子集合。例如，图2-31中，图（a）为一个无向图结构，图（b）、图（c）和图（d）均为图（a）的子图。

这里需要强调的是，只有顶点集合是子集的，或者只有边集合是子集的，都不是子图。

8）路径

路径即图结构中两个顶点之间的连线，路径上边的数量称为路径长度。两个顶点之间的路径可能途经多个其他顶点，两个顶点之间的路径也可能不止一条，相应的路径长度可能不一样。

图结构中的一条路径，如图2-32所示。这里粗线部分显示了顶点V5到V2之间的一条路径，这条路径途经的顶点为V4，途经的边依次为（V5，V4）、（V4，V2），路径长度为2。

同样，还可以在该图中找到顶点V5到V2之间的其他路径，分别为：

・路径（V5，V1）、（V1，V2），途经顶点V1，路径长度为2。

・路径（V5，V3）、（V3，V1）、（V1，V2），途经顶点V1和V3，路径长度为3。

图结构中的路径还可以细分为如下三种形式。

・简单路径：在图结构中，如果一条路径上顶点不重复出现，则称为简单路径。

・环：在图结构中，如果路径的第一个顶点和最后一个顶点相同，则称之为环，有时也称为回路。

・简单回路：在图结构中，如果除第一个顶点和最后一个顶点相同，其余各顶点都不重复的回路称为简单回路。

9）连通、连通图和连通分量

通过路径的概念，可以进一步研究图结构的连通关系，主要涉及如下内容：

・如果图结构中两个顶点之间有路径，则称这两个顶点是连通的。这里需要注意连通的两个顶点可以不是邻接顶点，只要有路径连接即可，可以途经多个顶点。

・如果无向图中任意两个顶点都是连通的，那么这个图便称为连通图。如果无向图中包含两个顶点是不连通的，那么这个图便称为非连通图。

・无向图的极大连通子图称为该图的连通分量。

理论可以证明，对于一个连通图，其连通分量有且只有一个，那就是该连通图自身。而对于一个非连通图，则有可能存在多个连通分量。例如，图2-33中，图（a）为一个非连通图，因为其中顶点V2和顶点V3之间没有路径。这个非连通图中的连通分量包括两个，分别为图（b）和图（c）。

10）强连通图和强连通分量

与无向图类似，在有向图中也有连通的概念，主要涉及如下内容：

・如果两个顶点之间有路径，也称这两个顶点是连通的。需要注意的是，有向图中边是有方向的。因此，有时从Vi到Vj是连通的，但从Vj到Vi却不一定连通。

・如果有向图中任意两个顶点都是连通的，则称该图为强连通图。如果有向图中包含两个顶点不是连通的，则称该图为非强连通图。

・有向图的极大强连通子图称为该图的强连通分量。

理论上可以证明，强连通图只有一个强连通分量，那就是该图自身。而对于一个非强连通图，则有可能存在多个强连通分量。例如，在图2-34中，图（a）为一个非强连通图，因为其中顶点V2和顶点V3之间没有路径。这个非强连通图中的强连通分量有两个，如图（b）和图（c）所示。

11）权

在前面介绍图的时候，各个边并没有赋予任何含义。在实际的应用中往往需要将边表示成某种数值，这个数值便是该边的权（Weight）。无向图中加入权值，则称为无向带权图。有向图中加入权值，则称为有向带权图。典型的无向带权图和有向带权图，如图2-35所示。

权在实际应用中可以代表各种含义，例如，在交通图中表示道路的长度，在通信网络中表示基站之间的距离，在人际关系中代表亲密程度等。

12）网（Network）

网即边上带有权值的图的另一名称。网的概念与实际应用更为贴切。

2.8.3　准备数据

学习了前面的理论知识后，下面就开始图结构的程序设计。首先需要准备数据，即准备在图结构操作中需要用到的变量及数据结构等。由于图是一种复杂的数据结构，顶点之间存在多对多的关系，因此无法简单地将顶点映射到内存中。

在实际应用中，通常需要采用结构数组的形式来单独保存顶点信息，然后采用二维数组的形式保存顶点之间的关系。这种保存顶点之间关系的数组称为邻接矩阵（Adjacency Matrix）。

这样，对于一个包含n个顶点的图，可以使用如下语句来声明一个数组保存顶点信息，声明一个邻接矩阵保存边的权。

char[] Vertex=new char[MaxNum]；//保存顶点信息（序号或字母））

int[][] EdgeWeight=new int[MaxNum][MaxNum]；//保存边的权

对于数组Vertex，其中每一个数组元素保存顶点信息，可以是序号或者字母。而邻接矩阵EdgeVeight保存边的权或者连接关系。

在表示连接关系时，该二维数组中的元素EdgeVeight[i][j]=1表示（Vi，Vj）或<Vi，Vj>构成一条边，如果EdgeVeight[i][j]=0表示（Vi，Vj）或<Vi，Vj>不构成一条边。例如，对于图2-36所示的无向图，可以采用一维数组来保存顶点，保存的形式如图2-37所示。

示例代码如下：

对于邻接矩阵，可以按照如图2-38所示进行存储。对于有边的两个顶点，在对应的矩阵元素中填入1。例如，V1和V3之间存在一条边，因此EdgeVeight[1][3]中保存1，而V3和V1之间存在一条边，因此EdgeVeight[3][1]中保存1。因此可见，对于无向图，其邻接矩阵左下角和右上角是对称的。

对于有向图，如图2-39所示。保存顶点的一维数组形式不变，如图2-40所示。而对于邻接矩阵，仍然采用二维数组，其保存形式如图2-41所示。对于有边的两个顶点，在对应的矩阵元素中保存1。这里需要注意，边是有方向的。

例如，顶点V2到顶点V3存在一条边，因此在EdgeVeight[2][3]中保存1，而顶点V3到顶点V2不存在边，因此在EdgeVeight[3][2]中保存0。

对于带有权值的图来说，邻接矩阵中可以保存相应的权值。也就是说，此时，有边的项保存对应的权值，而无边的项则保存一个特殊的符号Z。例如，对于图2-42所示的有向带权图，其对应的邻接矩阵，如图2-43所示。

这里需要注意的是，在实际程序中为了保存带权值的图，往往定义一个最大值MAX，其大于所有边的权值之和，用MAX来替代特殊的符号Z保存在二维数组中。

学习了前面的理论知识后，可以在程序中准备相应的数据用于保存图结构。示例代码如下：

在上述代码中，定义了图的最大顶点数MaxNum和用于保存特殊符号Z的最大值MaxValue。邻接矩阵图结构为GraphMatrix，其中包括保存顶点信息的数组Vertex，图的类型GType、顶点的数量VertexNum、边的数量EdgeNum、保存边的权的二维数组EdgeWeight及遍历标志数组isTrav。

2.8.4　创建图

在使用图结构之前，首先要创建并初始化一个图。代码示例如下：

在上述代码中，输入参数GM为一个指向图结构的引用。程序中，由用户输入顶点信息和边的信息。对于边来说，需要输入起始顶点、结束顶点和权值，各项以空格分割。最后，判断是否为无向图，因为无向图还需将边的权值保存到对角位置。

2.8.5　清空图

清空图即将一个图结构变成一个空图，这里只需将矩阵中各个元素设置为MaxValue即可。清空图的示例代码如下：

在上述代码中，输入参数GM为一个指向图结构的引用。程序中，通过双重循环为矩阵中各个元素赋值MaxValue，表示这是一个空图。

2.8.6　显示图

显示图即显示图的邻接矩阵，用户可以通过邻接矩阵方便地了解图的顶点和边等结构信息。显示图的示例代码如下：

在上述代码中，输入参数GM为一个指向图结构的引用。在程序中，首先在第1行输出顶点信息。然后，逐个输出矩阵中的每个元素。这里，以Z表示无穷大MaxValue。

2.8.7　遍历图

遍历图即逐个访问图中所有的顶点。由于图的结构复杂，存在多对多的特点，因此，当顺着某一路径访问过某顶点后，可能还会顺着另一路径回到该顶点。同一顶点被多次访问浪费了大量时间，使得遍历的效率低。

为了避免这种情况，可在图结构中设置一个数组isTrav[n]，该数组各元素的初始值为0，当某个顶点被遍历访问过，则设置对应的数据元素值为1。在访问某个顶点i时，先判断数组isTrav[i]中的值，如果其值为1，则继续路径的下一个顶点；如果其值为0，则访问当前顶点（进行相应的处理），然后继续路径的下一个顶点。

常用的遍历图的方法有两种：广度优先遍历法和深度优先遍历法。下面以深度优先遍历法为例进行介绍。深度优先遍历法类似于树的先序遍历，具体执行过程如下：

（1）从数组isTrav中选择一个未被访问的顶点Vi，将其标记为1，表示已访问。

（2）从Vi的一个未被访问过的邻接点出发进行深度优先遍历。

（3）重复步骤（2），直至图中所有和Vi有路径相通的顶点都被访问过。

（4）重复步骤（1）至步骤（3）的操作，直到图中所有顶点都被访问过。

深度优先遍历法是一个递归过程，具体的程序代码示例如下：

在上述代码中，方法DeepTraOne（）从第n个结点开始深度遍历图，其输入参数GM为一个指向图结构的引用，输入参数n为顶点编号。程序中通过递归进行遍历。

方法DeepTraGraph（）用于执行完整的深度优先遍历，以访问所有的顶点。其中，输入参数GM为一个指向图结构的引用。程序中通过调用方法DeepTraOne（）来完成所有顶点的遍历。

2.8.8　图结构操作实例

学习了前面的图结构的基本运算之后，便可以轻松地完成对图结构的各种操作。下面给出一个完整的例子，来演示图结构的创建和遍历等操作。完整的程序代码示例如下：

【程序2-6】

在主方法中，首先由用户输入图的种类，0表示无向图，1表示有向图。然后，由用户输入顶点数和边数。接着清空图，并按照用户输入的数据生成邻接表结构的图。最后，输出邻接矩阵并执行深度优先遍历法来遍历整个图。

整个程序的执行结果，如图2-44所示。这里输入的是一个无向图，包含4个顶点和6条边。