W.T.的博客

Every day to be a little better

数据结构与算法分析-图

发表于 更新于 分类于
本文字数： 19k 阅读时长 ≈ 17 分钟
图的概念，图的存储【邻接矩阵，邻接表】，图的基本操作，图的遍历【DFS，BFS】，最小生成树【Prim，Kruskal】，最短路径【Dijkstra，Floyd】，拓扑排序，关键路径

视频讲解，习题讲解，思维导图，PPT资源

链接: https://pan.baidu.com/s/1fRViwPYYriuezJANg2uJmA 密码: 7a4f

1. 图的基本概念

1.1. 图的定义

图G由顶点集V和边集E组成，记为G = (V, E)，其中V(G)表示图G中顶点的有限非空集；E(G) 表示图G中顶点之间的关系(边)集合。若V = {v1, v2, … , vn}，则用|V|表示图G中顶点的个数，也称图G的阶，

E= {(u, v) | u$\epsilon $V, v$\epsilon $V}，用|E|表示图G中边的条数。

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

1.2. 图逻辑结构的应用

车站路线图

铁路路线图

地图

微信好友关系网——无向图

微博粉丝关系网——有向图

1.3. 图分类

1.3.1. 无向图

若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为(v, w)或(w, v)，因为(v, w) = (w, v)，其中v、w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v、w相关联。

G2 = (V2, E2)

V2 ={A,B,C,D,E}

E2 = {(A, B), (B, D), (B, E), (C, D), (C, E), (D, E)}

1.3.2. 有向图

若E是有向边(也称弧)的有限集合时，则图G为有向图。 弧是顶点的有序对，记为<v, w>，其中v、w是顶点，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。

<v, w> ≠ <w, v>

G1 = (V1, E1)

V1 = {A, B, C, D, E} D

E1 = {<A, B>, <A, C>, <A, D>, <A, E>, <B, A>, <B, C>, <B, E>, <C, D>}

1.3.3. 简单图

  1. 不存在重复边;
  2. 不存在顶点到自身的边

数据结构课程只探讨 “简单图”

1.3.4. 多重图

图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联， 则G为多重图

1.4. 顶点的度、入度、出度

1.4.1. 无向图

顶点v的度是指依附于该顶点的边的条数，记为TD(v)。

在具有n个顶点、e条边的无向图中，$\sum_{i=1}^{n}$ TD(vi)=2e

即无向图的全部顶点的度的和等于边数的2倍

1.4.2. 有向图

入度是以顶点v为终点的有向边的数目，记为ID(v);

出度是以顶点v为起点的有向边的数目，记为OD(v)。

顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

在具有n个顶点、e条边的有向图中，$\sum_{i=1}^{n}$ID(vi) =$\sum_{i=1}^{n}$OD(vi) = e

1.5. 顶点**-**顶点的关系描述

路径——顶点vp到顶点vq之间的一条路径是指顶点序列，Vp，Vi1，Vi2，…，Vim，Vq

回路——第一个顶点和最后一个顶点相同的路径称为回路或环

简单路径——在路径序列中，顶点不重复出现的路径称为简单路径

简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。 路径长度——路径上边的数目

点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。 若从u到v根本不存在路径，则记该距离为无穷∞)。

无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的

有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

1.6. 连通图

若无向图中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。

常见考点:

对于n个顶点的无向图G， 若G是连通图，则最少有 n-1 条边

若G是非连通图，则最多可能有 𝐶$_{n-1}^{2}$条边

1.7. 强连通图

若有向图中任何一对顶点都是强连通的，则称此图为强连通图。

常见考点：

对于n个顶点的有向图G， 若G是强连通图，则最少有n条边(形成回路)

1.8. 研究图的局部——子图

设有两个图 G= (V, E)和 G‘ = (V‘, E‘)，若V‘是V的子集，且E‘是E的子集，则称G‘是G的子图。

并非V和E的任何子集都能构成G的子图，E的子集中某些边关联的顶点可能不在V的子集中

若有满足 V(G‘) = V(G)的子图G‘，则称其为G的生成子图

并非任意挑几个点、几条边都能构成子图

1.9. 连通分量

无向图中的极大连通子图称为连通分量。

极大连通子图：子图必须连通，且包含尽可能多的顶点和边

1.10. 强连通分量

有向图中的极大强连通子图称为有向图的强连通分量

极大强连通子图：子图必须强连通，同时强连通分量保留尽可能多的边

1.11. 生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。

极小连通子图：边尽可能的少，但要保持连通

若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通 图，若加上一条边则会形成一个回路。

1.12. 生成森林

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

