图

数据结构与算法 / 数据结构
Word count: 4.7k   |   Reading time≈ 17 min

图

(一)图的定义和基本术语

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

无向图：每条边都是无方向的
有向图：每条边都是有方向的
有向图、无向图.png

完全图：任意两个点都有一条边相连
    无向完全图：n个定点，n(n-1)/2条边
    有向完全图：n个定点，**n(n-1)**条边
完全图.png

稀疏图：有很少边/弧的图(e < n㏒n)
稠密图：有较多边/弧的图

网：边/弧带权的图
邻接：有边/弧相连的两个顶点之间的关系
    存在(vi,vj),则称vi和vj互为邻接点；(无向图)
    存在<vi,vj>,则称vi邻接到vj，vj邻接于vi。<有向图>
**关联(依附)*：边/弧与顶点*之间的关系
    存在(vi,vj)/<vi,vj>，则称该边/弧关联于vi和vj

顶点的度：与该顶点相关联的边的数目
    在有向图中，定点的度=该顶点的入度+出度
        顶点v的入度：以v为终点的有向边的条数，记作ID(v)
        顶点v的出度：以v为始点的有向边的条数，记作OD(v)
顶点的度例子.png

路径：接续的边构成的顶点序列
路径的长度：路径上边/弧的数目/权值之和
回路(环)：第一个顶点和最后一个顶点相同的路径
简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径
**简单回路(简单环)**：除路径起点和终点相同外，其余其余顶点均不相同
简单路径_回路.png

**连通图(强连通图)**：对任何两个顶点，都存在路径
连通图.png

权与网：
图中边/弧所具有的相关数称为权
带权的图称为网

子图：图包含所有子图的顶点和路径

连通分量(强连通分量)：
无向图G的极大连通子图称为连通分量
极大连通子图：该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不再连通
极小连通子图：该子图是G的连通子图，在该子图中删除任意一条边，子图不再连通
连通分量.png
强连通分量.png

生成树：包含无向图G的所有顶点的极小连通子图(去掉一条边则非连通)
     所有顶点均由边连接在一起，但不存在回路
     一个图可以有许多颗不同的生成树
     生成树的顶点个数与图的顶点个数相同
     n 个顶点的连通图的生成树有 n - 1条边
     生成树中任意两个顶点之间的路径是唯一的
生成森林：对非连通图，由各个连通分量的生成数的集合
极小连通子图_生成树.png
一个图可对应多个生成树.png

(二)图的存储结构

1.邻接矩阵(数组) 表示法

建立一个顶点表(记录各个顶点表)和一个邻接矩阵(表示各个顶点之间的关系)
设图 A = (V,E) 有 n 个顶点，则
顶点表Vexs[n]
顶点表.png
图的邻接矩阵是一个二维数组A.arcs[n][n]
有关系则记为 1 ，否则为 0

(1)无向图的邻接矩阵表示法：

特点：
无向图的邻接矩阵是对称的
顶点 i 的度 = 第 i 行(列)中 1 的个数
完全图的邻接矩阵中，对角元素为 0 ，其余 1
无向图的邻接矩阵表示法.png

(2)有向图的邻接矩阵表示法：

特点：
有向图的邻接矩阵可能是不对称的
顶点的度 = 第 i 行元素之和(出度) + 第 i 列元素之和(入度)
有向图的邻接矩阵表示法.png

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

有：权值 无：∞
网的邻接矩阵表示法.png

邻接矩阵的建立

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

1
2
3
4
5
6
7
8
9
10
#define MaxInt 32767 //表示极大值∞
#define MVNum 100  //最大顶点数
typedef char VerTexType;  //设置顶点的数据类型为字符型
typedef int ArcType;  //假设边的权值类型为整型

typedef struct{
	VerTexType vex[MVNum]; //顶点表
	ArcType arcs[MVNum][MVNum]; //邻接矩阵
	int vexnum,arcnum; //图的当前点数和边数
}AMGraph; //Adjacency Matrix Graph

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

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
26
27
28
Status CreateUDN(AMGraph &G){
	//输入总顶点数、总边数
	cin >> G.vexnum >> G.arcnum; 
	//依次输入点的信息
	for(i = 0; i < G.vexnum; ++i){
		cin >> G.vexs[i]; 
	}
	//初始化邻接矩阵
	for(i = 0; i < G.vexnum; ++i){
		for(j = 0; j < G.vexnum; ++j){
			G.arcs[i][j] = MaxNum; //边的权值均置为极大值
		}
	}


	//构造邻接矩阵
	for(k = 0; k < G.arcnum; ++k){
		//输入一条边所依附的顶点及边的权值
		cin >> v1 >> v2 >> w;
		//确定v1和v2在G中的位置
		i = LocateVex(G,v1);
		j = LocateVex(G,v2);
		//设置权值
		G.arcs[i][j] = w;
		G.arcs[j][i] = G.arcs[i][j];
	}
	return OK;
}

