数据结构-图的概念与存储结构（类C语言版）_图的逻辑结构

图的定义和术语

图：G = (V, E)
Graph = (Vertex, Edge)
V：顶点（数据元素）的有穷非空集合；
E：边的有穷集合。

无向图

每条边都是无方向的。

有向图

每条边都是有方向的。

完全图

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

稀疏图

有很少边或弧的图（e<nlogn）。

稠密图

有较多边或弧的图。

网

边/弧带权的图。

邻接

有边/弧相连的两个顶点之间的关系。
存在（v_i, v_j），则称v_i和v_j互为邻接点；
存在<v_i, v_j>，则称v_i邻接到v_j，v_j邻接于v_i。

关联（依附）

边/弧与顶点之间的关系。
存在(v_i, v_j) / <v_i, v_j>，则称该边/弧关联于v_i和v_j。

顶点的度

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

图中各顶点的度

有向树

问：当有向图中仅1个顶点的入度为0，其余结点的入度均为1，此时是何形状？
答：是树！而且是一棵有向树！

路径

连续的边构成的顶点序列。

路径长度

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

回路（环）

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

简单路径

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

简单回路（简单环）

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

连通图（强连通图）

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

权与网

图中边或弧所具有的相关树称为权。表明从一个顶点到另一个顶点的距离或耗费。
带权的图称为网。

子图

设有两个图G = (V, {E})、G1 = (V1, {E1})，若V1 ⊆ V，E1 ⊆ E，则称G1是G的子图。

连通分量（强连通分量）

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

有向图G的极大强连通子图称为G的强连通分量。
极大强连通子图的意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。

极小连通子图

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

生成树与生成森林

生成树：包含无向图G所有顶点的极小连通子图。
生成森林：对非连通图，由各个连通分量的生成树的集合。

图的定义与操作

图的存储结构

图的逻辑结构：多对多。

图没有顺序存储结构，但可以借助二维数组来表示元素间的关系。
数组表示法——邻接矩阵

链式存储结构：多重链表。

• 邻接表
• 邻接多重表
• 十字链表

在这里重点介绍：邻接矩阵（数组）表示法、邻接表（链式）表示法。

邻接矩阵表示法

建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。

设图A = (V, E) 有n个顶点，则顶点表Vexs[n]为：

图的邻接矩阵是一个二维数组A.arcs[n][n]，定义为：

无向图的邻接矩阵表示法

上图的邻接矩阵表示法如下：

分析1：无向图的邻接矩阵是对称的；
分析2：顶点 i 的度 = 第 i 行（列）中 1 的个数；
特别：完全图的邻接矩阵中，对角元素为0，其余 1 。

有向图的邻接矩阵表示法

上图的邻接矩阵表示法如下：

注：在有向图的邻接矩阵中，
第 i 行含义：以结点v_i为尾的弧（即出度边）；
第 i 列含义：以结点v_i为头的弧（即入度边）。

分析1：有向图的邻接矩阵可能是不对称的。
分析2：顶点的出度 = 第 i 行元素之和。
顶点的入度 = 第 i 列元素之和。
顶点的度 = 第 i 行元素之和 + 第 i 列元素之和。

网（即有权图）的邻接矩阵表示法

图的邻接矩阵存储表示

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

//-----图的邻接矩阵存储表示－－－－－
#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; 
1
2
3
4
5
6
7
8
9
10
11

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

算法思想：
（1）输入总顶点数和总边数。
（2）依次输入点的信息存入顶点表中。
（3）初始化邻接矩阵，使每个权值初始化为极大值。
（4）构造邻接矩阵。依次输入每条边依附的顶点和其权值，确定两个顶点在图中的位置之后，使相应边赋予相应的权值，同时使其对称边赋予相同的权值。

