第六章-图

WanXing2022年7月28日大约 10 分钟

6.1 图的基本概念

1.图的定义

1.图的定义：由顶点集V和边集E组成，记为 G=（V，E）
图不可以是空图，图的顶点集V一定是空，但边集E可以为空，此时图中只有顶点没有边
2.有向图：<v，w>，v为弧尾，w为弧头，v到w弧
2.无向图：（v，w）v、w互为邻接点
3.简单图：①：不存在重复边，②：不存在顶点到自身的边
4.多重图：不满足简单图
5.完全图：无向图（0 ~ $n(n-1)/2$ ）; 有向图（0 ~ $n(n-1)$ ）
6.子图：V、E是图的子集
7.连通：顶点到顶点路径存在则连通
8.连通图：任意两个顶点连通
9.连通分量：无向图中的极大连通子图
- 10.强连通图、强连通分量：有向图中，正逆向都有路径
11.生成树：包含图中全部顶点的一个极小连通子图
砍去一条边变成非连通图，加上一条边形成回路
12.生成森林：连通分量的生成树构成非连通分量的生成森林
12.顶点的度、入度和出度：
- 无向图->度：依附于顶点边的条数；
- 有向图->入度：以顶点为终点；出度：以顶点为起点
13.边的权和网：每条边附带有某种含义的数值
14.稠密图、稀疏图：边数很少的图称为稀疏， $|E|<|V|log|V|$
15.路径、路径长度和回路
16.简单路径、简单回路：顶点不重复出现的路径
17.距离：最短路径，不存在记为 $\infty$
18.有向树：一个顶点入度为0，其他均为1

6.2 图的存储及基本操作

1.邻接矩阵法

1.定义：用一个一维数组存储图中的顶点信息，用一个二维数组（邻接矩阵）存储图中边的信息
2.结构定义

#define MaxVertexNum 100    //顶点数目的最大值
typedef char VertexType;    //顶点的数据类型
typedef int EdgeType;   //边上权值的数据类型
typedef struct{
  VertexType Vex[MaxVertexNum];
  EdgeType Edge[MaxVertexNum][MaxVertexNum];
  int vexnum,arcnum;    //顶点数和弧数
}

空间复杂度 $O(n^2)$

3.特点
- 无向图的邻接矩阵一定是一个对称矩阵
- 对于无向图，第i行（或列）元素的个数，正好是顶点的度
- 对于有向图，第i行是顶点的出度；第i列是顶点的入度
- 容易确定顶点之间边的相连，但是检测的时间花费巨大
- 稠密图适合使用邻接矩阵存储
- $A^n[i][j]$ 等于顶点i到顶点j的长度为n的路径的数目

2.邻接表法

1.定义：
- 对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点的边 -> 边表
- 边表的头指针和顶点的数据信息采用顺序存储 -> 顶点表
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 {    //邻接表 ->只定义一次这种结构体类型的变量
  Adjlist vertices;
  int vexnum,arcnum;
}ALGraph;

空间复杂度：有向图 $O(|V|+|E|)$ ，无向图 $O(|V|+2|E|)$

3.特点
- 对于稀疏图，采用邻接表可极大节省存储空间
- 给定一顶点，很容易找出他的所有邻边，但是在确定两顶点间是否存在边效率较低
- 存在逆邻接表加速求解给定顶点的入度
- 图的邻接表表示不唯一，因为链接次序可以任意

3.十字链表

1.定义：对应于有向图每条弧有一个结点，对应于每个结点也有一个结点
- 弧结点：尾域、头域、链域（弧头相同的下一条、弧尾相同的下一条）、info域
- 顶点结点：data域、firstin（以该顶点为弧头的的第一个弧结点）和firstout

空间复杂度： $O(|V|+|E|)$

2.特点
- 容易求得结点的入度和出度
- 表示不唯一
- 一个十字链表确定一个图

4.邻接多重表

1.定义：无向图的另一种链式存储结构

5.图的基本操作

