本文包含了图的基本概念

1.相关概念

1.1 无/有向

无向图：每一个顶点之间的连线没有方向

有向图：连线有方向（类似离散数学的二元关系 <A,B>代表从A到B的边，有方向）

1
<A,B>中A为始点，B为终点

在无向图中，(V,U)和(U,V)是同一条边

1.2 顶点和边

图中的节点叫做顶点。

顶点之间的线条就是边，表示事物与事物之间的关系。

image-20221203152531855

1.3 自回路/多重图

image-20221203152631926

1.4 完全图

图中每一个顶点都有连线（有最多的边数）就叫做完全图

设顶点为N个

  • 无向完全图中n(n-1)/2条边
  • 有向完全图中n(n-1)条边

1.5 邻接与关联

无向图中(u,v)是一条边

  • 顶点u和v邻接
  • 边(u,v)与顶点u和v相关联

1.6 子图

image-20221203153003325

图中G3是G1的子图，G4是G2的子图

简单说来，就是子图是原图的一部分，包括顶点、边（注意方向）都是原图中的一部分

1.6 路径

路径是顶点序列

路径是一个节点到另外一个节点需要经过的边

  • 路径长度：路径上边的数目
  • 简单路径：除起点、终点可以相同外，路径中其余顶点不相同
  • 回路：起点和重点相同的简单路径

1.7 连通图

两个顶点之间只要有路径，那就是连通的

  • 连通图：无向图中任意两点之间都有路径，那么就是一个连通图
  • 连通分量：无向图的极大连通子图

image-20221203153649688

注意，虽然连通分量被称为“极大连通子图”，但它并不是节点最多的哪一个。比如上图中的G2和G3都是极大连通子图。

  • 强连通图：有向图中，如果两个顶点之间U和V之间有U到V的路径，那就一定有从V到U的路径
  • 强连通分量：有向图的极大联通子图

image-20221203154021923

强连通图G1的极大强连通分量就是它自己（只有非强连通图才有多个强连通分量）

上图中G2就不是强联通图，因为4节点没有入边（也就没有节点能到4）

  • 第三图的上半部分并非G1的强连通分量，但是是G2的强力连通分量。
  • 同时，单独的4顶点也是一个强连通分量（单独顶点都是）

1.7 顶点的度

度：与该顶点相关联的边的数目

  • 入度：射入v的边的数目
  • 出度：从v射出去的边的数目

1.8 生成树

生成树包含图中的所有顶点，但是只有足够构成一颗树的n-1条边

  • 因为n-1条边再加上一条就会构成回路
  • 生成树中不包含回路

1.9 网

给图中的每条边都添加上权值，带权的图称为网

2.表示法

2.1 邻接矩阵

用二维数组来表示每个顶点之间的关系（矩阵）

image-20221203162700284

优缺点

优点

  • 便于判断两个顶点之间是否有边，可以直接根据下标判断，O(1)
  • 便于计算各个顶点的度
    • 无向图：第i行元素之和就是顶点i的度（前提是用1来表示）
    • 有向图：第i行元素之和为顶点i的出度；第i列为入度

缺点

  • 如果节点多，边少，就会出现空间浪费
  • 无法方便地找到一个顶点和那一条边相连（需要遍历）
  • 对于无向图，也会出现空间浪费

2.2 邻接表

邻接表有些类似于哈希表的拉链法。每一个节点后面跟着一个单链表，用于存储与这个节点相连的节点。

在G2的有向图中，一般存储的是出度表，即从该节点出发的边。如果边有权值，则还需要存储权值

image-20221204134044713

优缺点

优点：

  • 可以快速找到一个节点和谁相连（出度）

缺点

  • 不便于判断两个顶点之间是否有边
  • 不便于计算有向图各个顶点的度（需要遍历所有节点）

关于第二个缺点，可以新增一个入度表（即一个出度表/一个入读表）来计算。但是这样会增加时空复杂度。

3.遍历

3.1 深度优先DFS