1.13. 边的权、带权图**/**网

给各边赋予一个权 值——实际距离

给各边赋予一个数 值——转发概率

边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。

带权图/网——边上带有权值的图称为带权图，也称网。

带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

带权图的应用举例：地图导航——距离最短，地图导航——收费最低

1.14. 几种特殊形态的图

1.14.1. 无向完全图

无向图中任意两个顶点之间都存在边

若无向图的顶点数|V|=n，则 |E| ∈ [0, C$_{n}^{2}$] = [0, n(n–1)/2]

1.14.2. 有向完全图

有向图中任意两个顶点之间都存在方向相反的两条弧

若有向图的顶点数|V|=n，则 |E| ∈ [0, 2C$_{n}^{2}$] = [0, n(n–1)]

1.14.3. 稀疏图

边数很少的图

1.14.4. 稠密图

边数很多的图

没有绝对的界限，一般来说|E| $\geq$ |V|log|V|时，可以将G视为稠密图

1.14.5. 树

不存在回路，且连通的无向图

n个顶点的树，必有n-1条边。

常见考点：n个顶点的图，若 |E|>n-1，则一定有回路

1.14.6. 有向树

一个顶点的入度为0、其余顶点的 入度均为1的有向图，称为有向树。

2. 图的存储

2.1. 邻接矩阵法(数组)

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

2.1.1. 结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//顶点数目最大值
#define MaxVertexNum 100
//权值无穷大
#define INFINITY 2<<30
//顶点数据类型
#define char VertexType
//带权图中边上权值的数据类型
#define int EdgeType
typedef struct{
  //顶点表
  VertexType Vex[MaxVertexNum];
  //邻接矩阵，边表
  EdgeType Edge[MaxVertexNum][MaxVertexNum];
  //图的当前顶点树和边数
  int vexnum,arcnum;
}MGraph;

2.1.2. 度计算

第i个结点的出度 = 第i行的非零元素个数

第i个结点的入度 = 第i列的非零元素个数

第i个结点的度 = 第i行、第i列的非零元素个数之和

邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O(|V|)

2.1.3. 邻接矩阵法的性能分析

空间复杂度：O(|V|2) ——只和顶点数相关，和实际的边数无关

适合用于存储稠密图

无向图的邻接矩阵是对称矩阵，可以压缩存储(只存储上三角区/下三角区)

2.1.4. 对称矩阵

若 n 阶方阵中任意一个元素 ai,j 都有 ai,j = aj,i 则该矩阵为对称矩阵

普通存储：n*n 二维数组

压缩存储策略：只存储主对角线+下三角区(或主对角线+上三角区)

策略:只存储主对角线+下三角区 按行优先原则将各元素存入一维数组中。

B[0] B[1] B[2] B[3] … B[$\frac{(1+n)*n}{2}$-1]
a1,1 a2,1 a2,2 a3,1 … an,n-1 an,n

思考:

  1. 数组大小应为多少?

    $\frac{(1+n)*n}{2}$

  2. 站在程序员的角度，对称矩阵压缩存储后怎样才能方便使用?

    可以实现一个“映射”函数

    矩阵下标 -> 一维数组下标

  3. 按行优先的原则，ai,j 是第几个元素?

    [1+2+···+(i-1)] + j -> 第 $\frac{i(i-1)}{2}$ + j 个元素 -> k= $\frac{i(i-1)}{2}$+ j − 1

  4. 按行优先的原则，aj,i是第几个元素?

    ai,j = aj,i (对称矩阵性质)

    k= $\frac{j(j-1)}{2}$ + 𝑖 − 1

故压缩到一维数组时，下三角区和主对角线元素 k=$\frac{i(i-1)}{2}$+j-1，上三角区元素ai,j =aj,i，$\frac{j(j-1)}{2}$+i-1

2.1.5. 邻接矩阵法的性质

设图G的邻接矩阵为A(矩阵元素为0/1)，则An的元素An [i] [j]等于由顶点i到顶点j的长度为n的路径的数目

2.1.6. 邻接矩阵法要点回顾

  • 如何计算指定顶点的度、入度、出度(分无向图、有向图来考虑)?时间复杂度如何?
  • 如何找到与顶点相邻的边(入边、出边)?时间复杂度如何?
  • 如何存储带权图?
  • 空间复杂度——O(|V|2)，适合存储稠密图
  • 无向图的邻接矩阵为对称矩阵，如何压缩存储?
  • 设图G的邻接矩阵为A(矩阵元素为0/1)，则An的元素An[i] [j]等于由顶点i到顶点j的长度为n 的路径的数目

2.2. 邻接表法(顺序+链式存储)

2.2.1. 结构体

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
//边
typedef struct ArcNode{
  //该弧所指向的顶点的位置
  int adjvex;
  //指向下一条弧的指针
  struct ArcNode *next;
  //边权值
  //InfoType info
}ArcNode;

//顶点
#define MaxVertexNum 100
//顶点数据类型
#define char VertexType
typedef struct VNode{
  //顶点信息
  VertexType data;
  //指向第一条依附该结点的弧的指针
  ArcNode *first;
}VNode,AdjList[MaxVertxNum];

//图
typedef struct{
  //邻接表
  AdjList vertices;
  //顶点数，弧数
  int vexnum,arcnum;
}ALGraph;

2.2.2. 对比:树的孩子表示法

孩子表示法：顺序存储各个节点，每个结点中保存孩子链表头指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct CTNode{
  //孩子结点在数组中的位置
  int child;
  //下一个孩子
  struct CTNode *next;
}

typedef struct{
  ElemType data;
  //第一个孩子
  struct CTNode *firstChild;
}CTBox;

#define MAX_TREE_SIZE 100
typedef struct{
  CTBox nodes[MAX_TREE_SIZE];
  int n,r;
}CTree;

2.2.3. 邻接表的性能分析

图的邻接表表示方式并不唯一

无向图：边结点的数量是2|E|，整体空间复杂度为 O(|V| + 2|E|)

有向图：边结点的数量是|E|，整体空间复杂度为 O(|V| + |E|)

思考：

  1. 如何求顶点的度、入度、出度?

    第i个结点的出度 = 该结点后链接的结点个数

    第i个结点的入度 = 遍历所有边结点中值等于该结点的个数

    第i个结点的度 = 出度+入度

  2. 如何找到与一个顶点相连的边/弧?

    指向：搜索该结点后链接结点中是否存在该结点

    被指向：搜索所有边结点找相同值

2.3. 十字链表法-存储有向图

邻接矩阵、邻接表存储有向图时，有向图找顶点的入边不方便，邻接矩阵存储空间复杂度高达O(|V|2)

用十字链表法空间复杂度：O(|V|+|E|)

如何找到指定顶点的所有出边?——顺着绿色线路找

如何找到指定顶点的所有入边?——顺着橙色线路找

2.4. 邻接多重表法-存储无向图

邻接矩阵、邻接表存储无向图，邻接表每条边对应两份冗余信息，删除顶点、删除边等操作时间复杂度高，邻接矩阵存储空间复杂度高达O(|V|2)

空间复杂度：O(|V|+|E|) 删除边、删除节点等操作很方便

删除A-B边

删除顶点E

2.5. 四种存储结构对比

邻接表 邻接矩阵 十字链表 邻接多重表
空间复杂度 无向图O(|V|+2|E|)；有向图O(|V|+|E|) O(|V|2) O(|V|+|E|) O(|V|+|E|)
适用于 存储稀疏图 存储稠密图 有向图 无向图
表示方式 不唯一 唯一 不唯一 不唯一
计算度/出度/入度 计算有向图的度，入度不方便，其余很方便 必须遍历对应行或列
找相邻的边 找有向图的入边不方便，其余很方便 必须遍历对应行或列 很方便 很方便

3. 图的基本操作

3.1. 总览

  • Adjacent(G,x,y)：判断图G是否存在边<*x*, *y*>或(x, y)。

  • Neighbors(G,x)：列出图G中与结点x邻接的边。

  • InsertVertex(G,x)：在图G中插入顶点x。

  • DeleteVertex(G,x)：从图G中删除顶点x。

  • AddEdge(G,x,y)：若无向边(x, y)或有向边<x*, y>不存在，则向图G*中添加该边。

  • RemoveEdge(G,x,y)：若无向边(x, y)或有向边<x*, y>存在，则从图G*中删除该边。

  • FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点

    或图中不存在x，则返回-1。

  • NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一

个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。

  • Get_edge_value(G,x,y)：获取图G中边(x, y)或<*x*, *y*>对应的权值。
  • Set_edge_value(G,x,y,v)：设置图G中边(x, y)或<x*, y>对应的权值为v*。

3.2. Adjacent(G,x,y)

判断图G是否存在边<x,y>或(x, y)。

有向图 无向图
邻接表 查找结点x的链表中是否存在结点y
O(1)~O(|V|)		 查找结点x的链表中是否存在结点y or
查找结点y的链表中是否存在结点x
O(1)~O(|V|)
邻接矩阵 矩阵G[x] [j]=0则不存在，=1则存在
O(1)		 矩阵G[x] [j]=0则不存在，=1则存在 or
矩阵G[j] [x]=0则不存在，=1则存在
O(1)

3.3. Neighbors(G,x)

列出图G中与结点x邻接的边–求结点x的度

有向图 无向图
邻接表 出度：列举结点x的链表中所有结点O(|V|)
入度：搜素所有边结点查找结点x，找到结点x所在链表的被指向O(|E|)		 出/入度：列举结点x的链表中所有结点O(|V|)
邻接矩阵 出度：使G[x] [j]!=0所在x行的所有结点j - O(|V|)
入度：使G[j] [x]!=0所在x列的所有结点j - O(|V|)		 出/入度：使G[x] [j]!=0所在x行的所有结点j - O(|V|)

3.4. InsertVertex(G,x)

在图G中插入顶点x

有向图 无向图
邻接表 结点数组增加一行 –O(1) 结点数组增加一行 – O(1)
邻接矩阵 矩阵增加一行一列 – O(1) 矩阵增加一行一列 – O(1)

3.5. DeleteVertex(G,x)

从图G中删除顶点x

有向图 无向图
邻接表 将数组结点中对应结点数据域置空，对应链表置NULL – O(1)~O(|V|)
遍历所有边结点删除结点x – O(|E|)		 将数组结点中对应结点数据域置空，对应链表置NULL
遍历所有边结点删除结点x– O(1)~O(|E|)
邻接矩阵 将x行x列置空 将x行x列置空

3.6. AddEdge(G,x,y)

若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。

有向图 无向图
邻接表 结点x链表中后插结点y – O(1)-O(|V|) 结点x链表中后插结点y
结点y链表中后插结点x – O(1)-O(|V|)
邻接矩阵 G[x] [y]=1 - O(1) G[x] [y]=1 且G[y] [x]=1 – O(1)

4. 图的遍历

4.1. 广度优先遍历BFS

4.1.1. 树层序 vs 图层序

树层序遍历：

  1. 若树非空，则根节点入队
  2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
  3. 重复2直到队列为空

图层序遍历类同于树，此外要点：

  1. 找到与一个顶点相邻的所有顶点
  2. 标记哪些顶点被访问过
  3. 需要一个辅助队列

4.1.2. 算法实现

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
29
30
31
32
33
34
35
36
37
bool visited[VertexNum];
InitQueue(Q);

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

//从结点v开始遍历
void BFS(Graph G,int v){
  visit(v);
  visited[v]=true;
  //顶点v入队
  EnQueue(Q,v);
  while(!IsEmpty(Q)){
    //顶点v出队
    DeQueue(Q,v);
    for(int w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
      //检测v的所有邻接点
      if(!visited[w]){
        //w为v的尚未访问的邻接顶点
        visit(w);
        //w作已访问标记
        visited[w]=true;
        //w入队
        EnQueue(Q,w);
      }
    }
  }
}

4.1.3. 遍历实现

从顶点1出发得到的广度优先遍历序列：1，2，5，6，3，7，4，8

从顶点2出发得到的广 度优先遍历序列：2，1，6，5，3，7，4，8

从顶点3出发得到的广度优先遍历序列：3，4，6，7，8，2，1，5

4.1.4. 遍历序列的可变性

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

从顶点2开始，【2，1，6，5，3，7，4，8】

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

从顶点2开始，【2，1，6，5，3，7，4，8】 or 【2，6，1，3，7，5，4，8】

4.1.5. 复杂度

空间复杂度：最坏情况，辅助队列大小为 O(|V|)

时间复杂度：

邻接矩阵——访问|V|个顶点需要O(|V|)的时间，查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点， 时间复杂度**=** O(|V|2)

邻接表——访问|V|个顶点需要O(|V|)的时间，查找各个顶点的邻接点共需要O(|E|)的时间， 时间复杂度=O(|V|+|E|)

4.1.6. 广度优先生成树

广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一。

对非连通图的广度优先遍历，可得到广度优先生成森林

4.2. 深度优先遍历DFS

4.2.1. 树的深度优先遍历 vs DFS

树的深度优先遍历(先根、后根):

从根节点出发，能往更深处走就尽量往深处走。每当访问一个结点的时候，要检查是否还有与当前结点相邻的且没有被访问过的结点，如果有的话就往下一层钻。 

1
2
3
4
5
6
7
8
void PreOrder(TreeNode *R){
  if(R!=NULL){
    visit(R);
    while(/*R还有下一个子树T*/){
      PreOder(T);
    }
  }
}

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

