有向图和无向图#xff1a;

条边即任意两个顶点之间都有直接相连的边则称此图为无向完全图。

在有

如下图

在有向图中顶点的度等于该顶点的入度与出度之和顶点的入度是以该顶点为终点的边的条数顶点的出度是以该顶点为起点的边的条数。

在无向图中顶点的度等于与该顶点相关联的边的条数同时也等于该顶点的入度和出度。

路径与路径长度

的路径。

对于不带权的图一条路径的长度是指该路径上的边的条数对于带权的图一条路径的长度是指该路径上各个边权值的总和。

带权图示例

若路径上的各个顶点均不相同则称这样的路径为简单路径。

若路径上第一个顶点与最后一个顶点相同则称这样的路径为回路或环。

如下图

是连通的如果图中任意一对顶点都是连通的则称此图为连通图。

在有向图中若每一对顶点vi

之间都存在一条从vi到vj

交通网络图中的每个顶点表示一个地点图中的边表示这两个地点之间是否有直接相连的公路边的权值可以是这两个地点之间的距离、高铁时间等。

网络设备拓扑图中的每个顶点表示网络中的一个设备图中的边表示这两个设备之间是否可以互传数据边的权值可以是这两个设备之间传输数据所需的时间、丢包的概率等。

社交网络图中的每个顶点表示一个人图中的边表示这两个人是否互相认识边的权值可以是这两个人之间的亲密度、共同好友个数等。

关于有向图和无向图

交通网络对应的图可以是有向图也可以是无向图无向图对应就是双向车道有向图对应就是单向车道。

网络设备拓扑对应的图通常是无向图两个设备之间有边表示这两个设备之间可以互相收发数据。

社交网络对应的图可以是有向图也可以是无向图无向图通常表示一些强社交关系比如QQ、微信等一定互为好友有向图通常表示一些弱社交关系比如微博、抖音不一定互相关注。

在交通网络中根据最短路径算法计算两个地点之间的最短路径根据最小生成树算法得到将各个地点连通起来所需的最小成本。

在社交网络中根据广度优先搜索得到两个人之间的共同好友进行好友推荐根据入边表和出边表得知有哪些粉丝以及关注了哪些博主。

条边而图中边的数量不取决于顶点的数量。

树通常用于存储数据并快速查找目标数据而图通常用于表示某种场景。

邻接矩阵

用一个数组存储顶点集合顶点所在位置的下标作为该顶点的编号所给顶点可能不是整型。

用一个二维数组matrix存储边的集合其中matrix[i][j]

表示编号为

对于不带权的图两个顶点之间要么相连要么不相连可以用0和1表示m

jmatrix[i][j]

的两个顶点相连为0表示不相连。

对于带权的图连接两个顶点的边会带有一个权值可以用这个权值来设置对应matrix[i][j]

的值如果两个顶点不相连则使用不会出现的权值进行设置即可图中为无穷大。

对于无向图来说顶点

和顶点

相连因此无向图对应的邻接矩阵是一个对称矩阵即matrix[i][j]

matrix[j][i]

邻接矩阵适合存储稠密图因为存储稠密图和稀疏图时所开辟的二维数组大小是相同的因此图中的边越多邻接矩阵的优势就越明显。

邻接矩阵能够

O(1)

邻接矩阵不适合查找一个顶点连接出去的所有边需要遍历矩阵中对应的一行该过程的时间复杂度是O(N)其中

邻接矩阵所需成员变量

用于存储顶点集合顶点所在位置的下标作为该顶点的编号。

映射关系vIndexMap

用于建立顶点与其下标的映射关系便于根据顶点找到其对应的下标编号。

邻接矩阵matrix

表示编号为

无向图居多。

在构造函数中完成顶点集合的设置并建立各个顶点与其对应下标的映射关系同时为邻接矩阵开辟空间将矩阵中的值初始化为MAX_W

表示刚开始时各个顶点之间均不相连。

提供一个接口用于添加边在添加边时先分别获取源顶点和目标顶点对应的下标编号然后再将邻接矩阵中对应位置设置为边的权值如果图为无向图则还需要在邻接矩阵中添加目标顶点到源顶点的边。