深度优先以递归为基本思路，从一个结点开始，递归向后遍历这个节点的单链表中的节点。

image-20221204134842519

为了避免同一个节点遍历多次，我们需要有一个bool数组来标识一个节点是否遍历过。如果遍历过，则把对应下标的值设定为true来标识

由于深度优先的递归部分只能遍历连通图。若出现了上图中非联通的情况，需要我们在外循环中重新遍历一下bool标识数组，确认所有节点都遍历完成。

如果漏了节点（就是没有和其他节点联通的独立节点）那么就以此节点开头再进行一次深度遍历。

image-20221204140840949

3.2 广度优先BFS

image-20221204140627539

广度优先遍历类似二叉树的层序遍历，依靠循环+队列来完成遍历

  • 入起始节点，打印起始节点的值
  • 出队头节点（第一次的时候是起始节点）往队列中入该节点单链表中的所有节点
  • 依此类推，出一个节点，就入这个节点单链表中的所有节点
  • 同样地用一个bool数组标识节点是否被访问。如果被访问了则跳过该节点
  • 也需要在队列循环结束后遍历一遍bool数组，确认所有节点都访问完毕。

image-20221204140819112

3.3 判断一个图是否连通

使用任何遍历方式，遍历完毕后检查bool数组

若有节点没有被访问，则说明是非连通图

4.拓扑排序

https://blog.musnow.top/posts/1720780208/

给定一个图，每次都选择一个无入度（没有入边）的节点加入序列中，并删除该节点的出边。最终得到的序列就是一个拓扑排序之后的序列。

注意，每次删除出边后，都可能形成新的无入度的节点。

因此，针对同一棵树的拓扑排序序列，可能有多种不同的情况

5.最小生成树算法

生成树的概念参考 1.8 生成树，最小生成树即让生成树中所有边的权值加起来最小

5.1 普里姆Prim

image-20221206164945471

如图中所示，我们先根据这个树的结构构造三个数组

  • nearest代表和这个节点最近的节点（默认为-1）
  • lowcost代表和这个节点最近节点的权值（默认为无穷大）
  • mark是一个bool数组，标识该节点是否已经加入到最小生成树

当我们每从图中取出一个节点的时候，就需要更新这三个表

如图，当我们取走0之后，就需要更新和0连通的三个节点，其中nearest代表刚刚删除掉的节点0，lowcost代表它们和0相连边的权值；同时要把mark中0改为true，表明0已经加入生成树了

image-20221206165820864

第二次选取的时候，遍历lowcost表，找到权值最小的边为(0,2)权值为1。此时就把2加入进去，并更新与2相连的节点3（注，必须要权值更小才需要更新）

image-20221206170707450

依次遍历，直到所有节点都加入了最小生成树（左下角的图）

image-20221206171723913

该算法的时间复杂度为O(N^2)，只与节点的数量N有关

5.2 克鲁斯卡尔Kruskal

image-20221206172343754

构建一个和原图一样的节点图（无边）在原图中查找权值最小的边，判断其节点是否已经相同，如果没有形成环，则加入到最小生成树的图中

判断是否成环可以通过并查集解决

如下图，先遍历所有边，发现(0,2)的权值最小，判断该边加入后并不会使生成树形成环，则加入该边

  • 下图中(0,2)之间的边1已经移动到了T图上
  • 同时将0和2加入到同一个并查集的合集内

image-20221206172624950

同理继续找权值最小的边，加入到生成树中。如下，将3边移动到右图。

image-20221206172822375

此时我们遇到了3条权值最小的边，权值都为5。此时可以随便加入一条边即可（不能使生成树成环）

如下图中(0,3)和(2,3)的边加入后会使图成环，不能选择该边

  • 并查集中0、2、3、5已经在一个集合中，此时判断(0,3)在一个集合，该边不能加入；(2,3)在一个集合中，该边不能加入

image-20221206172909839

应该选择(1,2)这条边，其不会让树成环

image-20221206173200557

