第7章 图结构

第7章 图 结 构

本章学习要点

◆熟悉图的定义、相关术语以及基本概念

◆熟练掌握图的4种存储结构，能根据实际问题选择合适的存储结构 ◆熟练掌握图的两种遍历方法

◆理解并掌握最小生成树意义和两种算法 ◆理解并掌握查找最短路径的有关算法 ◆理解并掌握拓扑排序的有关算法 ◆理解并掌握查找关键路径的有关算法

在计算机科学、工程以及其它许多学科中，常常需要研究数据对象之间的各种关系。比如，可以用线性表来表示数据对象之间的线性关系，用树结构来表示数据对象之间的某种层次关系。但是，还有许多问题（比如信息通信网络）中的数据对象是不能用以上两种关系来明确表示的，这就需要一种更为复杂的数据结构—图结构。图结构可以用来表示数据对象之间的任意关系，图中的每个结点都可以和其它任一结点相连接，即图中数据对象之间的对应关系是“多个对多个”的关系。

本章将详细介绍图的基本概念、各种存储结构、遍历方法，求图的连通分量、生成树、最短路径，最后介绍一些有关图的应用问题。

7.1图的定义和基本术语

7.1.1图的定义

图G(graph) 是由两个集合V和VR组成，记为G=(V,VR)。V是顶点的有穷非空集合；VR

是定义在V上的所有关系（两个不同顶点之间的弧或边）的集合。VR可以是空集合，当VR为空集时G表示集合类结构类型。如图7.1(a)、(b)所示的是一个有向图和一个无向图。

7.1.2图结构的基本术语

（1）顶点(Vertex) 图中的数据元素。比如，图7.1中的顶点有：v1,v2,v3,v4,v5,v6。

（2）弧(Arc) 设VR是图中所有顶点之间的关系集，若∈VR，则表示从顶点v

-.167.-

第7章 图结构

到顶点w的一条弧。

例如，在图7.1(a)所示的图G中的弧有：,,,,,和,共8条弧。 （3）弧尾(Tail) 弧的起始点。

（4）弧头(Head) 弧的终端点。一条弧用有序对符号“<弧尾，弧头>”来表示。

（5）有向图(Digraph) 由顶点和弧组成的图称为有向图。比如，图7.1(a)表示一个有向图。 （6）边(Edge) 设VR是图中所有顶点之间的关系集，若∈VR必有∈VR，则以无序对符号(v,w)或(w,v)来代替和，表示顶点v与顶点w之间的一条边。

例如，在图7.1(b)所示的图G中的边有：(v1,v2),(v1,v4),(v2,v3),(v2,v6),(v3,v5),(v4,v5)和(v5,v6)共7条边。 （7）无向图(Undigraph) 由顶点和边组成的图称为无向图。比如，图7.1(b)表示一个无向图。 （8）完全图(Completed graph) 用n表示图中的顶点数，则具有n(n-1)/2条边的无向图称为无向完全图；具有n(n-1)条弧的有向图称为有向完全图。当图G中边(或弧)的总数e满足：

e?nlogn时，称其为稀疏图(sparse graph)；当e满足：e?nlogn时称其为稠密图(dense

graph)。显然，完全图是稠密图，反之不然。图7.2(a)所示为由4个顶点组成的无向完全图，而图7.2(b)则是由3个顶点组成的有向完全图。

（9）权(Weight) 与图的边或弧相关的数（比如长度）称为权。

（10）网(Network) 具有权值的图称为网，带权的有向图称为有向网，带权的无向图称为无向网。比如，图7.3(a)表示的是一个有向网，而图7.3(b)表示的是一个无向网。

（11）子图(Subgraph) 假设有两个图G=(V,E)和G=(V,E)，若V’?V并且E’?E，则称G’

’

’

’

是G的子图。

例如，图7.4(a)为有向图及其部分子图，图7.4(b)为无向图及其部分子图。

-.168.-

第7章 图结构