在获取顶点对应的下标时先在vIndexMap

中进行查找如果找到了对应的顶点则返回该顶点对应的下标编号如果没有找到对应的顶点则说明所给顶点不存在此时可以抛出异常。

代码如下

invalid_argument(不存在的顶点);return

-1;}}//添加边void

//获取源顶点和目标顶点的下标_matrix[srci][dsti]

weight;

//添加从目标顶点到源顶点的边}}//打印顶点集合和邻接矩阵void

print()

接口用于打印顶点集合和邻接矩阵。

后续图的相关算法都会以邻接矩阵为例进行讲解因为一般只有比较稠密的图才会存在最小生成树和最短路径的问题。

邻接表

用一个数组存储顶点集合顶点所在的位置的下标作为该顶点的编号所给顶点可能不是整型。

用一个出边表存储从各个顶点连接出去的边出边表中下标为

的顶点连接出去的边。

用一个入边表存储连接到各个顶点的边入边表中下标为

如下图

出边表和入边表类似于哈希桶其中每个位置存储的都是一个链表出边表中下标为

的顶点的入度。

在实现邻接表时一般只需要用一个出边表来存储从各个顶点连接出去的边即可因为大多数情况下都是需要从一个顶点出发找与其相连的其他顶点所以一般不需要存储入边表。

邻接表适合存储稀疏图因为邻接表存储图时开辟的空间大小取决于边的数量图中边的数量越少邻接表存储边时所需的内存空间就越少。

邻接表适合查找一个顶点连接出去的所有边出边表中下标为

邻接表不适合确定两个顶点是否相连需要遍历出边表中源顶点对应位置的链表该过程的时间复杂度是

O(E)

weight):_dsti(dsti),_weight(weight),_next(nullptr){}};

说明一下

用于存储顶点集合顶点所在位置的下标作为该顶点的编号。

映射关系vIndexMap

用于建立顶点与其下标的映射关系便于根据顶点找到其对应的下标编号。

邻接表出边表linkTable

无向图居多。

在构造函数中完成顶点集合的设置并建立各个顶点与其对应下标的映射关系同时为邻接表开辟空间将邻接表中的值初始化为空指针表示刚开始时各个顶点之间均不相连。

提供一个接口用于添加边在添加边时先分别获取源顶点和目标顶点对应的下标编号然后在源顶点对应的链表中头插一个边结点如果图为无向图则还需要在目标顶点对应的链表中头插一个边结点。

代码如下

invalid_argument(不存在的顶点);return

-1;}}//添加边void

//获取源顶点和目标顶点的下标//添加从源顶点到目标顶点的边Edge*

sdEdge

_linkTable[srci];_linkTable[srci]

sdEdge;if

_linkTable[dsti];_linkTable[dsti]

print()

图的遍历指的是遍历图中的顶点主要有广度优先遍历和深度优先遍历两种方式。

广度优先遍历

广度优先遍历又称BFS其遍历过程类似于二叉树的层序遍历从起始顶点开始一层一层向外进行遍历。

如下图

广度优先遍历需要借助一个队列和一个标记数组利用队列先进先出的特点实现一层一层向外遍历利用标记数组来记录各个顶点是否被访问过。

刚开始时将起始顶点入队列并将起始顶点标记为访问过然后不断从队列中取出顶点进行访问并判断该顶点是否有邻接顶点如果有邻接顶点并且该邻接顶点没有被访问过则将该邻接顶点入队列并在入队列后立即将该邻接顶点标记为访问过。

代码如下

为了防止顶点被重复加入队列导致死循环因此需要一个标记数组当一个顶点被访问过后就不应该再将其加入队列了。

如果当一个顶点从队列中取出访问时才再将其标记为访问过也可能会存在顶点被重复加入队列的情况比如当图中的顶点B出队列时顶点C作为顶点B的邻接顶点并且还没有被访问过顶点C还在队列中此时顶点C就会再次被加入队列因此最好在一个顶点被入队列时就将其标记为访问过。

