数据结构 第六章 图——图的定义和存储类型

在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前趋和直接后继；在树型结构中，数据元素之间有着明显的层次关系，并且每一层中的数据元素可能和下一层的多个元素相关，但只能和上一层的一个元素相关。而在图结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

6.1 图的定义和基本术语

6.1.1 图的定义

图（graph）G由两个集合V和E组成，其中V是顶点（vertex）的有穷非空集合，E是图中边的有穷集合。E(G)可以为空，但为空时G只有顶点而没有边。

下图就是一个无向图的例子。在这里插入图片描述
通过观察，我们可以看到上述图中的边并没有方向，所以我们把这类图叫做无向图，而 ( x , y ) (x,y) (x,y)表示从顶点x到顶点y的一条边，例如上图中的 ( v 1 , v 2 ) (v1,v2) (v1,v2)，就表示一条边。同样，由于它的边没有方向，因此 ( v 2 , v 1 ) (v2,v1) (v2,v1)与 ( v 1 , v 2 ) (v1,v2) (v1,v2)是一样的。

既然对于图来说，有无向图的说法，那么就一定会有有向图的说法，下图就是一个有向图的例子。在这里插入图片描述
为了跟无向图区别，有向图中一条边（有向图中的边也叫弧）由 < x , y > <x,y> <x,y>来表示，其中，x是有向边的始点（弧尾），y是有向边的终点（弧头）。

在了解了图的两种类型后，下面介绍图的基本术语

6.1.2 图的基本术语

对于一个图，我们用n表示图中顶点数目，用e表示边的数目。

  1. 子图：假设有两个图 G = ( V , E ) G=(V,E) G=(V,E)和 G ′ = ( V ′ , E ′ ) G^{'}=(V^{'},E^{'}) G′=(V′,E′)，如果 V ′ ⊆ V V^{'}\subseteq V V′⊆V且 E ′ ⊆ E E^{'}\subseteq E E′⊆E，则称 G ′ G^{'} G′为G的子图，例如：在这里插入图片描述

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

  3. 稀疏图和稠密图：有很少条边或弧( e < n log ⁡ 2 n e<n\log_2 n e<nlog2​n)的图称为稀疏图，反之称为稠密图。

  4. 权和网：在实际应用中，每条边可以标上具有某种含义的数值，该数值称为该边上的权。这种带权的图通常称为一个网。如下图在这里插入图片描述

  5. 邻接点：对于无向图，能够组成一条边的两个结点互为邻接点。

  6. 度、入度、出度：一个顶点v的度是指和该顶点相关联的边的数目，记为 T D ( v ) TD(v) TD(v)，如上图无向图G2中v3的度为3。对于无向图，顶点的度分为入度和出度。入度是以顶点v为头的弧（由邻接点指向该顶点）的数目，记为 I D ( v ) ID(v) ID(v)。出度是以顶点v为尾的弧（由该顶点指向邻接点）的数目，记为 O D ( v ) OD(v) OD(v)。有向图的顶点v的度为 T D ( v ) = I D ( v ) + O D ( v ) TD(v)=ID(v)+OD(v) TD(v)=ID(v)+OD(v)。例如，上图中有向图G1的顶点v1的入度为1，出度为2，则它的度就为3。

  7. 路径和路径长度：在无向图中，路径就是从一个顶点出发，经过其相关联的边到达另一顶点的过程。在有向图中，路径也就有方向了。路径长度就是一条路径上经过的边或弧的数目。

  8. 回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。

  9. 简单路径、简单回路、简单环：序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路或简单环。

  10. 连通、连通图、连通分量：在无向图中，如果两个顶点之间有路径，则称这两个顶点是连通的。如果对于图中任意两个顶点都有路径，即任意两个路径都连通，则称G为连通图。所谓连通分量，指的是无向图中的极大连通子图（注意理解“极大”）。例如下图：在这里插入图片描述

  11. 强连通图和强连通分量：在有向图中，若任意两个顶点间都有路径，则称G是强连通图。有向图中的极大强连通子图称作强连通分量。

  12. 连通图的生成树：一个极小连通子图，它含有图中全部顶点，但只有n-1条边，这样的连通子图称为连通图的生成树。一棵有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和小于n-1条边，则是非连通图。如果它多于n-1条边，则一定有环。但是，有n-1条边的图不一定是生成树。

  13. 有向树和生成森林：有一个顶点的入度为0，其余顶点的入度均为1的有向图称为有向树。一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。例如在这里插入图片描述

6.4 图的存储结构

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序存储结构。

但图是一个平面的结构，也就是说可以把图放在一个直角坐标系中，仅用两个坐标就可以表示其顶点。由此，我们可以发现二维数组也相当于是有两个“坐标”，而与二维数组相关联的也就是矩阵了。所以我们可以借助二维数组来表示元素之间的关系，称为邻接矩阵法。下面介绍邻接矩阵的方法。

