数据结构考研第六章——图（内含动图）

大纲要求：图的相关算法相对较多，通常只要求掌握其基本思想和实现步骤，而算法的具体实现不是重点。

一、图的基本概念

1. 图的概念：图G由顶点集V和边集E组成的，记为G=（V，E）
2. 有向图：若E是有向边（也称为弧），则G为有向图
   G=（V，E），其中V={1，2，3}，E={<1,2>，<2,3>，<2,1>}
3. 无向图：若E是无向边（也称为边），则G为无向图
   G=（V，E），其中V={1，2，3}，E={（1,2），（2,3），（2,1）}
4. 简单图：不存在重复的边，不存在顶点到自身的边（数据结构仅讨论简单图）
5. 多重图：存在重复的边，存在顶点到自身的边
6. 完全图：对于无向图来说有n(n-1)/2条边，对于有向图来说有n(n-1)条边
7. 连通：对于无向图来说，若顶点v到顶点w有路径存在，则称v和w是连通的
   连通图：对于无向图来说，若任意两个顶点都连通，则称为连通图。否则称为非连通图。
   连通分量：对于无向图来说，无向图中的极大连通子图称为连通分量
8. 强连通：对于有向图来说，若顶点v到顶点w有路径存在，则称v和w是强连通的
   强连通图：对于有向图来说，若任意两个顶点都连通，则称为强连通图。否则称为非强连通图。
   强连通分量：对于有向图来说，有向图中的极大强连通子图称为强连通分量
9. 生成树：包含图中全部顶点的一个极小连通子图。
   极小连通子图是既要保持图的连通又要使得边数最少的子图。极大连通子图要求包含所有的边
10. 度TD、出度ID、入度OD
    顶点的度等于入度与出度之和
    有向图的全部顶点的入度之和和出度之和相等，无向图没有出度和入度之分。
    无向图的全部顶点的度的和等于边数的2倍，有向图也是。
11. 网：带有权值的边的图称为网
12. 稠密图：边数满足E>=VlogV的图。
    稀疏图：边数满足E
13. 路径：顶点v到顶点w之间的顶点序列
    路径长度：路径边上的数目
    回路：第一个顶点和最后一个顶点相同的路径
14. 距离：两个顶点之间最短路径
15. 有向树：一个顶点（作为根）入度为0，其余顶点（非根）入度为1的有向图

二、图的存储结构

核心思想：紧扣 “图由点和边组成” 这一基本概念思考四种存储结构

1. 邻接矩阵法

【数据结构】

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{
	VertexType Vex[MaxVertexNum];					//顶点表
	EdgeType Edge[MaxVertexNum][MaxVertexNum];		//边表，邻接矩阵形式
	int vexNum;			//顶点数
	int arcnum;			//边数
}
1
2
3
4
5
6
7
8
9

【存储特点】

1. 当邻接矩阵的元素仅表示相应边是否存在时，EdgeType可采用值为0和1;
   当邻接矩阵的元素表示相应边的权值时，EdgeType需要表示具体权值；
2. 无向图的邻接矩阵是对称矩阵，对规模大的邻接矩阵可采用压缩存储；
   邻接矩阵表示法的空间复杂度为O($n^2$)，其中n为图的顶点数
3. 适用范围：稠密图适合使用邻接矩阵的存储表示

【相关计算】

1. 对于无向图，邻接矩阵的第i行(列)非零元素(非∞元素)的个数正好是顶点i的度TD
   对于有向图，邻接矩阵的第i行非零元素(非∞元素)的个数正好是顶点i的出度OD，邻接矩阵的第i列非零元素(非∞元素)的个数正好是顶点i的入度TD
2. 设置图G的邻接矩阵为A，$A^n$的元素$A^n[i][j]$等于由顶点i到顶点j的长度为n的路径的数目

2. 邻接表法

【数据结构】