此时所有边都已经连起来了，最小生成树生成成功

算法分析

image-20221206173648882

image-20221206173706988

该算法的时间复杂度为O(E*logE)，其中E为边的数目

6.最短路径

带权有向图中，把一条路径（仅考虑简单路径）上所经边的权值之和定义为该路径的路径长度

从源点到终点可能不止一条路径，把路径长度最短的那条路径称为最短路径

6.1 单源最短路径

思路有些类似并查集，path数组中存放的是每一个节点的上一条路径，若下标1处存放0，则代表是从0走到1。同时d数组中标识从0走到下标1的长度。

image-20221206184617517

把1加到s序列之后，发现0到节点2的路径长度缩短了，从原本的(0,2)的6变成了现在(0,1)+(1,2)的4+1=5，长度缩短，对应d数组中下标2处也需要更新

继续下去，直到U数组中没有节点，S数组中节点满，即可获得一个从0出发到任何节点的单源最短路径

6.1.1 狄克斯特拉算法Dijkstra

求解单源最短路径问题的算法

前提：给定一个带权有向图G和源点v，限定各边上的权值大于等于0

基于定理：最短路径上的顶点的最短路径就是该路径

理解：现有一条v到u的最短路径v->……->a->u，那么v到a的最短路径即为v->……->a

算法思路

把图G中的顶点集合V分成两部分：

第一部分，为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径v，……，u，就将u加入到集合S中，直到全部顶点都加入到S中，算法结束）

第二部分，为其余未求出最短路径的顶点集合（用U表示）

过程：

  1. 初始化：S只包含源点即S={v}，v的最短路径为0。U包含除v以外的其他顶点，U中顶点i距离为边上的权值（若v与i直接相连）或∞（v与i不是直接相连）

image-20221215202813428

  1. 从U中选取一个距离v最小的顶点u，把u加入S中（该选定的距离就是v到u的最短路径长度）

image-20221215203045922

image-20221215203110663

  1. 以u为新考虑的中间点，修改U中各顶点i的最短路径长度

若从源点v到顶点 i的最短路径长度（经过顶点u）比原来最短路径长度（不经过顶点u）短，则修改顶点 i的最短路径长度

image-20221215203341139

  1. 重复2、3步，直至所有顶点都包含在S中
代码设计

着重解决两个问题：

  1. 如何存放最短路径长度？

用一维数组d[i]存储。源点v默认，d[i]表示源点到顶点i的最短路径长度

如d[2]=12表示源点到顶点2的最短路径长度为12

  1. 如何存放最短路径？

用一维数组path[]存储。path数组中所存储的数组代表当前顶点在最短路径中的前驱顶点

如path[3]=1，表示在最短路径中，顶点3的前驱顶点是顶点1

算法演示

image-20221215204311623

这是初始化状态

发现数组d中顶点1距离源点距离最近，那么就将顶点1加入到S中

image-20221215204643536

这时，我们需要更新剩余点的最短路径长度和最短路径

显然，顶点2，3，4，5，6并不会都做更新。只有与顶点1直接相连的顶点才有可能会受影响。在上图中会受影响的为顶点2和顶点4

image-20221215204857064

原本顶点2的最短路径长度是6，最短路径是<0,2>。现在由于顶点1的引入，最短路径长度变为5，最短路径变为<0,1>,<1,2>

顶点4同理！

至此，就完成了一次顶点的引入。下面重复上述操作至所有顶点都在S中即可

下面是全过程：

image-20221215210605089

image-20221215210729969

image-20221215210949302

==总结一下：在更新d和path数组时，只有与本次引入S中的顶点i直接相连的后驱顶点才有可能发生改变，其余顶点是不可能变的==

现在我们利用d和path数组来求解最短路径长度和最短路径：

  • 求源点0到终点6的最短路径长度

即为d[6]的值，为16

  • 求0到6的最短路径

image-20221216102425727

从终点往源点找

时间复杂度

时间复杂度为 O(n2)