6.4.1 邻接矩阵（无向图和有向图）

1. 邻接矩阵表示法

假设有一个数组 A [ i ] [ j ] A[i][j] A[i][j]， i i i和 j j j分别表示图中两个顶点的位置，若 i i i和 j j j之间存在边（有向图中的边带方向），则 A [ i ] [ j ] = 1 A[i][j]=1 A[i][j]=1，否则 A [ i ] [ j ] = 0 A[i][j]=0 A[i][j]=0。
上图中G1和G2的邻接矩阵如下图所示
G 1 = [ 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 ] G 2 = [ 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 ] G_{1}=\begin{bmatrix} 0&1&1&0\\ 0&0&0&0\\ 0&0&0&1\\ 1&0&0&0 \end{bmatrix} G_{2}=\begin{bmatrix} 0&1&0&1&0\\ 1&0&1&0&1\\ 0&1&0&1&1\\ 1&0&1&0&0\\ 0&1&1&0&0\\ \end{bmatrix} G1​=⎣⎢⎢⎡​0001​1000​1000​0010​⎦⎥⎥⎤​G2​=⎣⎢⎢⎢⎢⎡​01010​10101​01011​10100​01100​⎦⎥⎥⎥⎥⎤​

若G是网，则邻接矩阵可以定义为
A [ i ] [ j ] = { w i , j         若 这 两 个 顶 点 之 间 存 在 边 ∞           这 两 个 顶 点 之 间 不 存 在 边 A[i][j]=\begin{cases} w_{i,j} ~~~~~~~若这两个顶点之间存在边\\ \infty ~~~~~~~~~这两个顶点之间不存在边\\ \end {cases} A[i][j]={wi,j​       若这两个顶点之间存在边∞         这两个顶点之间不存在边​

对于邻接矩阵表示法，这里的二维数组是用来表示两个顶点间的关系的。而对于单个的顶点，我们需要分别存储它们的信息。那么对于此，我们就可以再用一个一维数组来存储顶点的信息。其具体存储表示如下：

#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;

2. 采用邻接矩阵表示法创建无向网

算法分析：

  1. 首先我们要知道该无向图有多少个顶点和边，以便后面我们建立相应的数组。
  2. 知道了它们的个数后，我们就可以开始建立一维数组来存储顶点的信息，然后构造二维数组并初始化。
  3. 初始化后，我们要考虑的就是如何确定两顶点构成的边在邻接矩阵中的位置并将边值输入到邻接矩阵中。
  • 由二维数组可知，一条边的位置由 i i i和 j j j确定， i i i和 j j j也就是两顶点在一维数组中的下标
  • 由此，我们可以创建一个函数来求两顶点的下标
  • 学过线性代数的小伙伴们应该对这块内容问题不大

具体算法：

#define Ok 0

typedef int Status;

int LocateVex(AMGraph G, VerTexType v)
{
	int num = 0;
	for (int i = 0; i <= G.vexnum; i++)
	{
		if (v == G.vexs[i])
		{
			num = i;
				break;
		}
	}
	return num;
}

Status CreateUDN(AMGraph &G)
{
	ArcType i, j, k,w;
	VerTexType v1, v2;
	printf("请输入总顶点和总边数：");
	scanf("%d,%d"), &G.vexnum, &G.arcnum);
	printf("请输入顶点的信息：");
	for (i = 0; i < G.vexnum; i++)
		scanf("%c", &G.vexs[i]);
	for (i = 0; i < G.vexnum; i++)
		for (j = 0; j < G.vexnum; j++)
			G.arcs[i][j] = MaxInt;
	for (k = 0; k < G.arcnum; k++)
	{
		printf("请输入一条边依附的顶点及权值：");
		scanf("%c,%c,%d", &v1, &v2, &w);
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j] = w;
		G.arcs[j][i] = G.arcs[i][j];
	}
	return OK;
}

该算法的时间复杂度是 O ( n 2 ) O(n^2) O(n2)。上述是针对于无向网的代码，而对于无向图，只需要将边的权值初始化为0，再将权值w改为1即可。

3. 邻接矩阵表示法的优缺点

  1. 优点
  • 便于判断两个顶点之间是否有边
  • 便于计算各个顶点的度
  1. 缺点
  • 不便于增加和删除顶点
  • 不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕
  • 空间复杂度高。这对于稀疏图而言尤其浪费空间

下面介绍适合表示稀疏图的表示方法——邻接表

6.4.2 邻接表（无向图）

1. 邻接表表示法