4.2.2. 算法实现

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
bool visited[VertexNum];

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

//从结点v开始遍历
void DFS(Graph G,int v){
  visit(v);
  visited[v]=true;
  for(int w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
      //w为u尚未访问的邻接顶点
      if(!visited[w]){
        DFS(G,w);
      }
    
  }
}

//非递归形式-同层数据从右往左输出
InitStack(S);
void DFS(Graph G,int v){
  visited[v]=true;
  Push(S,v);
  while(!IsEmpty(S)){
    Pop(G,v);
    visit(v);
    ArcNode *p=(G->adjList[v]).firstarc;
    while(p!=NULL){
      int w = p->adjvex;
      if(!visited[w]){
        Push(G,w);
        visited[w]=true;
      }
      p = p->nextarc;
    }
  }
}

4.2.3. 遍历实现

从2出发的深度优先遍历序列：2，1，5，6，3，4，7，8

从3出发的深度优先遍历序列：3，4，7，6，2，1，5，8

从1出发的深度优先遍历序列：1，2，6，3，4，7，8，5

4.2.4. 复杂度分析

空间复杂度：

来自函数调用栈，最坏情况，递归深度为O(|V|)

最好情况，O(1) —— 一个顶点关联其他所有结点

时间复杂度：

时间复杂度=访问各结点所需时间+探索各条边所需时间