Adjacent(G, x, y)
Neighbors(G, x)
InsertVertex(G, x)
AddEdge(G, x, y)
RemoveEdge(G, x, y)
FirstNeighbor(G, x)
NextNeighbor(G, x, y)
Get_edge_value(G, x, y)
Set_edge_value(G, x, y, v)

6.3 图的遍历

1.广度优先搜索 Breadth-First-Search, BFS

伪代码
BFSopen in new window 算法的性能分析
- 空间复杂度 $O(|V|)$
- 采用邻接表时间复杂度 $O(|V|+|E|)$
- 采用邻接矩阵的时间复杂度为 $O(|V|^2)$
BFS 算法求解单源最短路径问题
广度优先生成树

深度优先搜索 Depth-First-Search, DFS

伪代码
DFSopen in new window 算法的性能分析
- 空间复杂度 $O(|V|)$
- 采用邻接表的时间复杂度 $O(|V|+|E|)$
- 采用邻接矩阵时间复杂度 $O(|V|^2)$
深度优先的生成树和生成森林

6.4图的遍历与图的连通性

无向图：若连通则从任一结点出发，一次遍历就能访问所有结点
有向图：从初始点到图中各个顶点都有路径

6.4 图的应用

1.最小生成树 Minimum-Spanning-Tree, MST

1.生成树：砍去一条边，生成树变为非连通图；增加一条边，形成图中的一条回路
- 最小生成树的性质
  - 1.最小生成树不唯一
  - 2.最小生成树的边的权值之和唯一
  - 3.最小生成树的边数为顶点数 -1

2.Prim 算法

1.初始化：添加任一顶点 $u_0$
2.循环：
- 从图中（原图 - 已有图）选出最小权值的边，加入树

3.Kruskal 算法

1.初始化：每个顶点构成一棵独立的树
2.循环：
- 按边权值递增的顺序依次选择一条边
  - 若加入后不构成回路，则加入
  - 若构成回路，则丢弃

4.最短路径 Short Path First, SPF

Dijkstra 算法——求单源最短路径问题
- 迪杰斯特拉 Dijkstra
  - Dijkstra 算法
Floyd 算法——求各顶点之间最短路径问题
~OSPF 算法
~SPFA 算法 Shortest Path Faster Algorithm

5.Dijkstra

初始化：只有一个顶点
每次从未标记的结点中选择距离出发点最近的结点，标记，收录到最优路径中
计算刚加入结点A的邻近结点B的距离，若（结点A距离 + 结点A到结点B的边长）< 结点B的距离，更新结点B的距离和前面点
直到目的地标记

边上带有负权值时并不适用