如果所给图不是一个连通图那么从一个顶点开始进行广度优先遍历无法遍历完图中的所有顶点这时可以遍历标记数组查看哪些顶点还没有被访问过对于没有被访问过的顶点则从该顶点处继续进行广度优先遍历直到图中所有的顶点都被访问过。

深度优先遍历

深度优先遍历又称DFS其遍历过程类似于二叉树的先序遍历从起始顶点开始不断对顶点进行深入遍历。

如下图

深度优先遍历可以通过递归实现同时也需要借助一个标记数组来记录各个顶点是否被访问过。

从起始顶点处开始进行递归遍历在遍历过程中先对当前顶点进行访问并将其标记为访问过然后判断该顶点是否有邻接顶点如果有邻接顶点并且该邻接顶点没有被访问过则递归遍历该邻接顶点。

代码如下

如果所给图不是一个连通图那么从一个顶点开始进行深度优先遍历无法遍历完图中的所有顶点这时可以遍历标记数组查看哪些顶点还没有被访问过对于没有被访问过的顶点则从该顶点处继续进行深度优先遍历直到图中所有的顶点都被访问过。

最小生成树

条边最小生成树指的是一个图的生成树中总权值最小的生成树。

连通图中的每一棵生成树都是原图的一个极大无环子图从其中删去任何一条边生成树就不再连通在其中引入任何一条新边都会形成一条回路。

说明一下

对于各个顶点来说除了第一个顶点之外其他每个顶点想要连接到图中至少需要一条边使其连接进来所以由

n个顶点和

条边。

对于生成树来说图中的每个顶点已经连通了如果再引入一条新边那么必然会使得被新边相连的两个顶点之间存在一条直接路径和一条间接路径即形成回路。

最小生成树是图的生成树中总权值最小的生成树生成树是图的最小连通子图而连通图是无向图的概念有向图对应的是强连通图所以最小生成树算法的处理对象都是无向图。

条边不能构成回路。

构造最小生成树的算法有Kruskal算法和Prim算法这两个算法都采用了逐步求解的贪心策略。

Kruskal算法

个顶点、不含任何边的图作为最小生成树对原图中的各个边按权值进行排序。

每次从原图中选出一条最小权值的边将其加入到最小生成树中如果加入这条边会使得最小生成树中构成回路则重新选择一条边。

按照上述规则不断选边当选出n−1

动图演示

根据原图设置最小生成树的顶点集合以及顶点与下标的映射关系开辟最小生成树的邻接矩阵空间并将矩阵中的值初始化为

MAX_W

表示刚开始时最小生成树中不含任何边。

遍历原图的邻接矩阵按权值将原图中的所有边添加到优先级队列小堆中为了避免重复添加相同的边在遍历原图的邻接矩阵时只应该遍历矩阵的一半。

使用一个并查集来辅助判环操作刚开始时图中的顶点各自为一个集合当两个顶点相连时将这两个顶点对应的集合进行合并使得连通的顶点在同一个集合这样通过并查集就能判断所选的边是否会使得最小生成树中构成回路如果所选边连接的两个顶点本就在同一个集合那么加入这条边就会构成回路。

使用count

和totalWeight

时则停止选边此时可以将最小生成树的总权值作为返回值进行返回。

每次选边时从优先级队列中获取一个权值最小的边并通过并查集判断这条边连接的两个顶点是否在同一个集合如果在则重新选边如果不在则将这条边添加到最小生成树中并将这条边连接的两个顶点对应的集合进行合并同时更新count

totalWeight

edge._weight;}};//获取当前图的最小生成树Kruskal算法W