邻接矩阵——访问|V|个顶点需要O(|V|)的时间，查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点， 时间复杂度**=** O(|V|2)

邻接表——访问|V|个顶点需要O(|V|)的时间，查找各个顶点的邻接点共需要O(|E|)的时间， 时间复杂度=O(|V|+|E|)

4.2.5. 遍历序列可变性

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

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

4.2.6. 深度优先生成树

深度优先生成树由深度优先遍历过程确定

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

同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，深度优先生成树也不唯一

4.3. 图的遍历与图的连通性

对无向图进行BFS/DFS遍历，调用BFS/DFS函数的次数**=**连通分量数

对于连通图，只需调用1次 BFS/DFS

对有向图进行BFS/DFS遍历 调用BFS/DFS函数的次数要具体问题具体分析

若起始顶点到其他各顶点都有路径，则只需调用1次 BFS/DFS 函数

对于强连通图，从任一结点出发都只需调用1次 BFS/DFS

5. 最小生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。

若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通 图，若加上一条边则会形成一个回路。

广度优先生成树，深度优先生成树都是极小连通子图。

5.1. 最小生成树(最小代价树)概念

连通图的生成树是包含图中全部顶点的一个极小连通子图。

对于一个带权连通无向图 G= (V, E)，生成树不同，每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树(Minimum-Spanning-Tree, MST)。