（12）邻接点(Adjacent) 对于无向图G=(V,VR)，若边(v,w)∈VR，则称v和w互为邻接点，边(v,w)依附(Incident)于顶点v和w，或者说边(v,w)与顶点v、w相关联。对于有向图G=(V,VR)，若弧∈VR，则称顶点v邻接到顶点w，顶点w邻接自顶点v。

（13）度(Degree) 在无向图中，顶点v的度是指和v相关联的边的数目，记为TD(v)。 （14）出度(Out degree)和入度(In degree) 在有向图中，顶点v的出度是指以v为弧尾的弧的数目，记为OD(v)；顶点v的入度是指以v为弧头的弧的数目，记为ID(v)；顶点v的度是指v的出度、入度的和，记为TD(v)。

一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点e条边（或弧）的图，必定满足关系如下：

1ne??TD(vi)

2i?1（15）路径(Path) 在图中，从顶点v到顶点w的顶点序列称为路径。显然，有向图的路径是有向的。路径长度是指路径上的边或弧的数目。序列中顶点不重复出现的路径称为简单路径。

（16）回路或环(Cycle) 在路径的顶点序列中，第一个顶点和最后一个顶点相同的路径称为回路。除了第一个顶点和最后一个顶点外，其余顶点均不重复出现的回路称为简单回路或简单环。

例如，在图7.4(a)所示的有向图中，顶点序列(v1,v3,v4,v1,v2)表示一条有向路径，由于其中存在重复点v1所以不是简单路径，该路径的长度为4；顶点序列(v1,v3,v4)表示一条有向路径，并且是长度为2的简单路径；顶点序列(v1,v3,v4,v1)表示一条有向路径并且是长度为3的简单回路（或环）。在图7.4(b)所示的无向图中，顶点序列(v1,v3,v5,v4,v3,v5,v2)表示一条路径，由于其中存在重复点v3、v5所以不是简单路径；顶点序列(v1,v3,v4,v5,v2,v1)是长度为5的简单回路。 （17）连通图(Connected graph) 在无向图G=(V,VR)中，如果从顶点v到顶点w有路径，则称v与w是连通的。如果对于任意两个顶点v,w∈V都是连通的则称G是连通图。

（18）连通分量(Connected component) 无向图G中的极大连通子图称为G的连通分量。图7.5给出一个无向图和它的3个连通分量的示例。

（19）强连通图 在有向图G=(V,VR)中，如果对于任意两个顶点v,w∈V，都存在一条v到w

-.169.-

第7章 图结构

的路径，则称G是强连通图；如果对于任意两个顶点v,w∈V，都存在一个顶点序列：v=v0,v1,v2,…,vk=w满足或∈VR，则称G是弱连通图。

例如，图7.1(a)为弱连通图，图7.2(b)为强连通图。

（20）强连通分量 有向图G中的极大强连通子图称为G的强连通分量。图7.6给出一个有向图和它的2个强连通分量的示例。

说明：

在连通分量和强连通分量定义中的“极大”应理解为包含依附于该连通子图或强连通子图中顶点的所有边或弧。

（21）生成树 一个无向连通图的生成树是一个极小连通子图，即它包含图中的所有（假设n个）顶点，但是只有足以构成一棵树的n-1条边。 说明：

1）一个无向连通图的生成树不是唯一的，所有生成树的顶点相同但是所包含的边可以不同。

2）一棵有n个顶点的连通图的生成树有且仅有n-1条边。但是有n个顶点和n-1条边的无向图不一定是生成树。

例如，图7.7给出一个连通图(图7.7(a))和它的3棵生成树(图7.7(b))的示例。

（22）生成森林 如果一个有向图G恰有一个顶点的入度为0，其余顶点的入度均为1，则G是一棵有向树。一个有向图的生成森林由若干棵有向树组成，森林中含有图中全部顶点，但是只有足以构成若干棵不相交的有向树的弧。显然，一个有向图生成的有向树或生成森林都不是唯一的。

关于“顶点位置”的说明：

在图的基本操作定义中，其“顶点位置”和“邻接点位置”仅是一个相对的概念。从图的定义

-.170.-