在图中查找顶点

1
2
3
4
5
6
7
int LocateVex(AMGraph G,VertexType u){
	int i;
	for(i = 0; i < G.vexnum; ++i){
		if(u == G.vexs[i]) return i;
	}
	return -1;
}

其他情况建立网or图.png

邻接矩阵 ———— 好处：
直观、简单、好理解
方便检查任意一对顶点间是否存在边
方便找任一顶点的所有邻接点
方便计算任一顶点的“度”
邻接矩阵 ———— 不好：
不利于增加和删除顶点
浪费空间(存稀疏图)
浪费时间(统计稀疏图中一共有多少条边)

2.邻接表(链式) 表示法

邻接表示法_链式_.png
顶点：按编号顺序将顶点数据存储在一维数组中；
关联同一顶点的边(以顶点为尾的弧)：用线性链表存储

头结点：
data:放顶点的数据本身
firstarc:存储第一个边的边结点的地址
表结点：
邻接点域：存放与vi邻接的顶点在表头数组中的位置
链域：指示下一条边/弧

(1)无向图的邻接表

无向图的邻接表.png
特点：

  1. 邻接表不唯一(表节点次序可交换)。
  2. 若无向图中有 n 个顶点、 e 条边
        则其邻接表需要n 个头结点和2e个表结点。适宜存储稀疏图。
  3. 无向图中顶点 vi 的度为第 i 个单链表中结点数。

(2)有向图的邻接表

有向图的邻接表__逆邻接表.png

邻接表：找出度易，找入度难
逆邻接表：找入度易，找出度难
题目：已知某网的邻接表，画出该网络

建立邻接表的算法

表头顶点的结点结构

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

弧(边)的结点结构

1
2
3
4
5
6
7
#define MVNum 100 //最大顶点数
//边结点
typedef struct ArcNode{
	int adjvex;  //该边所指向的顶点的位置
	struct ArcNode * nextarc;  //指向下一条边的指针
	OtherInfo info;  //和边相关的信息
}ArcNode;

图的结构定义