最小生成树可能有多个，但边的权值之和总是唯一且最小的

最小生成树的边数 = 顶点数 - 1。砍掉一条则不连通，增加一条边则会出现回路

如果一个连通图本身就是一棵树，则其最小生成树就是它本身

只有连通图才有生成树，非连通图只有生成森林

求最小生成树的算法：Prim，Kruskal

5.2. Prim算法(普里姆)

5.2.1. 概念

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

时间复杂度：O(|V|2) 适合用于边稠密图

5.2.2. 实现思想

从V0开始，总共需要 n-1 轮处理

每一轮处理：循环遍历所有个结点，找到lowCost最低的，且还没加入树的顶点。 再次循环遍历，更新还没加入的各个顶点的lowCost值

5.2.3. 算法代码

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
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=510;
const int Inf=312312312;
int graph[maxn][maxn];
int dis[maxn];
bool visit[maxn]={false};


for (int i = 0; i < n; ++i)
	{
		int u=-1; int min=Inf;
		for (int j = 0; j < n; ++j)
		{
			if (visit[j]==false&&min>dis[j])
			{
				u=j;
				min=dis[j];
			}
		}
		if (u==-1)
		{
			break;
		}
		visit[u]=true;
		for (int v = 0; v < n; ++v)
		{
			if (visit[v]==false&&graph[u][v]!=Inf)
			{
				if (graph[u][v]<dis[v])
				{
					dis[v]=graph[u][v];
				}
			}
		}	
	}

5.3. Kruskal算法

5.3.1. 概念

每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)直到所有结点都连通

时间复杂度：O( |E|log2|E| ) 适合用于边稀疏图

5.3.2. 实现思想

共执行 e 轮，每轮判断两个顶点是否属于同一集合，需要 O(log2e)

总时间复杂度 O(elog2e)

初始：将各条边按权值排序

6. 最短路径

6.1. 单源最短路径

6.1.1. BFS

无权图可以视为一种特殊的带权图，只是每条边的权值都为1

6.1.1.1. 算法实现

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
29
30
31
32
33
34
35
36
37
#define Inf 2<<30;
bool visited[VertexNum];
InitQueue(Q);
//最短路径数组
int d[VertexNum];
//记录路径中的顶点
int path[VertexNum];

void BFS(Graph G,int u){
  for(int i=0;i<G.vexnum;i++){
    visited[i]=false;
    //开始时u到i结点距离为无穷
    d[i]=Inf;
    //无结点指向i结点
    path[i]=-1;
  }
  d[u]=0;
  visited[u]=true;
  //顶点v入队
  EnQueue(Q,u);
  while(!IsEmpty(Q)){
    //顶点v出队
    DeQueue(Q,u);
    for(int w = FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
      //检测v的所有邻接点
      if(!visited[w]){
        d[w]=d[v]+1;
        //路径为从u到w
        path[w]=u;
        //w作已访问标记
        visited[w]=true;
        //w入队
        EnQueue(Q,w);
      }
    }
  }
}