#define MaxVertexNum 100
typedef struct ArcNode{		//边表结点
	int adjvex;				//该弧所指向的顶点的位置
	struct ArcNode *next;	//指向下一条弧的指针
}ArcNode;
typedef struct VNode{		//顶点表结点
	VertexType data;		//顶点信息
	ArcNode *first;			//顶点的第一条弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
	AdList vertices;			//邻接表
	int vexnum,arcnum;			//图的顶点数和边数
}ALGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13

【存储特点】

1. 适用范围：稀疏图适合使用邻接表法的存储表示
2. 邻接表法的空间复杂度：无向图的空间复杂度为O(V+2E)，有向图的空间复杂度为O(V+E)
3. 在邻接表中，给定一顶点，能很容易找出它的所有邻边，因为只需要读取它的邻接表，时间复杂度远小于O(n);而在邻接矩阵则需要扫描一行，时间复杂度为O(n).
   在邻接表中，确认两个顶点是否存在边，则需要在边链表上依次查找，时间复杂度为O(n);而在邻接矩阵则可以通过A[i][j]元素查到，时间复杂度为O(1).
4. 在有向图的邻接链表中，求一个顶点的出度只需要计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。后者可以采用逆邻接表来加速求解。
5. 图的邻接表表示并不唯一

3. 十字链表法（只用于有向图）

【数据结构】 这种存储结构要从边的特点出发定义

1. 弧的两个端点：弧头和弧尾
2. 弧的分类：弧头相同的弧链接在一起，弧尾相同的弧链接在一起。
   
   

【存储特点】

1. 在十字链表中，既容易找到V为尾的弧，又容易找到V为头的弧，因而容易求得顶点得出度和入度。

4. 邻接多重表（只用于无向图）

【数据结构】
【数据结构】 这种存储结构要从边的特点出发定义

1. 边的两个端点：弧头和弧尾
2. 边的分类：依附在相同顶点的边链接在一起。
   
   

三、图的基本操作

基本操作 ：图的基本操作是独立于图的存储结构的，而对于不同的存储方式，操作算法的具体实现会有着不同的性能。在设计具体算法的实现时，应考虑采用何种存储方式的算法效率会更高。

1. Adjacent(G,x,y)：判断图G是否存在边或(x,y)
2. Neighbors(G,x)：列出图G中与结点x邻接的边
3. InsertVertex(G,x)：在图G中插入顶点x
4. DeleteVertex(G,x)：在图G中删除顶点x
5. AddEdge(G,x,y)：若无向边(x,y)或者有向边不存在，则添加
6. RemoveEdge(G,x,y)：若无向边(x,y)或者有向边存在，则删除
7. FirstNeighbor(G,x)：求图G中第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1.
8. NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号。若没有则返回-1；
9. Get_edge_value(G,x,y)：获取权值
10. Set_edge_value(G,x,y)：设置权值

四、图的遍历算法

1. 广度优先搜索BFS

【算法思想】

1. 首先从未被访问的顶点v开始，接着由顶点v出发，依次访问v的各个未被访问过的邻接顶点w1，w2，w3…，然后依次访问w1，w2，w3…未被访问过的邻接结点，直到没有邻接结点为止。
2. 如果图中尚有未被访问过的结点，则另选择一个未曾被访问过的顶点作为始点，重复上述过程。

【代码实现】 （辅助队列+非递归算法）

bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G){
	for(int i=0;i<G.vexnum;++i){
		visited[i]=FALSE;
	}
	InitQueue(Q);
	for(i=0;i<G.vexnum;++i)
		if(!visited[i])
			BFS(G,i)
}
void BFS(Graph G,int v){
	visit(v);
	visited[v]=TRUE;
	Enqueue(Q,v);
	while(!isEmpty(Q)){
		DeQueue(Q,V);
		for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v)){//如果为空，会返回-1
			if(!visited[w]){
				visit(w);
				visited(w)=TRUE;
				EnQueue(Q,w);
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

【具体实例】

【算法分析】

1. 空间复杂度：最坏的情况下空间复杂度为O(V)
2. 时间复杂度：邻接表时间复杂度为O(V+E)=顶点访问时间O(V)+边访问时间O(E)，邻接矩阵时间复杂度为O($V^2$)

【BFS算法求解单源最短路径问题】 (注意与Dijkstra算法的区别)

void BFS_MIN_Distance()
{
	for(i=0;i<G.vexnum;++i) d[i]=∞；
	visited[u]=TRUE;
	d[u]=0;
	EnQueue(Q,u);
	while(!IsEmpty(Q)){
		DeQueue(Q,u);
		for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
			if(!visited[w]){
				visited[w]=TRUE;
				d[w]=d[u]+1;			//整个算法的精髓
				EnQueue(Q,w);
			}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

【广度优先生成树】

1. 在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树
2. 由于邻接矩阵表示唯一，所以生成树也是唯一的
3. 由于邻接表存储表示不唯一，所以生成树也是不唯一的

2. 深度优先搜索

【算法思想】

1. 首先访问图中某一起始顶点v，然后从v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点。
2. 若还有尚未被访问的顶点，则从该顶点开始继续上述搜索过程。

【代码实现】

bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G){
	for(int i=0;i<G.vexnum;++i){
		visited[i]=FALSE;
	}
	for(i=0;i<G.vexnum;++i)
		if(!visited[i])
			BFS(G,i)
}

void DFS(Graph G,int v){
	visit(v);
	visited[v]=TRUE;
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
		if(!visited[w]) DFS(G,w)		//精髓：直接选用了新结点来寻找邻接结点，这就成了深度遍历了
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

【具体实例】

【算法分析】

1. 空间复杂度：使用了递归工作栈，故空间复杂度为O(V)
2. 时间复杂度：邻接表时间复杂度为O(V+E)=顶点访问时间O(V)+边访问时间O(E)，邻接矩阵时间复杂度为O($V^2$)

【深度优先生成树】

1. 在深度遍历的过程中，我们可以得到一棵遍历树，称为深度优先生成树
2. 由于邻接矩阵表示唯一，所以生成树也是唯一的
3. 由于邻接表存储表示不唯一，所以生成树也是不唯一的

3. 图的遍历

1. 对于无向图来说，两个函数调用BFS(G,i)和DFS(G,i)的次数等于该图的连通分量数。
2. 对于有向图来说，两个函数调用BFS(G,i)和DFS(G,i)的次数等于该图的强连通分量数。

五、图的应用

1. 最小生成树

【概念特性】

1. 概念：权值之和最小的生成树
2. 特性：最小生成树不是唯一的，但是最小生成树的边的权值之和是唯一的。

【Prim算法】

1. 算法思想：初始时从图中任选一个顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1.
2. 算法分析：时间复杂度为O($V^2$)，因为n个顶点，每个顶点有n-1条边比较大小。
3. 适用范围：边稠密的图
4. 具体实例

【Kruskal算法】

1. 算法思想：初始时为只有n个顶点而无边的非连通图T={V，{}}，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上（即不形成环路），则将此边加入T，否则舍弃此边而选择下一条权值最小的边。直至T中所有顶点都在一个连通分量上。
2. 算法分析：时间复杂度为O($ElogE$)
3. 适用范围：边稀疏的图
4. 具体实例
   

2. 最短路径

【Dijkstra算法：实现单源最短路径问题】 （带正权无向图、带正权有向图）

1. 算法介绍：Dijkstra算法应用了贪心算法思想，是目前公认的最好的求解最短路径的方法。算法解决的是有带权无向图、带权有向图中单个源点到其他顶点的最短路径问题。
2. 辅助数组
   dist[]：记录从源点$v_0$到其他各顶点当前的最短路径长度。
   path[]：path[i]表示源点到顶点i之间的最短路径的前驱结点。
3. 算法思想：
   设置一个集合S记录已求得的最短路径的顶点，初始时把源点$v_0$放入S；
   集合S每并入一个新顶点$v_i$，都要修改源点$v_0$到集合V-S中顶点当前的最短路径长度值；
4. 算法特点：使用邻接矩阵的时间复杂度为O($V^2$)，并且不适用于权值带负数的情况
5. 具体实例
   

【Floyd算法：各顶点之间最短路径问题】（带正负权无向图、带正负权有向图）

【算法思想】

【代码实现】

//核心代码
for(int k=0;k<n;k++)						//中转结点
	for(int i=0;i<n;i++)					//起始结点
		for(int j=0;j<n;j++)				//终点
			if(d[i][j]>d[i][k]+d[k][j])
				d[i][j]=>d[i][k]+d[k][j];
1
2
3
4
5
6

【具体实例】

【算法分析】

1. 时间复杂度：根据核心代码不难得出时间复杂度为O($V^3$).
2. 使用范围：带正负权无向图、带正负权有向图，但是不允许含带负权值的边组成的回路。

3. 有向无环图DAG描述表达式 （描述含有公共子式的表达式的有效工具）

【使用真题演示】

4. 拓扑排序

【基本概念】

1. AOV网：带权有向无环图 表示活动的网络，记为AOV网
2. 活动：每个顶点代表一个活动
3. 事件：每条边代表一个事件

【算法思想】

1. 从AOV网中选择一个没有前驱的顶点并输出
2. 从网中删除该顶点和所有以它为起点的有向边
3. 重复步骤1和步骤2直到当前AOV网为空

【代码实现】

bool TopoLogicalSort(Graph G){
	InitStack(S);
	for(int i=0;i<n;i++){
		if(indegree[i]=0)
			Push(S,i)
	}
	int count=0;		//用来计数是否全部结点拓扑完毕
	while(!IsEmpty(S)){
		Pop(S,i);
		print[count++]=i;
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){	//这个for循环是核心
			v=p->adjvex;
			if(!(--indegree[v])) Push(S,v);
		}
	}
	if(count<G.vexnum) return false;			//排序失败，有向图中有回路
	else return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

【算法分析】

1. 时间复杂度：邻接表时间复杂度为O(V+E)，邻接矩阵时间复杂度为O($V^2$)
2. 唯一性：若顶点有多个后继，则拓扑排序算法不唯一；若顶点有多个后继，则拓扑排序算法唯一

5. 关键路径 （完成整个工程的最短时间就是关键路径的长度）

【基本概念】

1. 源点：入度为0的顶点称为源点
2. 汇点：出度为0的顶点称为汇点
3. 关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径
4. 事件vk的最早发生时间ve(k)：ve(k)=Max{ve(j)+Weight($v_j$,$v_k$)}，从源点v1到顶点vk的最长路径长度
5. 事件vk的最迟发生时间vl(k)：vl(k)=Min{vl(j)-Weight($v_k$,$v_j$)}，即选择最大的一段后退距离
6. 活动ai的最早发生时间e(i)：若边<$v_k$,$v_j$>表示活动$a_i$，则有e(i)=ve(k);
7. 活动ai的最迟发生时间l(i)：若边<$v_k$,$v_j$>表示活动$a_i$，则有l(i)=vl(j)-Weight($v_k$,$v_j$);
8. 一个活动ai的最迟开始时间l(i)和最早开始时间e(i)的差额：d(i)=l(i)-e(i)

【算法思想】

1. 从源点出发，令ve(源点)=0，按拓扑排序求其余顶点的最早发生时间ve()；
2. 从汇点出发，令vl(汇点)=ve(汇点)，按逆拓扑排序求其余顶点的最迟发生时间vl()；
3. 根据各顶点的ve()值求所有弧的最早开始时间e()；
4. 根据个顶点的vl()值求所有弧的最迟开始时间l()；
5. 求AOE网中所有差额d()，找出所有d()=0的活动构成关键路径

【具体实例】
关键路径为（$v_1$,$v_3$,$v_4$,$v_6$）

【特点】

1. 关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。