Status CreateUDN(AMGraph &G) 
{	//采用邻接矩阵表示法，创建无向网G
	cin>>G.vexnum>>G.arcnum; 			// 输入总顶点数，总边数
	for(i=O;i<G.vexnum;++i) 			// 依次输入点的信息
		cin>>G.vexs[i); 
	for(i=O;i<G.vexnum;++j)				// 初始化邻接矩阵，边的权值均置为极大值Maxint
		for(j=0; j<G.vexnum; ++j) 
			G.arcs[i][j]=Maxint;
	for(k=O;k<G.arcnum;++k) 			// 构造邻接矩阵
	{
		cin>>vl>>v2>>w; 				// 输入一条边依附的顶点及权值
		i=LocateVex(G,v1);j=LocateVex(G,v2); //确定v1和v2在G中的位置，即顶点数组的下标
		G.arcs[i][j]=w; 				//边<v1, v2>的权值置为w
		G.arcs[j][i]=G.arcs[i][j];		// 置<v1, v2>的对称边<v2, v1>的权值为w
	}									// for
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在图中查找顶点

int LocateVex(AMGraph G, VertexType u) {
	// 图G中查找顶点u，存在则返回顶点表中的下标；否则返回-1
	int i;
	for(i=0;i<G.vexnum;++i)
		if(u==G.vex[i]) return i;
	return -1;
}
1
2
3
4
5
6
7

邻接矩阵的优点

• 直观、简单、好理解。
• 方便检查任意一对顶点间是否存在边。
• 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）。
• 方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）。
  无向图：对应行（或列）非0元素的个数。
  有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”。

邻接矩阵的缺点

• 不便于增加和删除顶点。
• 浪费空间——存稀疏图（点很多而边很少）有大量无效元素。对稠密图（特别是完全图）还是很合算的。
• 浪费时间——统计稀疏图中一共有多少条 边。

邻接表表示法（链式）

无向图的邻接表表示法

顶点：按编号顺序将顶点数据存储在一维数组中。
关联同一顶点的边（以顶点为尾的弧）：用线性链表存储。

特点：

• 邻接表不唯一。
• 若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。
• 无向图中顶点v_i的度为第 i 个单链表中的结点数。

有向图的邻接表表示法

邻接表特点：

• 找出度易，找入度难。
• 顶点v_i的出度为第 i 个单链表中的结点个数。
• 顶点v_i的入度为整个单链表中邻接点域值是i - 1的结点个数。

逆邻接表特点：

• 找入度易，找出度难。
• 顶点v_i的入度为第 i 个单链表中的结点个数。
• 顶点v_i的出度为整个单链表中邻接点域值是 i - 1的结点个数。

练习

已知某网的邻接（出边）表，请画出该网络。

图的邻接表存储表示

// - - - - -图的邻接表存储表示－ －－－－
#define MVNum 100				// 最大顶点数
typedef struct ArcNode			// 边结点
{
	int adjvex; 				// 该边所指向的顶点的位置
	struct ArcNode * nextarc;   // 指向下一条边的指针
	Otherinfo info; 			// 和边相关的信息
}ArcNode; 

typedef struct VNode 			// 顶点信息
{
	VerTexType data; 
	ArcNode *firstarc; 			// 指向第一条依附该顶点的边的指针
) VNode,AdjList[MVNum]; 		// AdjList表示邻接表类型

typedef struct 					// 邻接表
{
	AdjList vertices; 
	int vexnum,arcnum; 			// 图的当前顶点数和边数
}ALGraph; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

采用邻接表表示法创建无向网

算法思想：
（1）输入总顶点数和总边数。
（2）建立顶点表。
依次输入点的信息存入顶点表中；
使每个表头节点的指针域初始化为NULL。
（3）创建邻接表。
依次输入每条边依附的两个顶点；
确定两个顶点的序号 i 和 j ，建立边结点；
将此边结点分别插入到v_i和v_j对应的两个边链表的头部。

Status CreateUDG(ALGraph &G) 
{	//采用邻接表表示法， 创建无向图 G
	cin>>G.vexnum>>G.arcnum; 	// 输入总顶点数， 总边数
	for(i=O;i<G.vexnum;++i) 	// 输入各点，构造表头结点表
	{
		cin>>G.vertices[i].data; // 输入顶点值
		G.vertices[i].firstarc=NULL;	// 初始化表头结点的指针域为NULL
	}							// for
	for(k=O;k<G.arcnum;++k) 	// 输入各边， 构造邻接表
	{
		cin>>v1>>v2; 			// 输入一条边依附的两个顶点
		i=LocateVex(G,v1); j=LocateVex(G,v2); // 确定vl和 v2在G中位置， 即顶点在G.vertices中的序号
		p1=new ArcNode;  		// 生成一个新的边结点*p1
		p1->adjvex=j;     		// 邻接点序号为j
		p1->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc= p1; //将新结点*p1插入顶点Vi的边表头部
		p2=new ArcNode; 		// 生成另一个对称的新的边结点*p2
		p2->adjvex=i; 			// 邻接点序号为i
		p2->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p2; //将新结点*p2插入顶点Vj的边表头部
	}							// for
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

邻接表特点

• 方便找任一顶点的所有“邻接点”。
• 节约稀疏图的空间。
  需要N个头指针 + 2E个结点（每个结点至少2个域）。
• 方便计算任一顶点的“度”？
  对无向图：是的。
  对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”。
• 不方便检查任意一对顶点间是否存在边。

邻接矩阵与邻接表表示法的关系

1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。
2.区别：
① 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。
② 邻接矩阵的空间复杂度为O(n²)，而邻接表的空间复杂度未O(n+e)。
3.用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图。

十字链表表示法——适用于有向图

十字链表（Orthogonal List）是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。
有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。

有向图的十字链表存储表示

// - - - - -有向图的十字链表存储表示－ －－－－
#define MAX_VERTEX_NUM 20 
typedef strut ArcBox 
{
	int tailvext,headvex;  			// 该弧的尾和头顶点的位置
	struct ArcBox *hlink, *tlink;   // 分别为弧头相同和弧尾相同的弧的链域
	InfoType *info; 				// 该弧相关信息的指针
) ArcBox; 

typedef struct VexNode 
{
	VertexType data; 
	ArcBox *firstin,*firstout; 		// 分别指向该顶点第一条人弧和出弧
}VexNode; 

typedef struct 
{
	VexNode xlist [MAX_VERTEX_NUM]; //表头向量
	int vexnnm, arcnum; 			//有向图的当前顶点数和弧数
}OLGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

邻接多重表（无向图的另一种链式存储结构）

回顾：
邻接表的优点：容易求得顶点和边的信息。
邻接表的缺点：某些操作不方便（如：删除一条边需找表示此边的两个结点）。
邻接表中，任何一条边，都会出现两次。

边结点

mark：标志域，标记此边是否被搜索过。
ivex、jvex：该边依附的两个顶点在表头数组中位置。
ilink：指向依附于ivex的下一条边。
jlink：指向依附于jvex的下一条边。

顶点结点

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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21