6.1.1.2. BFS算法的局限性

BFS算法求单源最短路径只适用于无权图，或所有边的权值都相同的图

6.1.2. Dijkstra算法

6.1.2.1. 迪杰斯特拉

艾兹格·W·迪杰斯特拉 Edsger Wybe Dijkstra (1930~2002)1972年图灵奖得主

  • 提出“goto 有害理论”——操作系统，虚拟存储技术
  • 信号量机制PV原语——操作系统，进程同步
  • 银行家算法——操作系统，死锁
  • 解决哲学家进餐问题——操作系统，死锁
  • Dijkstra最短路径算法——数据结构大题、小题

6.1.2.2. 算法思想

初始：从V0开始，初始化三个数组信息如下：

算法过程：

V0到V2 的最短**(带权)路径⻓度为：dist[2] = 9**

通过 path[ ] 可知，V0到V2 的最短**(带权)路径：V2 —> V1 —> V4 —> V0**

6.1.2.3. 算法代码

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
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=510;
const int Inf=312312312;
int graph[maxn][maxn];
int dis[maxn];
bool visit[maxn]={false};


for (int i = 0; i < n; ++i)
	{
		int u=-1; int min=Inf;
		for (int j = 0; j < n; ++j)
		{
			if (visit[j]==false&&min>dis[j])
			{
				u=j;
				min=dis[j];
			}
		}
		if (u==-1)
		{
			break;
		}
		visit[u]=true;
		for (int v = 0; v < n; ++v)
		{
			if (visit[v]==false&&graph[u][v]!=Inf)
			{
				if (dis[u]+graph[u][v]<dis[v])
				{
					dis[v]=dis[u]+graph[u][v];
				}
			}
		}	
	}

6.1.2.4. 时间复杂度

初始：

  • 若从V0开始，令 final[0]=ture; dist[0]=0; path[0]=-1。
  • 其余顶点final[k]=false; dist[k]=arcs[0] [k]; path[k]= (arcs[0] [k]==∞) ? -1 : 0

n-1轮处理:

循环遍历所有顶点，找到还没确定最短路径，且dist 最小的顶点Vi，令final[i]=ture。

并检查所有邻接自Vi 的顶点，对于邻接自Vi 的顶点 Vj ，若 final[j]==false 且 dist[i]+arcs[i] [j] < dist[j]，则令 dist[j]=dist[i]+arcs[i] [j]; path[j]=i。(注:arcs[i] [j]表示Vi 到Vj 的弧的权值)

时间复杂度：O(|V|2)

对比Prim最小生成树算法，不同的是 arcs[i] [j] < dist[j] ，则 dist[j]=arcs[i] [j]; path[j]=i，不涉及路径的累加

6.1.2.5. 可用于求所有顶点间的最短路径

对于所有顶点，重复|V|次即可，总的时间复杂度也是O(|V|3)

6.1.2.6. 不用于负权值带权图

事实上V0到V2的最短带权路径⻓度为5，Dijkstra算法不适用于有负权值的带权图

6.2. 各顶点间最短路径-Floyd算法

6.2.1. 罗伯特·弗洛伊德

罗伯特·弗洛伊德 (1936-2001)Robert W**.**Floyd 1978年图灵奖得主

  • 提出Floyd算法(Floyd-Warshall算法 )
  • 提出堆排序算法

6.2.2. Floyd算法思想

求出每一对顶点之间的最短路径 使用动态规划思想，将问题的求解分为多个阶段

对于n个顶点的图G，求任意一对顶点 Vi —> Vj 之间的最短路径可分为如下几个阶段:

  • 初始：不允许在其他顶点中转，最短路径是?

  • 0：若允许在 V0中转，最短路径是?

  • 1：若允许在 V0、V1中转，最短路径是?

  • 2：若允许在 V0、V1、V2 中转，最短路径是?

    根据 A(2) 可知，V1到V2 最短路径⻓度为 4，根据 path(2) 可知，完整路径信息为 V1—>V2

    根据 A(2) 可知，V0到V2 最短路径⻓度为 10，根据 path(2) 可知，完整路径信息为 V0—>V1—>V2

    根据 A(2) 可知，V1到V0 最短路径⻓度为 9, 根据 path(2) 可知，完整路径信息为 V1—>V2—>V0

  • n-1：若允许在 V0、V1、V2 ……Vn-1中转，最短路径是?

6.2.3. 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
//初始时A[][]=G[][]，path[][]=-1
//Vk作为中转点，n-顶点数
for(int k=0;k<n;k++){
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(A[i][j]>A[i][k]+A[k][j]){
        A[i][j]=A[i][k]+A[k][j];
        path[i][j]=k;
      }
    }
  }
}

