本文包含了的基本概念

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)