数据结构 - 图

数据结构第六章图的学习笔记。

正文部分

1、图的定义、存储结构

1.1、图的定义和术语

线性表可以是空表，树可以是空树，但图不可以空

即图的顶点不能空，但边可以空

图: G=(V,E)

V: 顶点(数据元素)的有穷非空集合

E: 边的有穷集合

简单图：1.不存在重复边 2.不存在顶点到自身的边

多重图：两点间的边多于一条，允许自己的边连接自己

1. 无向图: 每条边都是无方向的 (x,y)为边，且与(y,x)相同
2. 有向图: 每条边都是有方向的 <x,y>为边，且与<y,x>不同
3. 完全图: 任意两个点都有一条边相连
4. 稀疏图: 有很少边或弧的图(e<nlogn)
5. 稠密图: 有较多边或弧的图
6. 网: 边/弧带权的图
7. 邻接: 有边/弧相连的两个顶点之间的关系(圆括号是无向图，尖括号是有向图)

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

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

8. 关联(依附): 边/弧与顶点之间的关系

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

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

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

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

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

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

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

1.2、图的相关概念

点到点的距离，即最短路径。两点无连接，则这两点的距离为无穷

1. 路径: 接续的边构成的顶点序列
2. 路径长度: 路径上边或弧的数目/权值之和
3. 回路(环): 第一个顶点和最后一个顶点相同的路径
4. 简单路径: 除路径起点和终点可以相同外，其余顶点均不相同的路径
5. 简单回路(简单环): 除路径起点和终点相同外，其余顶点均不相同的路径
6. 连通图(强连通图): 在无(有)向图G={V,{E}}中，若对任何两个顶点v、u都存在从v、u的路径，则称G是连通图(强连通图)
7. 权与网: 图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费带权的图称为网
8. 子图: 设有两个图G=(V,{E})、G1=(V1,{E1}),若则称G1是G的子图

1.3、连通分量

1. 无向图G的极大连通子图称为G的连通分量
2. 极大连通子图:该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不再连通
3. 有向图G的极大强连通子图称为G的连强通分量
4. 极大强连通子图:该子图是G的强连通子图，将G的任何不在该子图中的顶点加入，子图不再强连通
5. 极小连通子图:该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通
6. 生成森林: 对非连通图，由各个连通分量的生成树的集合

1.4、图的存储结构

1.4.1、邻接矩阵法：

数组实现的顺序存储，空间复杂度高，不适合存储稀疏图 n^2

无向图的邻接矩阵：（右上和左下是对称重复的）

	A	B	C	D	E	F
A	0	1	1	1	0	0
B	1	0	0	0	1	1
C	1	0	0	0	1	0
D	1	0	0	0	0	1
E	0	1	1	0	0	0
F	0	1	0	1	0	0

无向图邻接矩阵特点：第i个结点的度 = 第i行（或第i列）的非零元素个数

---

有向图的邻接矩阵：

	A	B	C	D	E	F
A	0	1	0	0	0	0
B	0	0	0	0	0	0
C	1	0	0	0	0	0
D	1	0	0	0	0	0
E	0	1	1	0	0	0
F	0	1	0	1	0	0

有向图邻接矩阵特点：

• 第i个结点的出度 = 第i行（或第i列）的非零元素个数
• 第i个结点的入度 = 第i行（或第i列）的非零元素个数
• 第i个结点的度 = 第i行、第i列的非零元素个数之和

邻接矩阵性质：

两个矩阵A,B相乘，新的矩阵的C(1,4)位置的值为：A的第一行的第一个值*B的第四列的第一个值，有几个就+几个

$$C(1,4) = A(1,1)*B(1,4)+A(1,2)*B(2,4)+A(1,3)*B(3,4)+A(1,4)*B(4,4)$$

1.4.2、邻接表（顺序存储+链式存储）

计算图的入读和找图的入边不方便，只能遍历

指针顺序不唯一，适合存稀疏图

index	data	*指针1	*指针2	*指针3
0	A	–> 1	–> 2	–> 3
1	B	–> 0	–> 4	–> 5
2	C	–> 0	–> 4
3	D	–> 0	–> 5
4	E	–> 1	–> 2
5	F	–> 1	–> 3

拓展，逆邻接表：

存的是指向它的结点（前驱）

1.4.3、十字链表（有向图）（了解即可）：

数据域后的第一个橙色可以找到入边，第二个绿色找出边。这是相对于有向图来说的

1.4.4、邻接多重表（无向图）（了解即可）：

2、图的遍历过程及算法

2.1、广度优先遍历（BFS）