空间复杂度：O(|V|2)

时间复杂度：O(|V|3)

6.2.4. 用于负权图

6.2.5. 仍不能解决的问题

Floyd 算法不能解决带有“负权回路”的图(有负权值的边组成回路)，这种图有可能没有最短路径

6.3. BFS—Dijkstra—Floyd

BFS 算法 Dijkstra 算法 Floyd 算法
无权图 ☑️ ☑️ ☑️
带权图 ✖️ ☑️ ☑️
带负权值的图 ✖️ ✖️ ☑️
带负权回路的图 ✖️ ✖️ ✖️
时间复杂度 O(|V|2)(邻接矩阵)或O(|V|+|E|)(邻接表) O(|V|2) O(|V|3)
通常用于 求无权图的单源最短路径 求带权图的单源最短路径 求带权图中各顶点间的最短路径

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

7.1. 有向无环图

若一个有向图中不存在环，则称为有向无环图，简称DAG图(Directed Acyclic Graph)

7.2. DAG描述表达式

7.3. 解题方法

8. 拓扑排序

8.1. 概念

8.1.1. AOV网

AOV(Activity On Vertex NetWork，用顶点表示活动的网)：用DAG图(有向无环图)表示一个工程。顶点表示活动，有向边<Vi， Vj>表示活动<Vi必须先于活动Vj进行。

8.1.2. 拓扑排序

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序

  1. 每个顶点出现且只出现一次。
  2. 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A 到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

找到做事的先后顺序

8.2. 实现思想

  1. 从AOV网中选择一个没有前驱(入度为0)的顶点并输出。
  2. 从网中删除该顶点和所有以它为起点的有向边。
  3. 重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点(无回路)为止。

8.3. 算法代码

邻接表

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
//边
typedef struct ArcNode{
  //该弧所指向的顶点的位置
  int adjvex;
  //指向下一条弧的指针
  struct ArcNode *nextarc;
  //边权值
  //InfoType info
}ArcNode;

//顶点
#define MaxVertexNum 100
//顶点数据类型
#define char VertexType
typedef struct VNode{
  //顶点信息
  VertexType data;
  //指向第一条依附该结点的弧的指针
  ArcNode *firstarc;
}VNode,AdjList[MaxVertxNum];

//图
typedef struct{
  //邻接表
  AdjList vertices;
  //顶点数，弧数
  int vexnum,arcnum;
}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
29
30
31
32
33
int print[MaxVertxNum];

bool TopplogicalSort(Graph G){
  InitStack(S);
  for(int i=0;i<G.vexNum;i++){
    //所有入度为0的顶点入栈
    if(indegree[i]==0){
      Push(G,i);
    }
  }
  //记录输出顶点数
  int count = 0;
  while(!IsEmpty(S)){
    int v;
    Pop(S,v);
    //输出顶点
    print[count++]=v;
    for(int w = G.vertices[v].firstarc;w=w->nextarc){
      //将所有v指向的顶点入度-1，并且将入度减为0的顶点入栈
      int p = w->adjvex;
      indegree[p]--;
      if(indegree[p]==0){
        Push(S,p);
      }
    }
  }
  //是否存在回路
  if(count<G.vexnum){
    return false;
  }else{
    return true;
  }
}

时间复杂度：O(|V|+|E|)若采用邻接矩阵，则需O(|V|2)

8.4. 逆拓扑排序

8.4.1. 实现思想

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

8.4.2. 算法实现-DFS

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
bool visited[VertexNum];

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

//从结点v开始遍历
void DFS(Graph G,int v){
  visited[v]=true;
  for(int w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
      //w为u尚未访问的邻接顶点
      if(!visited[w]){
        DFS(G,w);
      }    
  }
  //从底层开始输出顶点值
  visit(v);
}

//利用子女顶点在栈内存在时间小于父顶点
int finshTime[MaxVertexNum];
int count = 0;
for(int i=0;i<G.vexnum;i++){
  finshTime[i]=0;
}
void DFS(Graph G,int v){
  visited[v]=true;
  for(int w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
    if(!visited[w]){
      DFS(G,w);
    }
  }
  count++;
  finshTime[v]=count;
}

思考：如果存在回路，则不存在逆 拓扑排序序列，如何判断回路?

9. 关键路径

9.1. 概念

9.1.1. AOE网

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网 (Activity On Edge NetWork)

AOE网具有以下两个性质:

  1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始;
  2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。 另外，有些活动是可以并行进行的

在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始;

也仅有一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径⻓度的路径称为关键路径，而把关键路径上的活动称为关键活动

完成整个工程的最短时间就是关键路径的⻓度，若关键活动不能按时完成，则整个 工程的完成时间就会延⻓

9.1.2. 关键路径