Kruskal(GraphV,

_vertexs.size();//设置最小生成树的各个成员变量minTree._vertexs

_vertexs;

//设置最小生成树的顶点集合minTree._vIndexMap

_vIndexMap;

//设置最小生成树顶点与下标的映射minTree._matrix.resize(n,

vectorW(n,

//开辟最小生成树的二维数组空间priority_queueEdge,

vectorEdge,

minHeap.top();minHeap.pop();int

srci

//边的源顶点和目标顶点不在同一个集合minTree._addEdge(srci,

dsti,

//合并源顶点和目标顶点对应的集合count;totalWeight

weight;cout

//边的源顶点和目标顶点在同一个集合加入这条边会构成环cout

成环:

在获取图的最小生成树时会以无参的方式定义一个最小生成树对象然后用原图对象调用上述Kruskal函数通过输出型参数的方式获取原图的最小生成树由于我们定义了一个带参的构造函数使得编译器不再生成默认构造函数因此需要通过default关键字强制生成Graph类的默认构造函数。

一条边包含两个顶点和边的权值可以定义一个Edge结构体来描述一条边结构体内包含边的源顶点和目标顶点的下标以及边的权值在使用优先级队列构造小堆结构时需要存储的对象之间能够支持

运算符进行重载将其重载为边的权值的比较。

当选出的边不会构成回路时需要将这条边插入到最小生成树对应的图中此时已经知道了这条边的源顶点和目标顶点对应的下标可以在Graph类中新增一个_addEdge子函数该函数支持通过源顶点和目标顶点的下标向图中插入边而Graph类中原有的addEdge函数可以复用这个_addEdge子函数。

最小生成树不一定是唯一的特别是当原图中存在很多权值相等的边的时候比如对于动图中的图来说将最小生成树中的bc

边换成

边也是一棵最小生成树。

上述代码中通过优先级队列构造小堆来依次获取权值最小的边你也可以通过其他排序算法按权值对边进行排序然后按权值从小到大依次遍历各个边进行选边操作。

Prim算法

个顶点、不含任何边的图作为最小生成树将图中的顶点分为两个集合forest

forest

集合的所有边中选出一条权值最小的边将其加入到最小生成树中由于选出来的边对应的两个顶点一个属于forest

集合另一个属于

最短路径问题从带权有向图中的某一顶点出发找出一条通往另一顶点的最短路径最短指的是路径各边的权值总和达到最小最短路径可分为单源最短路径和多源最短路径。

单源最短路径指的是从图中某一顶点出发找出通往其他所有顶点的最短路径而多源最短路径指的是找出图中任意两个顶点之间的最短路径。

根据原图设置最小生成树的顶点集合以及顶点与下标的映射关系开辟最小生成树的邻接矩阵空间并将矩阵中的值初始化为

MAX_W

集合中并将所有从起始顶点连接出去的边加入优先级队列小堆这些边就是刚开始时连接

forest

时则停止选边此时将最小生成树的总权值作为返回值进行返回。

每次选边时从优先级队列中获取一个权值最小的边将这条边添加到最小生成树中并将这条边的目标顶点加入

forest

的值。

此外还需要将从这条边的目标顶点连接出去的边加入优先级队列但是需要保证加入的边的目标顶点不能在

forest

集合的边就会构成回路。

需要注意的是每次从优先级队列中选出一个权值最小的边时还需要保证选出的这条边的目标顶点不在forest

集合中避免构成回路。

虽然向优先级队列中加入边时保证了加入的边的目标顶点不在forest

集合中但经过后续不断的选边可能会导致之前加入优先级队列中的某些边的目标顶点也被加入到了forest

count

edge._weight;}};//获取当前图的最小生成树Prim算法W