算法	适用性	邻接矩阵存储	邻接表	边集数组（三元组）
Prim	边稠密	$O(\|V\|^2)$	$O(\|V\|+\|E\|)$
Kruskal	边稀疏，顶点多			$O(\|E\|log\|E\|)$
Dijkstra	不适用于负权	$O(\|V\|^2)$
Floyd	负权、有无向都可	$O(\|V\|^3)$
拓扑排序		$O(\|V^2\|)$	$O(\|V\|+\|E\|)$
关键路径			$O(\|V\|+\|E\|$

6.Floydopen in new window

邻接矩阵dist储存路径，同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！而自己的长度为0.
从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。
而上述试探具体方法为遍历图中每一个点(i,j双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改。
重复上述直到最后插点试探完成

视频open in new window

7.有向无环图描述表达式

1.有向无环图 Direct Acyclic Graph
- 若一个有向图中不存在一个环，则称为有向无环图
- 利用DAG对相同子式共享

4.拓扑排序

1.AOV 网：Activity On Vertex Network
- 用DAG图表示一个工程，顶点表示活动，< $V_i$ , $V_j$ >表示活动顺序的一种关系
2.拓扑排序：
- 每个顶点只出现一次
- 若顶点A在序列中排在B的前面，则图中不存在从顶点A到B的路径
3.对AOV网进行拓扑排序
- 选择一个没有前驱的结点输出
- 从网中删除该顶点和所有以它为起点的有向边
- 重复直到AOV网为空或当前不存在无前驱的结点
4.对逆拓扑排序
- 从AOV网选择一个没有后继的顶点输出
- 从网中删除该顶点和所有以它为终点的有向边
- 重复直到AOV网为空

1.入度为0的顶点，工程可以从这个顶点所代表的活动开始或继续
2.若一个顶点有多个直接后继，拓扑排序通常不唯一；若顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继，则拓扑排序是唯一的
3.邻接矩阵是三角矩阵 -> 存在拓扑序列反之不一定

5.关键路径

1.AOE 网：Activity On Edge Network
- 以顶点表示事件，
- 以有向边表示活动，
- 以边上的权值表示活动的开销
2.开始顶点（源点）：入度为0，工程的开始
3.结束顶点（汇点）：出度为0，工程的结束
4.关键路径：所有路径中，最大路径长度的路径 -> 完成整个工程的最短时间
5.关键活动：关键路径上的活动
- 6.事件 $v_k$ $v_{k}$ 的最早发生时间 $ve(k)$ $v e (k)$
  - 从源点到该顶点的最长路径长度
- 7.事件 $v_k$ $v_{k}$ 的最迟发生时间 $vl(k)$ $v l (k)$
  - 保证它的后继事件在其最迟发生时间能够发生时，该事件最迟必须发生的时间
- 8.活动 $a_i$ $a_{i}$ 的最早开始时间 $e(i)$ $e (i)$
  - 事件最最早发生的事件
- 9.活动 $a_i$ $a_{i}$ 的最迟开始时间 $l(i)$ $l (i)$
  - 事件最迟发生时间和该活动所需时间之差
- 10.一个活动 $a_i$ $a_{i}$ 的最迟开始时间 $l(i)$ $l (i)$ 和其最早开始时间 $e(i)$ $e (i)$ 的差额 $d(i)=l(i)-e(i)$ $d (i) = l (i) - e (i)$
  - 指完该活动完成的时间余量 |--<-->--|
  - 若为0，则活动必须如期完成 -> 关键活动
- 11.求关键路径的步骤
  - 从源点出发， $ve(源点)=0$ ，按拓扑求得各点 $ve()$
  - 从汇点出发， $vl(汇点)=0$ ，按逆拓扑求得各点 $vl()$
  - 各点求 $e()$ 、 $l()$ 、 $d()$
  - $d()=0$ 为关键路径

关键路径上的所有活动都是关键活动，可以通过加快关键活动缩短整个工程的工期；不能任意缩短，一旦缩短到一定程度，关键活动变为非关键活动
关键路径并不唯一，只提高一条关键路径上的关键活动速度并不能提高整个工程的工期，只有加快包含在所有关键路径上的关键活动才能缩短工期

第六章-图

# 6.1 图的基本概念

# 1.图的定义

# 6.2 图的存储及基本操作

# 1.邻接矩阵法

# 2.邻接表法

# 3.十字链表

# 4.邻接多重表

# 5.图的基本操作

# 6.3 图的遍历

# 1.广度优先搜索 Breadth-First-Search, BFS

# 深度优先搜索 Depth-First-Search, DFS

# 6.4图的遍历与图的连通性

# 6.4 图的应用

# 1.最小生成树 Minimum-Spanning-Tree, MST

# 2.Prim 算法

# 3.Kruskal 算法

# 4.最短路径 Short Path First, SPF

# 5.Dijkstra

# 6.Floydopen in new window

# 7.有向无环图描述表达式

# 4.拓扑排序

# 5.关键路径

6.1 图的基本概念

1.图的定义

6.2 图的存储及基本操作

1.邻接矩阵法

2.邻接表法

3.十字链表

4.邻接多重表

5.图的基本操作

6.3 图的遍历

1.广度优先搜索 Breadth-First-Search, BFS

深度优先搜索 Depth-First-Search, DFS

6.4图的遍历与图的连通性

6.4 图的应用

1.最小生成树 Minimum-Spanning-Tree, MST

2.Prim 算法

3.Kruskal 算法

4.最短路径 Short Path First, SPF

5.Dijkstra

6.Floydopen in new window

7.有向无环图描述表达式

4.拓扑排序

5.关键路径