事件vk的最早发生时间 ve(k)——决定了所有从 vk开始的活动能够开工的最早时间

事件vk的最迟发生时间 vl(k)——它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。

活动ai的最早开始时间e(i)——指该活动弧的起点所表示的事件的最早发生时间

活动ai的最迟开始时间 l(i)——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。

活动ai的时间余量 d(i)=l(i)-e(i)，表示在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间

若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即 l(i) = e(i)的活动 ai是关键活动

由关键活动组成的路径就是关键路径

9.2. 求关键路径的步骤

  1. 求所有事件的最早发生时间 ve( )

    按拓扑排序序列，依次求各个顶点的 ve(k):

    ve(源点) = 0

    ve(k) = Max{ ve(j) + Weight(vj, vk)}，vj为 vk 的任意前驱

  2. 求所有事件的最迟发生时间 vl( )

    按逆拓扑排序序列，依次求各个顶点的 vl(k):

    vl(汇点) = ve(汇点)

    vl(k) = Min{ vl(j) - Weight(vk, vj)}，vj为 vk 的任意后继

  3. 求所有活动的最早发生时间 e( )

    若边<vk, vj>表示活动 ai，则有 e(i) = ve(k)

  4. 求所有活动的最迟发生时间 l( )

    若边<vk, vj>表示活动 ai，则有 l(i) = vl(j) - Weight(vk, vj)

  5. 求所有活动的时间余量 d( )

    d(i)=l(i)-e(i)

d(i)=0的活动就是关键活动， 由关键活动可得关键路径

9.2.1. 所有事件的最早发生时间ve() - 拓扑

ve(源点) = 0

ve(k) = Max{ ve(j) + Weight(vj, vk)}

计算ve()可以用拓扑排序，最初ve[1…n]=0；若ve[j]+weight(vj,vk)>ve[k]，则ve[k]=ve[j]+weight(vj,vk)

拓扑序列：V1、V3、V2、V5、V4、V6

ve(1)=0

ve(3)=2

ve(2)=3

ve(5)=6

ve(4)=max{ve(2)+2,ve(3)+4}=6

ve(6)=max{ve(5)+1, ve(4)+2, ve(3)+3}=8

9.2.2. 求所有事件的最迟发生时间 vl( ) - 逆拓扑

vl(汇点) = ve(汇点)

vl(k) = Min{ vl(j) - Weight(vk, vj)}，vj为 vk 的任意后继

计算vl()用逆拓扑排序，最初vl[1…n]=ve[汇点]；若vl[j]-weight(vk,vj)<ve[k]，则ve[k]=ve[j]+weight(vk,vj)

逆拓扑序列：V6、V5、V4、V2、V3、V1

vl(6)=8

vl(5)=7

vl(4)=6

vl(2)=min{vl(5)-3, vl(4)-2}=4

vl(3)=min{vl(4)-4, vl(6)-3}=2

vl(1)=0

9.2.3. 求所有活动的最早发生时间 e( )

若边<vk, vj>表示活动 ai，则有 e(i) = ve(k)

V1 V2 V3 V4 V5 V6
ve(k) 0 3 2 6 6 8
vl(k) 0 4 2 6 7 8

求e()

a1 a2 a3 a4 a5 a6 a7 a8
e() 0 0 3 3 2 2 6 6

9.2.4. 求所有活动的最迟发生时间 l( )

若边<vk, vj>表示活动 ai，则有 l(i) = vl(j) - Weight(vk, vj)

V1 V2 V3 V4 V5 V6
ve(k) 0 3 2 6 6 8
vl(k) 0 4 2 6 7 8

求l()

a1 a2 a3 a4 a5 a6 a7 a8
e() 0 0 3 3 2 2 6 6
l() 1 0 4 4 2 5 6 7

9.2.5. 求所有活动的时间余量 d( )

d(i)=l(i)-e(i)

img

V1 V2 V3 V4 V5 V6
ve(k) 0 3 2 6 6 8
vl(k) 0 4 2 6 7 8

求d()

a1 a2 a3 a4 a5 a6 a7 a8
e() 0 0 3 3 2 2 6 6
l() 1 0 4 4 2 5 6 7
d() 1 0 1 1 0 3 0 1

关键活动：a2、a5 、a7

关键路径：V1 —> V3 —> V4 —>V6

9.3. 关键活动、关键路径的特性

若关键活动耗时增加，则整个工程的工期将增⻓

缩短关键活动的时间，可以缩短整个工程的工期

当缩短到一定程度时，关键活动可能会变成非关键活动

可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工 期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的

本文结束  感谢您的阅读
  • 本文作者： Wang Ting
  • 本文链接： /zh-CN/2021/02/08/数据结构-图/
  • 发布时间： 2021-02-08 22:54
  • 更新时间： 2023-04-15 16:16
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！