数据结构第七章

图(Graph)G由两个集合V和E组成，记为G=(V, E)，其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。V(G)和E(G)通常分别表示图G的顶点集合和边集合，E(G)可以为空集。若EG)为空，则图G只有顶点而没有边。

子图：假设有两个图G=(V,E)和G1=（V1,E1）;如果V1V，E1E，则称G1为G的子图。

完全图：任意两个顶点都有一条边相连。（指的是无向图）

无向完全图和有向完全图:对于无向图，若具有n(n-1)/2条边，则称为无向完全图；对于有向图,若具有n(n-1)条弧,则称为有向完全图。

稀疏图和稠密图:有很少条边或弧（如e<nlogn)的图称为稀疏图，反之称为稠密图

权和网:在实际应用中，每条边可以标上具有某种含义的数值，该数值称为该边上的权，这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。

邻接点:对于无向图G，如果图的边(v, v1)E，则称顶点v和v1互为邻接点，即v和v1相邻接。

关联（依附）：边/弧与顶点之间的关系；边(v, v')依附于顶点v和v1，或者说边(v, v1)与顶点v和v1相关联。

顶点的度：与该顶点相关联的边的数目，记为TD(v);在有向图中，顶点的度等于该顶点的入度与出度之和，顶点v的入度是以v为终点的有向边的条数，记作ID(v),顶点的出度是以v为始点的有向边的条数，记作OD(v)。

路径：接续的边构成的顶点序列

路径长度：路径上边或弧的数目/权值之和

回路(环)：第一个顶点和最后一个顶点相同的路径

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径

简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径。

连通：两个顶点之间有路径，则称这两个顶点是连通的。

连通图：对于图中任意两个顶点都是连通的，则称该图是连通图

强连通图：在有向图中对于任意两个顶点是连通的，则称该图是强连通图。

连通分量：指的是无向图中的极大连通子图（极大连通子图意思为该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不再连通）

强连通分量：有向图的极大强连通子图

极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边子图不再连通

连通图的生成树：包含无向图所有顶点的极小连通子图

有向树：有一个顶点的入度为0，其余顶点的入度均为1的有向图称为有向树

生成森林：对于非连通图，由各个连通分量的生成树的集合

图的基本概念：

1、有向图

若E是有向边(也称弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v, w>，其中v,w是顶点，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。

图(a)所示的有向图G可表示为：

2、无向图

若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v, w相关联。

图(b)所示的无向图G2可表示为：

无向图是对称的

3、完全图（也称简单完全图）

对于无向图，∣E∣的取值范围是0 到n ( n ? 1 ) / 2 ，有n ( n ? 1 ) / 2 条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，∣E∣的取值范围是0 到n ( n ? 1 ) ，有n ( n ? 1 ) 条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。

4、稠密图、稀疏图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足∣ E ∣ < ∣ V ∣ l o g ∣ V时，可以将G 视为稀疏图。

5、子图

设有两个图G = ( V , E ) 和G ′ = ( V ′ , E ′ ) ，若V '是V 的子集，且E ′?是E 的子集，则称G ′ G的子图。

6、出度、入度

出度：以尾为弧

入度：以头为弧

对于无向图，顶点v的度是指依附于该顶点的边的条数，记为T D ( v )。在具有n 个顶点、e 条边的无向图中，

7、回路或环

第一个顶点和最后一个顶点相同

8、连通图

图中任意两顶点连通，则这个图为连通图（它是无向图）

9、非连通图

如果一个图有n个顶点和小于n-1条边，就是非连通图

10、生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n ,则它的生成树含有n ? 1 条边（无向图）

11、生成森林

一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一颗有向树。生成森林由多个有向树组成。

图的存储结构：

数组表示法：

用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）

其中图用0或1来表示，网用权或者∞来表示

网的邻接矩阵：

定义：? ? ? ? ? ? ? ? ? ? ? ? ? ?

? 若<>或（）

? ? ? ? ? ? ? ? ?∞? ?反之

图的邻接表特点：有e条边就会有2e个1对称，即：

邻接表：

邻接表是一种常用的图的数据结构，用于表示图中顶点之间的关系。它通过使用链表来存储每个顶点的邻接点。

在邻接表中，图的顶点被表示为一个数组，数组的每个元素都是一个链表。链表中的每个节点表示一个邻接点，节点中存储了与该顶点相邻的顶点的信息。

连接点域：指示与定点邻接的点在图中位置（下标）

链域：下一条边或弧的结点

数据域：数据域存储和边或弧相关的信息，如权值

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?头结点

data数据

firstarc(指针)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?表结点
?

adjvex? ??

? ? ? ? ? nextarc

? ? ? ? info

若无向图中有n个顶点，e条边，则它的邻接表需n个头结点和2e个表结点

若有向图中有n个顶点，e条边，则它的邻接表需n个头结点和e个表结点

图的遍历（相当于树）：

深度优先搜索类似于树的先序遍历(广度=层次)。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点再访问与邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

图的连通性：

最小生成树：

一颗生成树就的代价就是树上各代价之和。对于一个带权连通无向图G = ( V , E ) ，生成树不同，其中边的权值之和最小的那棵生成树（构造连通网的最小代价生成树），称为G的最小生成树。

克鲁斯卡尔算法：

构造最小生成树的过程如下图所示。初始时为只有n个顶点而无边的非连通图T = V ，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T ，否则舍弃此边而选择下一条权值最小的边。以此类推，直至T 中所有顶点都在一个连通分量上。

我们将下面左图的邻接矩阵通过程序转化为右图的边集数组，并且对它们按权值从小到大排序

拓扑排序

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤:

①从AOV网中选择一个没有前驱的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是AOV网。