Prim(GraphV,

_vertexs.size();//设置最小生成树的各个成员变量minTree._vertexs

_vertexs;

//设置最小生成树的顶点集合minTree._vIndexMap

_vIndexMap;

//设置最小生成树顶点与下标的映射minTree._matrix.resize(n,

vectorW(n,

//优先级队列小堆//将从起始顶点连接出去的边加入优先级队列for

(int

MAX_W)minHeap.push(Edge(starti,

count

minHeap.top();minHeap.pop();int

srci

//边的目标顶点还没有被加入到forest集合中//将从目标顶点连接出去的边加入优先级队列for

(int

//加入的边的目标顶点不能在forest集合中minHeap.push(Edge(dsti,

_matrix[dsti][i]));}minTree._addEdge(srci,

dsti,

//将边的目标顶点加入forest集合count;totalWeight

weight;cout

//边的目标顶点已经在forest集合中加入这条边会构成环cout

成环:

Prim算法构造最小生成树的思想在选边时是不需要判环但上述利用优先级队列实现的过程中仍需判环如果在每次选边的时候能够通过某种方式从连接forest

集合和remain

集合的所有边中选出权值最小的边那么就无需判环但这两个集合中的顶点是不断在变化的每次选边时都遍历连接两个集合的所有边该过程的时间复杂度较高。

Kruskal算法本质是一种全局的贪心每次选边时都是在所有边中选出权值最小的边而Prim算法本质是一种局部的贪心每次选边时是从连接

forest

最短路径问题从带权有向图中的某一顶点出发找出一条通往另一顶点的最短路径最短指的是路径各边的权值总和达到最小最短路径可分为单源最短路径和多源最短路径。

单源最短路径指的是从图中某一顶点出发找出通往其他所有顶点的最短路径而多源最短路径指的是找出图中任意两个顶点之间的最短路径。

单源最短路径-Dijkstra算法

中的顶点是尚未确定从源顶点到该顶点的最短路径的顶点。

每个顶点都有一个估计值表示从源顶点到该顶点的可能最短路径长度每次从集合Q

中并对该顶点连接出去的顶点的估计值和前驱顶点进行松弛更新。

按照上述步骤不断从集合

中此时通过各个顶点的估计值就可以得知源顶点到该顶点的最短路径长度通过各个顶点的前驱顶点就可以得知最短路径的走向。

动图演示

数组来记录从源顶点到各个顶点的最短路径长度估计值初始时将源顶点的估计值设置为权值的缺省值比如int就是0表示从源顶点到源顶点的路径长度为0将其余顶点的估计值设置为MAX_W表示从源顶点暂时无法到达其他顶点。

使用一个PathparentPath

数组来记录到达各个顶点路径的前驱顶点初始时将各个顶点的前驱顶点初始化为-1表示各个顶点暂时只能自己到达自己没有前驱顶点。

使用一个bool

集合中初始时所有顶点均不在S

数组中存储的就是从源顶点到各个顶点的最短路径长度parentPath

数组中存储的就是从源顶点到各个顶点的最短路径的前驱顶点通过不断查找各个顶点的前驱顶点最终就能得到从源顶点到各个顶点的最短路径。

代码如下

{public://获取单源最短路径Dijkstra算法void

Dijkstra(const

//各个顶点的估计值初始化为MAX_WparentPath.resize(n,

-1);

//将Q集合中的n个顶点全部加入到S集合//从集合Q中选出一个估计值最小的顶点W

minW

//将选出的顶点加入到S集合//对u连接出去的顶点进行松弛更新for

(int

//更新路径的前驱顶点}}}}//打印最短路径及路径权值void

printShortPath(const

//源顶点的前驱顶点为-1path.push_back(cur);cur

parentPath[cur];}reverse(path.begin(),

path.end());

的最短路径因此可以通过存储前驱顶点的方式来表示从源顶点到各个顶点的最短路径。

Dijkstra算法每次需要选出一个顶点并对其连接出去的顶点进行松弛更新因此其时间复杂度是

(N2)

的最短路径。

因为图中所有边的权值非负使用Dijkstra算法的前提所以对于估计值最小的顶点

来说其估计值不可能再被其他比它估计值更大的顶点松弛更新得更小因此顶点

在加入集合

的估计值和前驱顶点进行松弛更新。

Bellman-Ford算法根据路径的终边来进行松弛更新但是仅对图中的边进行一次遍历可能并不能正确更新出最短路径最坏的情况下需要对图中的边进行

n−1

数组来记录从源顶点到各个顶点的最短路径长度估计值初始时将源顶点的估计值设置为权值的缺省值比如int就是0表示从源顶点到源顶点的路径长度为0将其余顶点的估计值设置为MAX_W表示从源顶点暂时无法到达其他顶点。

使用一个

parentPath

数组来记录到达各个顶点路径的前驱顶点初始时将各个顶点的前驱顶点初始化为-1表示各个顶点暂时只能自己到达自己没有前驱顶点。

对图中的边进行

n−1

。

再对图中的边进行一次遍历尝试进行松弛更新如果还能更新则说明图中带有负权回路无法找到最短路径

//邻接矩阵

{public://获取单源最短路径BellmanFord算法bool

BellmanFord(const

//各个顶点的估计值初始化为MAX_WparentPath.resize(n,

-1);

//本轮没有更新过不必进行后续轮次的更新break;}}//更新n-1轮后如果还能更新则说明带有负权回路for

(int

Bellman-Ford算法是暴力求解可以解决带有负权边的单源最短路径问题。

负权回路指的是在图中形成回路的各个边的权值之和为负数路径每绕一圈回路其权值都会减少导致无法找到最短路径由于最多需要进行n−1

n−1

轮松弛更新后再进行一轮松弛更新如果还能进行更新则说明带有负权回路。

Bellman-Ford算法需要对图中的边进行

O(N×E)由于这里是用邻接矩阵实现的遍历图中的所有边的时间复杂度是O(N2)所以上述代码的时间复杂度是O(N3)空间复杂度是O(N)。

为什么最多进行n−1

如果形成回路的各个边的权值之和为负数则该回路为负权回路找不到最短路径。

如果形成回路的各个边的权值之和为非负数则多走这个回路是“徒劳”的可能会使得路径长度变长。

在每一轮松弛过程中后面路径的更新可能会影响到前面已经更新过的路径比如使得前面已经更新过的路径的长度可以变得更短或者使得某些源顶点之前不可达的顶点变得可达但每一轮松弛至少能确定最短路径中的一条边如果图中有n

条边因此最多需要进行n−1

对于上述图来说Bellman-Ford算法在第一轮松弛的时候只能更新出E−D

D−C

由于只有当前轮次进行过更新才有可能会影响其他路径因此在代码中使用update

标记每轮松弛算法是否进行过更新如果没有进行过更新则无需进行后面轮次的更新。

Bellman-Ford算法还有一个优化方案叫做SPFAShortest

Path

Algorithm其用一个队列来维护可能需要松弛更新的顶点避免了不必要的冗余计算大家可以自行了解。

Floyd-Warshall算法解决的是任意两点间的最短路径的算法其考虑的是路径的中间顶点对于从顶点

到顶点

的估计值和前驱顶点进行松弛更新。

Floyd-Warshall算法本质是一个简单的动态规划就是判断从顶点

到顶点

二维数组来记录从各个源顶点到各个顶点的最短路径长度的估计值vvDist[i][j]

表示从顶点

的最短路径长度的估计值初始时将二维数组中的值全部初始化为MAX_W表示各个顶点之间暂时无法互通。

使用一个vvParentPath

二维数组来记录从各个源顶点到达各个顶点路径的前驱顶点初始时将二维数组中的值全部初始化为-1表示各个顶点暂时只能自己到自己没有前驱顶点。

根据邻接矩阵对vvDist

和vvParentPath

的值设置为权值的缺省值比如int就是0表示自己到自己的路径长度为0。

依次取各个顶点

i−j

{public://获取多源最短路径FloydWarshall算法void

vvDist,

_vertexs.size();vvDist.resize(n,

vectorW(n,

//任意两个顶点直接的路径权值初始化为MAX_WvvParentPath.resize(n,

vectorint(n,

//各个顶点的前驱顶点初始化为-1//根据邻接矩阵初始化直接相连的顶点for

(int

//存在i-k和k-j的路径并且这两条路径的权值之和小于当前i-j路径的权值vvDist[i][j]

vvDist[i][k]

//松弛更新出更小的路径权值vvParentPath[i][j]

vvParentPath[k][j];

//更小路径的前驱顶点}}}}}private:vectorV

_vertexs;

Bellman-Ford算法是根据路径的终边来进行松弛更新的而Floyd-Warshall算法是根据路径经过的中间顶点来进行松弛更新的因为根据Bellman-Ford算法中的dist

只能得知从指定源顶点到某一顶点的路径权值而根据Floyd-Warshall算法中的vvDist

可以得知任意两个顶点之间的路径权值。

Floyd-Warshall算法的时间复杂度是O(N3)空间复杂度是O(N2)虽然求解多源最短路径也可以以图中不同的顶点作为源顶点去调用Dijkstra算法或Bellman-Ford算法但Dijkstra算法不能解决带负权的图Bellman-Ford算法调用