图的广度优先遍历就类似树的层次遍历

同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一

同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一

算法要点：

• 需要一个辅助队列
• 如何从一个结点找到与之邻接的其他顶点
• visited数组，防止重复访问
• 如何处理非连通图

复杂度：

• 空间复杂度：O(n) ---- 辅助队列
• 时间复杂度：
  • 访问结点的时间+访问所有边的时间
  • 邻接矩阵：O(|V|^2)
  • 邻接表：O(|V|+|E|)

广度优先生成树：

• 即为广度优先遍历确定的树
• 邻接表存储的图表示方式不唯一，遍历序列，生成树也不唯一
• 遍历非连通图可得广度优先生成森林

伪代码描述广度优先遍历：

/* 伪代码 */
/* 访问标记数组 */
bool visited[MAX_VERTEX_NUM];

/* 对图G进行广度优先遍历 */
void BFSTraverse(Graph G)//主要是处理连通图多的情况
{
	for (int i = 0; i < G.vexnum; ++i)
	{
		visited[i] = FALSE;//访问标记数组初始化
	}
	InitQueue(Q); //初始化辅助队列
	for (int i = 0; i < G.vexnum; ++i)//从0号顶点开始遍历
	{
		if (!visited[i])//对每个连通分量调用一次BFS
		{
			BFS(G, i);//vi未访问过，从Vi开始BFS
		}
	}
}
/* 广度优先遍历 */
void BFS(Graph G, int v) //从顶点v出发，广度优先遍历图G
{
	visit(v); //访问初始顶点v
	visited[v] = TRUE;//对v做已访问标记
	Enqueue(Q, v);//顶点v入队列Q
	while (!isEmpty(Q))
	{
		DeQueue(Q, v);//顶点v出队列
        //检测v所有邻接点
		for (w = FirstNeighbor(G,v); w >=0; w = NextNeighbor(G, v, w))
		{	
			if (!visited[w])  //w为v的尚未访问的邻接顶点
			{
				visited[w];//访问顶点w
				visited[w] = TRUE;//对w做已访问标记
				EnQueue(Q, w);//顶点w入队列
			}
		}
	}
}

2.2、深度优先遍历（DFS）

图的深度优先遍历就类似树的先序遍历

算法要点：

• 递归地深入探索未被访问过的邻接点（类似于树的先根遍历）
• 如何从一个结点找到与之邻接的其他顶点
• visited数组，防止重复访问
• 如何处理非连通图

复杂度：

• 空间复杂度：O(|V|) ---- 来自递归工作站
• 时间复杂度：
  • 访问结点的时间+访问所有边的时间
  • 邻接矩阵：O(|V|^2)
  • 邻接表：O(|V|+|E|)

深度优先生成树：

• 即为深度优先遍历确定的树
• 邻接表存储的图表示方式不唯一，深度优先遍历序列，生成树也不唯一
• 深度优先遍历非连通图可得深度优先生成森林

伪代码描述深度优先遍历：

/* 访问标记数组 */
bool visited[MAX_VERTEX_NUM];

/* 对图G进行深度优先遍历 */
void DFSTraverse(Graph G)//主要是处理连通图多的情况
{
	for (v = 0; v < G.vexnum; ++v)
	{
		visited[i] = FALSE;//访问标记数组初始化
	}
	
	for (v = 0; v < G.vexnum; ++v)//从0号顶点开始遍历
	{
		if (!visited[v])//对每个连通分量调用一次BFS
		{
			DFS(G, v);//vi未访问过，从Vi开始BFS
		}
	}
}
/* 深度优先遍历 */
void DFS(Graph G, int v) //从顶点v出发，深度优先遍历图G
{
	visit(v); //访问初始顶点v
	visited[v] = TRUE;//对v做已访问标记
    //检测v所有邻接点
    for (w = FirstNeighbor(G,v); w >=0; w = NextNeighbor(G, v, w))
    {	
        if (!visited[w])  //w为v的尚未访问的邻接顶点
        {
           DFS(G,w);
        }
    }
}

---

图的遍历和连通性：

• 无向图：DFS/BFS函数调用次数 = 连通分量数
• 有向图
  • 若从起始顶点到其他顶点都有路径，则只需调用一次DFS/BFS函数
  • 对于强连通图，从任一顶点出发都只需调用一次DFS/BFS函数

3、最小生成树构造过程及算法（MST）

针对的是带权连通无向图

边的权值之和最小的生成树，就是最小生成树

普利姆算法（Prim）：

• 时间复杂度为：O(|V|^2) 适合边稠密图