邻接表（Adjacency List）是图的一种链式存储结构。所谓邻接表，就是每个顶点后面链接与该顶点邻接的结点（该顶点和链接的每个结点都可以构成一条边），然后又将每个顶点整合在一起，组成一个结构体数组。我们将该结构体称为顶点结点表，把链接的邻接结点称为边结点。

  1. 顶点结点表
    所有顶点以顺序结构的形式存储。该结点包括数据域（data） 和链域（firstarc） 两部分。数据域用于存储顶点 v i v_{i} vi​的名称或其它有关信息；链域用于指向链表中第一个结点（与该顶点邻接的第一个邻接点）。

  2. 边结点表
    边结点包括邻接点域（adjvex）、数据域（data） 和链域（nexarc） 三部分。其中，邻接点域致使与顶点邻接的点在图中的位置（相当于顶点结点表中顺序存储的下标）；数据域存储和边相关的信息（没有时可以不用）；链域致使与顶点邻接的下一条边的结点。

两表中的链域都是指示邻接点。

下面为G1、G2 的邻接表在这里插入图片描述

在这里插入图片描述
有了前面的描述，对于邻接表的存储结构表示就更简单了

#define MVNum 100			//最大顶点数
typedef struct ArcNode		//边结点
{
	int adjvex				//该边所指向的顶点的位置
	struct ArcNode *nextarc;
	OtherInfo info;
}ArcNode;
typedef struct VNode		//顶点
{
	VerTexType data;
	ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct				//链接表
{
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;

有了邻接表的存储表示了之后，我们就可以着手开始采用邻接表创建图了。

2. 采用邻接表表示法创建无向图

算法分析：

  1. 首先我们还是要先确定该图有几个顶点和边，即先输入最大顶点数和最大边数
  2. 然后我们将顶点结点表初始化，输入每个顶点的信息（即值域data），并将其每个指针初始化为NULL。
  3. 初始化工作完成后，一般来说，我们是先选取一个顶点 v i v_{i} vi​及其邻接点 v j v_{j} vj​，然后找到该顶点及其邻接点在图中的位置（即顶点结点表中的顶点下标）
  4. 找到位置后，由于顶点和其邻接点属于不同的结点，而在前面我们并没有对边结点做相应的操作，所以在这里我们应创建一个新的边结点p1，使adjvex的值为该顶点在图中的位置，然后使 v i v_{i} vi​的链域指向p1。
  5. 又因为我们创建的是无向表，所以我们也要在图中找到 v j v_{j} vj​的位置，然后生成另一个新的边结点p2，使adjvex的值为该邻接点在图中的位置，并使 v j v_{j} vj​指向p2。
  6. 对于多个邻接点，我们采用的是前插法

算法具体实现：

Status CreateUDG(ALGraph &G)
{
	printf("请输入总顶点数和总边数：\n");
	scanf("%d,%d",&G.vexnum,&G.arcnum);
	for(int i=0;i<G.vexnum;i++)
	{
		printf("请输入每个顶点的值：\n");
		scanf("%c",&G.vertices[i]);
		G.vertices[i].firstarc=NULL;
	}	
	for(int k=0;k<G.arcnum;k++)
	{
		int i,j;
		VerTexType v1,v2;
		printf("请输入一个顶点及其邻接点的值：\n");
		scanf("%c,%c",&v1,&v2);
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		
		p1=(ArcNode*)malloc(sizeof(ArcNode));
		p1->adjvex=i;
		p1->nextarc=G.vertices[i].firstarc;			//G.vertices[i].firstarc表示顶点结点指向的第一个边结点，没有指向任何结点时其值为NULL
		G.vertices[i].first=p1;
		
		p2=(ArcNode*)malloc(sizeof(ArcNode));
		p2->adjvex=j;
		p2->nextarc=G.vertices[j].firstarc;
		G.vertices[j].firstarc=p2;
	}	
	return OK;
}

值得注意的是，一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法，以及边的输入次序。

3. 邻接表表示法的优缺点

  1. 优点
  • 便于增加和删除顶点
  • 便于统计边的数目
  • 空间效率高
  1. 缺点
  • 不便于判断顶点之间是否有边
  • 不便于计算有向图各个顶点的度。对于无向图来说，顶点的度就是每个顶点链接的结点个数。在有向图的邻接表中，每个顶点的结点数只能表示该顶点的出度，求入度比较困难。若有向图采用逆邻接表表示，则与邻接表表示相反，求顶点的入度容易，出度难。

那么有没有一种链表是便于求得顶点的入度和出度呢？下面将要介绍的十字链表就符合上述情况

6.4.3 十字链表（有向图）

十字链表（Orthogonal List）是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。

为了方便理解，我们再描述一下邻接表与逆邻接表。对于有向图中的弧 < v i , v j > <v_{i},v_{j}> <vi​,vj​>，在邻接表中，我们是由顶点结点 v i v_{i} vi​指向顶点的邻接点 v j v_{j} vj​，在逆邻接表中，则是由顶点的邻接点 v j v_{j} vj​指向顶点 v i v_{i} vi​，相当于就是邻接表是用出度表示，逆邻接表用入度表示。

如果要将两个表结合起来，因为在邻接表和逆邻接表中都只有一个链域，所以在十字链表中的顶点结点要有两个域（firstin，firstout）分别指向以该顶点为弧头或弧尾的第一个弧结点。

而对于边结点（在前面的表示法中相当于邻接点的结点），在十字链表中也的的确确变成了“边”的结点，因此，它需要两个域（tailvex，headvex）分别指示弧头和弧尾着两个顶点在图中的位置。

由上述可知，边结点也应有两个链域（hlink，tlink）分别指向弧头相同的下一条边和弧尾相同的下一条边。边结点还应有一个信息域（info）用于存储该弧的相关信息（也可不用）。

于是，我们可以得到十字链表的存储结构表示如下：

#define MAX_VEXTEX_NUM 20
typedef struct ArcBox
{
	int tailvex,headvex;
	struct ArcBox *tlink,*hlink;
	InfoType *info;
}ArcBox;
typedef struct VexNode
{
	VertexType data;
	ArcBox *firstin,*firstout;
}VexNode;
typedef struct
{
	VexNode xlist[MAX_VEXTEX_NUM];
	int vexnum,arcnum;
}OLGraph;

为了方便理解，下面给出一个十字链表的示例图：
在这里插入图片描述

6.4.4 邻接多重表（无向图）

邻接多重表（Adjacency Multilist）是无向图的另一种链式存储结构。因为在邻接表中，每一条边有两个结点，分布在不同的链表中，我们在对边进行操作时就需要找到这两个结点，这确实比较麻烦。进而就引入了邻接多重表来解决这种麻烦。

邻接多重表的结构和十字链表的结构相似。在邻接多重表中，每一条边用一个结点表示。由此，既然一条边由个结点表示，那么该结点一定有两个域来指示组成这个边的两个顶点在图中的位置（ivex，jvex），同时也有两个链域分别指示下一条依附于两个顶点的边（ilink，jlink）。当然，这里仍然有一个info域来指示这条边的信息。

除此之外，在邻接多重表的边结点中还增加了一个标志域（mark），用来标记改边是否被搜索过。

每一个顶点也仍然用一个结点表示（结构体数组）。该结点有两个域，data域存储该顶点的信息，firstedge域指示第一条依附于该顶点的边。

由此，我们可以构建邻接多重表的存储结构：

#define MAX_VERTEX_NUM 20
typedef enum{unvisited,visited} VisitIf;
typedef struct EBox					//边结点
{
	VisitIf mark;
	int ivex,jvex;
	struct EBox *ilink,*jlink;
	InfoType *info;
}EBox;
typedef struct VexBox
{
	VertexType data;
	EBox *firstedge;
}VexBox;
typedef struct
{
	VexBox adjmulist[MAX_VERTEX_NUM];
	int vexnum,edgenum;
}AMLGraph;

总结

对于图的存储结构，一共有四种方式：邻接矩阵，邻接表，十字链表，邻接多重表。在这四种方式中，基本上都有“邻接”二字（十字链表也有这个意思）。所谓邻接，就是由一个顶点表邻接边表，其中顶点表有不同的形式，边表也有不同的形式。

对于邻接矩阵来说，顶点表是由一个一维数组组成，边表是由一个二维数组组成（矩阵）。这样，邻接矩阵的表示是相当简单的（不涉及指针），而且直观上来看这个结构，也很清晰明了，但是它实际上的空间复杂度是相当高的，对于边的操作（查找删除等），也极为不方便，需要扫描所有元素才能完成，所以对于邻接矩阵，适用于少量顶点有大量边组成的图的情况。

对于邻接表，则是较针对于无向图的（对于有向图也可以，不过出度入度很难表示），它的表示法不同于邻接矩阵（对于一个图有唯一表示），它的表示不唯一。相对于邻接矩阵，它对边进行的操作就相对简单，因为有边才生成结点，无边就不生成结点，空间复杂度也相对较低。但是不能直观地判断两个顶点间是否有边，这点是不如邻接矩阵的。邻接矩阵呢则是应该适用于顶点和边都不太多的情况下。
而邻接多重表又是邻接表的改进。这是因为邻接表的一条边由两个结点组成，而邻接多重表的边则是由一个结点组成，时间和空间的复杂度都相对较低。

对于十字链表，则是专门针对有向图的，这是为了更方便的知道有向图中每个顶点的出度和入度。