1
2
3
4
typedef struct{
	AdjList vertices;  //vertex复数
	int vexnum,arcnum; //图的当前顶点数和弧数
}ALGraph;

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

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
26
Status CreateUDG(ALGraph &G){
	cin >> G.vexnum >> G.arcnum;  //输入总顶点数、总边数
	//输入各点，构造表头结点表
	for(i = 0; i < G.vexnum; ++i){
		cin >> G.vertices[i].data;  //输入顶点值
		G.vertices[i].firstarc = NULL;  //初始化表头结点的指针域
	}

	//输入各边，构造邻接表
	for(k = 0; k < G.arcnum; ++k){
		cin >> v1 >> v2;  //输入一条边依附的两个顶点
		i = LocateVex(G,v1);
		j = LocateVex(G,v2);
		p1 = new ArcNode;   //生成一个新的边结点*p1
		p1 -> adjvex = j;   //邻接点序号为j
		//将新结点*p1插入顶点vi的边表头部
		p1 -> nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;

		p2 = new ArcNode;
		p2 -> adjvex = i;
		p2 -> nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
	return OK;
}

邻接表的特点：

  1. 方便找任一顶点的所有“邻接点”
  2. 节约稀疏图的空间
  3. 方便计算无向图的“度”
  4. 不方便检查任意一对顶点间是否存在边

邻接矩阵 && 邻接表 表示法的关系：
1. 联系：
邻接表中每一个链表对应于邻接矩阵中的一行
链表中结点个数 = 一行中非零元素的个数
2. 区别：
①邻接矩阵是唯一的，邻接表不唯一
②邻接矩阵的空间复杂度为O(n²)，而邻接表为O(n + e)或O(n + 2e)
3. 用途：
邻接矩阵多用于稠密图，而邻接表多用于稀疏图

十字链表__邻接多重表解决的问题.png

3.十字链表 表示法

有向图的另一种链式存储结构(将有向图的邻接表和逆邻接表结合起来)
有向图中的一条弧 -> 弧结点
有向图中的顶点 -> 顶点结点
十字链表.png

4.邻接多重表 表示法

邻接多重表.png

(三)图的遍历

遍历定义：
从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫图的遍历，它是图的基本运算。
遍历实质：
找每个顶点的邻接点的过程。

图的特点：
可能存在回路，可能又回到了曾经访问过的顶点。
解决思路：
设置辅助数组 visited[n]，用来标记每个被访问过的顶点。
初始状态 visited[i] = 0
顶点 i 被访问，改为 visited[i] = 1 ，阻止被多次访问

深度优先搜索(DFS)

(Depth_First Search)

从 起始顶点 v 出发，访问它的任一邻接顶点 w1
从 w1 出发，访问与 w1 邻接但还未被访问过的顶点 w2
…
直到到达所有邻接顶点都被访问过的顶点 u 为止
接着，退回一步，看看还有没有其他没有被访问的邻接顶点
有，继续访问
无，再退回，重复上述过程

连通图的深度优先遍历类似于 树的先根遍历

连通图的DFS遍历
深度优先搜索案例.png

非连通图的DFS遍历
非连通图的深度优先搜索遍历.png

DFS算法的实现

邻接矩阵-无向图-深度遍历.png

邻接矩阵-深度优先

1
2
3
4
5
6
7
8
9
void DFS(AMGraph G,int v){ // v 为起始点
	cout << v;
	visited[v] = true; //访问
	for(w = 0; w < G.vexnum; w++){
		if(G.arc[v][w] != 0 && (!visited[w])){
			DFS(G,w); // w 是 v 的邻接点，如果 w 未被访问，则递归调用 DFS
		}
	}
}

广度优先搜索(BFS)

(Breadth_First Search)
方法：从图的，某一结点出发，首先依次访问该结点的所有邻接点，
再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点
重复此过程，直至所有顶点均被访问完为止

连通图的 BFS遍历
广度优先搜索遍历的案例.png

非连通图的 BFS遍历
非连通图的广度遍历.png

邻接表-广度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BFS(Graph G,int v){
	cout << v;  //访问第 v 个顶点
	visited[v] = true;

	InitQueue(Q);
	EnQueue(Q,v);
	while(!QueueEmpty(Q)){
		DeQueue(Q,u);
		for(w = FirstAdjVex(G,u); w >= 0; w = NextAdjVex(G,u,w)){
			if(!visited[w]){ // w 为 u 的尚未访问过的邻接顶点
				cout << w;
				visited[w] = true;
				EnQueue(Q,w);
			}
		}
	}
}

(四)图的应用

(1)最小生成树

最小生成树的典型用途：在n个城市间建立通信网，如何选择n-1条线路，使总费用最低

生成树：包含无向图G的所有顶点的极小连通子图(所有顶点均由边连接在一起，但不存在回路)
最小生成树：给定一个无向网络，在该网中的所有生成树中，使得各边权值之和最小的那颗生成树称为该网的最小生成树，也叫最小代价生成树。

MST(Minimum Spanning Tree)性质:
MST性质.png
MST性质的解释：
在生成树的构造过程中，图中 n 个顶点分属两个集合：
     已落在生成树的顶点集：U
     尚未落在生成树上的顶点集：V-U
接下来则应在所有连通 U 中顶点和 V-U 中顶点的边中选取权值最小的边
MST性质的解释.png

构造最小生成树方法

1.普里姆(Prim)算法

普里姆算法思想.png

2.克鲁斯卡尔(Kruskal)算法

克鲁斯卡尔算法.png
两种算法比较
两种算法比较.png

(2)最短路径

典型用途：交通网络(用有向网来表示)问题——求最短路径

最短路径和最小生成树不同，路径上不一定包含 n 个顶点，也不一定包含 n - 1 条边

两种常见的最短路径问题

1.单源最短路径 —— Dijkstra(迪杰斯特拉)算法

按路径长度递增次序产生最短路径
最短路径第二类问题.png
图中某一个顶点到其他顶点的最短路径
①初始化：先找出从源点 v0 到各终点 vk 的直达路径(v0,vk),即通过一条弧直达的路径
②选择：从这些路径中找出一条长度最短的路径(v0,u)
③更新：然后对其余各条路径进行适当调整
     若图中存在弧 (u,vk) ,且 (v0,u) + (u,vk) = (v0,vk)
     则以路径 (v0,u,vk) 替代 (v0,vk)
在调整后的各条路径中，再找长度最短的路径，依此类推
时间复杂度：O(n²)

Dijkstra算法步骤
Dijkstra算法步骤.png

2.所有顶点间的最短路径 —— Floyd(弗洛伊德)算法

最短路径第一类问题.png
求 所有顶点间的最短路径 的方法：
方法一：每次以一个顶点为源点，重复执行 Dijkstra算法 n 次,时间复杂度为 O(n³)
方法二：弗洛伊德(Floyd)算法

弗洛伊德算法思想：
逐个顶点试探
从 vi 到 vj 的所有可能存在的路径中
选出一条
Floyd算法例子.png

拓扑排序和关键路径都是针对有向无环图来说的
有向无环图：无环的有向图，简称 DAG图(Directed Acycline Graph)
有向无环图示例.png
有向无环图常用来描述一个工程或系统的进行过程(通常把计划、施工、生产、程序流程等当成是一个工程)
一个工程可以分为若干个子工程，只要完成了这些子工程(活动)就可以导致整个工程的完成。

如何表示“活动”(用一个有向图表示一个工程的各子工程及其相互制约的关系):

AOV网(拓扑排序)：以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称 AOV网(Activity On Vertex network)
AOE网(关键路径)：以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称 AOE网(Activity On Edge)

(3)拓扑排序

(针对有向无环图 )

排课表：有先修课

拓扑排序：在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若 AOV网中有弧 <i，j>存在，则在这个序列中，i一定排在j的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。

拓扑排序的方法：
在有向图中选一个没有前驱的顶点且输出之 从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止
拓扑排序示例.png

拓扑排序的一个重要应用：
检测 AOV网中是否存在环方法：
对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该 AOV网必定不存在环
AOV网中有环的情况.png

(4)关键路径

(针对有向无环图)

家庭晚宴活动、办公室装修(已知每项任务历时、前置任务是什么、几点开始，求最迟几点开始准备)

AOE网的表示
把工程计划表示为边表示活动的网络，即 AOE网用顶点表示事件，弧表示活动，弧的权表示活动持续时间。
事件表示在它之前的活动已经完成，在它之后的活动可以开始

AOE网的形成
关键路径示例(AOE网的形成).png

例:设一个工程有11项活动，9个事件
事件 v1 表示整个工程开始(源点: 入度为0的顶点)
事件 v9 表示整个工程结束(汇点: 出度为0的顶点)

对于AOE网，我们关心两个问题
(1)完成整项工程至少需要务少时间?
     关键路径
(2) 哪些活动是影响工程进度的关键?(缩短哪个工程的时间会使总时间减少)
     关键路径上的关键活动

关键路径 —— 路径长度最长的路径
路径长度 —— 路径上各活动持续时间之和。
关键活动 —— 关键路径上的活动，即 l(i) == e(i) (即 l(i) - e(i) == 0 ) 的活动 (最晚开始时间 - 最早开始时间)
     l(i) - e(i) —— 表示完成活动 ai 的时间余量。 例: (3) - e(3) = 90

如何确定关键路径，需要定义4个描述量：
确定关键路径的4个描述量.png

如何找到 l(i) == e(i) 的关键活动？
如何求最早and最晚.png

求关键路径步骤：
最早发生时间ve = 最大的和(从头往后算)
最迟发生时间vl = 最小的差(从汇点往回算)
     汇点的最迟发生时间与其最早发生时间相同
     前一个顶点的最晚发生时间 - 权值
活动最早开始时间e：查弧尾的最早发生时间
活动最迟开始时间l：查弧头的最迟发生时间 - 弧的权值(活动持续时间)
求关键路径步骤.png

  1. 若网中有几条关键路径，则需加快同时在几条关键路径上的关键活动
    如: a11、a10、a8、a7。
  2. 如果一个活动处于所有的关键路径上，那么提高这个活动的速度，就能缩短整个工程的完成时间。如: a1、a4
  3. 处于所有的关键路径上的活动完成时间不能缩短太多否则会使原来的关键路径变成不是关键路径。这时，必须重新寻找关键路径。如:a1由6天变成3天，就会改变关键路径
Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2023-2025 Annie
  • Visitors: | Views:

嘿嘿 请我吃小蛋糕吧~

支付宝
微信