七、图

7.1图的定义

图( Graph)是由顶点的有穷非空集合和顶点之间边的集合组，通常表示为: G(V,E),其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点(Vertex）

线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。那么对于图呢？在图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。

线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

7.1.1 各种图的定义

无序对(unordered pair)一种特殊的集合.即仅含两个元素的集合.

有向图

每条边都是有方向的

无向图

每条边都是无方向的

完全图

任意两个点都有一条边相连

稀疏图

有很少边或弧的图(e <nlogn)

稠密图

有较多边或弧的图

网

边/弧带权的图

邻接

有边/弧相连的两个顶点之间的关系

存在(Vi, Vj),则称v和v:互为邻接点;

存在<Vi, Vj>,则称Vi邻接到Vj, Vj邻接于Vi;

关联(依附)

边/弧与顶点之间的关系

存在(Vi, Vj)/<Vi, Vj>，则称该边/弧关联于Vi和Vj;

顶点的度

与该顶点相关联的边的数目，记为TD(v)

在有向图中，顶点的度等于该顶点的入度与出度之和。

顶点V的入度是以v为终点的有向边的条数,记作ID(v)

顶点v的出度是以V为始点的有向边的条数，记作OD(v)

看实例：

当有向图中仅1个顶点的入度为0,其余顶点的入度均为1,此时是何形状?

是树!而且是一棵有向树!

路径

若干条边构造的顶点序列

路径长度

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

如果没有权值，上图这个路径的长度就是2

如果边有权值，那么边上的权值相加就是路径长度

回路(环)

第一个顶点和最后一个顶点相同的路径

简单路径

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

简单回路(简单环)

除路径起点和终点相同外，其余顶点均不相同的路径。

连通图(强连通图)

在无(有)向图G=(V, {E} )中，若对任何两个顶点v、u都存在从V到u的路径，则称G是连通图(强连通图)

从图中能很明白的看出各个概念之间的差异

这里不多解释

子图

如上，可以轻松看出图b和图c都是图a的子图

连通分量

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

极大连通子图是指顶点的个数已经是最大的了，在添加顶点的话子图不能形成连通了

强连通分量

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

极大强连通子图意思是:该子图是G的强连通子图，将D的任何不在该

子图中的顶点加入，子图不再是强连通的。

极小连通子图

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

极小连通子图可以包含所有顶点，也可以不包含所有顶点

生成树

包含无向图G所有顶点的极小连通子图

生成森林

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

7.1.2图的定义与术语总结

图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。

图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图

图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。

图上的边或弧上带权则称为网。

图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。

无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若千棵有向树构成生成森林。

7.2图的抽象数据类型

ADT图(Graph)
Data
  顶点的有穷非空集合和边的集合。
Operation
    CreateGraph (*G,V,VR) :按照顶点集V和边弧集VR的定义构造图G。
    DestroyGraph(*G) :图G存在则销毁。
    LocateVex(G,u) :若图G中存在顶点u，则返回图中的位置。
    GetVex (G,v) :返回图G中顶点v的值。
    PutVex (G,v,value) :将图G中顶点v赋值value。
    FirstAdjVex (G,*v) :返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空。
    NextAdjVex (G,v,*w) :返回顶点v相对于顶点w的下一一个邻接顶点，若w是v的最后
          一个邻接点则返回“空"。
    InsertVex (*G,v) :在图G中增添新顶点V。
    DeleteVex ( *G,v):删除图G中顶点v及其相关的弧。
    InsertArc ( *G,v,w):在图G中增添弧<v,w>,若G是无向图，还需要增添对称弧
          <w,v>。
    DeleteArc (*G,v,w):在图G中删除弧<v,w>,若G是无向图，则还删除对称弧
    DFSTraverse(G):对围G中进行深度优先遍历，在遍历过程对每个顶点调用。
    HFSTraverse(G) :对图G中进行广度优先遍历，在遍历过程对每个顶点调用。
endADT

7.3图的存储结构

7.3.1领接矩阵

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

1.无向图的邻接矩阵

2.有向图的邻接矩阵

分析1: 有向图的邻接矩阵可能是不对称的。

分析2: 顶点的出度=第i行元素之和

顶点的入度=第列元素之和

顶点的度=第i行元素之和+第j元素之和

3.网(即有权图)的邻接矩阵表示法

代码实现：

用两个数组分别存储顶点表和邻接矩阵

#define MaxInt 32767  //表示极大值，即∞
#define MVNum 100 //最大顶点数
typedef char VerTexType;  //设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
typedef struct{
    VerTexType vexs{MVNum]; //顶点表
    ArcType arcs[MVNum][MVNum];  //邻接矩阵
    int vexnum, arcnum;    //图的当前点数和边数。
}AMGraph;  // Adjacency Matrix Graph

7.3.2邻接表

为了解决边数相对顶点较少的图，邻接矩阵这种结构会存在大量的空间浪费

如下：

再回忆我们在树中谈存储结构时，讲到了一种孩子表示法，将结点存入数组，并对结点的孩子进行链式存储，不管有多少孩子，也不会存在空间浪费问题。这个思路同样适用于图的存储。我们把这种数组与链表相结合的存储方法称为邻接表

(Adjacency List)。

邻接表的处理办法：

1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。

2.图中每个顶点Vi的所有邻接点构一个线性表，由于邻接点的个数不定,所以用单链表存储，无向图称为顶点Vi的边表，有向图则称为顶点Vi作为弧尾的出表。

上图中的V1顶点与V0、V2互为邻接点，则在V1的边表中，adjvex分别为V0的0和V2的2

下面解释什么是边表

顶点表的各个节点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，**指向边表(因为它是无向图，所以叫边表)**的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex 是邻接点域，存储某顶点的邻接点在顶点表中的下标，next 则存储指向边表中下一个结点的指针。

在有向图中，邻接表的结构是类似的

我们可以建立一个有向图的逆邻接表，即对每个顶点Vi都建立一个链接为v为弧头的表

此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可

7.3.3十字链表

那么对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢?答案是肯定的，就是把它们整合在一起。这就是我们现在要讲的有向图的一种存储方法:十字链表(Orthogonal List)。

重新定义结点表结点结构

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点， firstout 表示出边表头指针，指向该顶点的出边表中的第一个结点。

重新定义边表结点结构

其中**tailvex 是指弧起点在顶点表的下标，headvex 是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，tallink 是指边表指针域，指向起点相同的下一条边。**如果是网，还可以再增加一个 weight域来存储权值。

实例如下：

以顶点V0来说，firstout指向的是出边表中的第一个结点V3所以tailvex和headvex是03（就是数组下标），那为什么headlink和taillink为空了呢，因为没用终点和V0一样的结点了（指向V3的），那为什么taillink也为空呢，因为没有和V0一样起点的结点（从V0出发）了呀！

图中也有些例子，可以多理解理解

同志们一定好好看看和理解这个图！！！

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样很容易找到以Vi为尾的弧，也容易找到以vi为头的弧，从而更容易求得顶点的出度和入度

缺点就是结构复杂了一点，在有向图的应用中，十字链表是非常好的数据结构模型