• 从某个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

克鲁斯卡尔算法（Kruskal）:

• 时间复杂度为：O(|E|log2|E|) 适合边稀疏图
• 每次选择一条权值最小的边，使这两条边的两头连通（已经连通的不选），直到所有结点都连通

4、拓扑排序过程及算法

4.1、AOV网：

• 顶点代表活动，有向边<Vi,Vj>表示活动Vi必须先于Vj进行
• AOV网一定是DAG图（有向无环图），不能有环。

4.2、拓扑排序

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

4.3、逆拓扑排序

1. 从AOV网中选择一个没有后继（出度为0）的顶点并输出
2. 从网中删除该顶点和所有以它为终点的有向边
3. 重复 1 和 2 直到当前的AOV网为空

另一种实现方式：用DFS实现拓扑排序/逆拓扑排序

/* 访问标记数组 */
bool visited[MAX_VERTEX_NUM];

/* 对图G进行深度优先遍历 */
void DFSTraverse(Graph G)//主要是处理连通图多的情况
{
	for (v = 0; v < G.vexnum; ++v)
	{
		visited[i] = FALSE;//访问标记数组初始化
	}
	
	for (v = 0; v < G.vexnum; ++v)//从0号顶点开始遍历
	{
		if (!visited[v])//对每个连通分量调用一次BFS
		{
			DFS(G, v);//vi未访问过，从Vi开始BFS
		}
	}
}
/* 深度优先遍历 */
void DFS(Graph G, int v) //从顶点v出发，深度优先遍历图G
{
	visit(v); //访问初始顶点v
	visited[v] = TRUE;//对v做已访问标记
    //检测v所有邻接点
    for (w = FirstNeighbor(G,v); w >=0; w = NextNeighbor(G, v, w))
    {	
        if (!visited[w])  //w为v的尚未访问的邻接顶点
        {
           DFS(G,w);
        }
    }
    //用在拓扑排序的主要改动
    cout << v;//输出顶点
}

4.4、性质

• 拓扑排序、逆拓扑排序序列可能不唯一
• 若图中有环，则不存在拓扑排序序列/逆拓扑排序序列

5、关键路径相关内容

5.1、AOV网

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销

相关概念：

• 在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），表示整个工程的开始；
• 也仅有一个出度为0的顶点，称为结束顶点（汇点），表示整个工程的结束
• 从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动

5.2、求解方法

1. 求所有事件的最早发生时间ve( ) 正序取最大值 （指的是结点）
2. 求所有事件的最迟发生时间vl( ) 倒序取最小值（指的是结点）
3. 求所有活动的最早发生时间e( ) （指的是边）从前往后算发出边的的结点值
4. 求所有活动的最迟发生时间 l( )（指的是边）从后往前算 结点值减路径值
5. 求所有活动的时间余量 d ( ) = （活动的最迟发生时间 - 活动的最早发生时间）
   1. d( i ) = 0的活动就是关键活动，由关键活动可得关键路径

5.3、特性

• 若关键活动耗时增加，则整个工期的工程将延长
• 缩短关键活动的时间，可以缩短整个工程的工期
• 当缩短到一定程度时，关键活动可能会变成非关键活动
• 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的

6、最短路径相关内容

6.1、单源最短路径

6.1.1、BFS算法（无权图）

对BFS算法进行修改：在visit一个顶点时，修改其最短路径长度d[ ]并在path[ ]记录前驱结点

6.1.2、Dijkstra算法（带权图、无权图）

就是上学路径问题，就是找到达学校路程最短的那条路

标记最短路径数组、最短路径长度数组、路径前驱数组

不适用于有负权值的带权图

6.2、各顶点间的最短路径

Floyd算法（带权图、无权图）

可以解决带负权值的图

添加中转点

//.....准备工作，初始化矩阵A和path
for (int k = 0; k < n; k++)//考虑以Vk作为中转点
{
    for (int i = 0; i < n; i++) //遍历整个矩阵，i为行号，j为列号
    {
        for (int j = 0; j < n; j++)
        {
            if (A[i][j]>A[i][k]+A[k][j]) //如果以Vk为中转点的路径更短
            {
                A[i][j] = A[i][k] + A[k][j];//更新最短路径长度
                path[i][j] = k;//中转点
            }
        }
    }
}

---

注：以上算法均不能解决带负权回路的图

7、与图的应用相关的递归算法

有向无环图：一个有向图中不存在环。简称DAG图

用来描述表达式：算数表达式用树的形式展示，合并相同层次的操作数和操作符

更多内容请在评论区留言讨论