图论算法在计算机科学中扮演着很重要的角色,它提供了对很多问题都有效的一种简单而系统的建模方式 |
概念
图由顶点(vertex, node)和边(edge)组成。顶点代表对象。我们可以给边赋予各种各样的属性,如权值(cost)。
图大体分为两种
1. 无向图
两个顶点间有连接,视为相邻。相邻顶点的序列称为路径。起点和终点重合的路径叫圈。任意两点间都有路径连接的图叫连通图。顶点连接的边数叫做这个顶点的度。没有圈的连通图就是树(tree)。
#####2. 有向图
入度,出度,没有圈的有向图叫DAG(Directed Acyclic Graph)。
对于每一个顶点给一个编号,第i号顶点叫做。那么存在从顶点到顶点的边时就有成立,这样的编号方式叫做拓扑序。
拓扑序
从 DAG 图中选择一个 没有前驱(即入度为0)的顶点并输出。
从图中删除该顶点和所有以它为起点的有向边。
重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。若当前图中不存在无前驱的顶点说明有向图中必存在环。
图的表示
稠密图用 邻接矩阵存储
稀疏图用 邻接表存储
邻接矩阵
邻接矩阵虽然好写,但是由于需要开一个二维数组,如果顶点数过大(一般不能超过1000)的题目便会超内存
代码实现:
- 复杂版本:
1 | /************************************************************************* |
这里要提到malloc函数
malloc函数是一种分配长度为num_bytes字节的内存块的函数,可以向系统申请分配指定size个字节的内存空间。malloc的全称是memory allocation,中文叫动态内存分配,当无法知道内存具体位置的时候,想要绑定真正的内存空间,就需要用到动态的分配内存。
返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定,void* 类型可以通过类型转换强制转换为任何其它类型的指针。
- 使用时一般要强制类型转换*
1 | MGraph Graph; |
- 简易版本:
1 | int G[maxn][maxn], Nv, Ne; |
邻接表(链式前向星)
代码实现:
- 简单版本
vector实现
stl是个好东西
1 | /************************************************************************* |
- 复杂版本
代码来自github
1 |
|
图的遍历
dfs算法(Depth First Search)
事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.
代码实现
1 | /************************************************************************* |
bfs算法(Breadth First Search)
广度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。可以类比树的层序遍历,一般由队列实现。
2018蓝桥杯c++A组
就是一道很经典的bfs
P1126 机器人搬重物
洛谷这道题,其实挺水的,结果卡了我半天的剪枝…果然还是鄙人太菜
1 | /************************************************************************* |
用结构体构造函数的话还是挺方便的
1 | struct node |
虽然后面发现这样也是等价的
1 | struct node |
最短路问题(以下算法模板已上传github)
单源最短路问题
Single-Source Shortest Paths (SSSP) problem
Bellman-Ford算法
- 使用邻接表比较方便
- 适用前提:没有负环(或称为负权值回路),因为有负环的话距离为负无穷。
- 若u->v是有向边,则d[v] <= d[u] + dis(u, v),这个操作称为松弛操作
- 优点:可以处理负权值,还可以发现负环
SPFA算法
SPFA的过程是BFS,它是不停扩展节点的。
本质Bellman-Ford算法的优化
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列优化,减少了不必要的冗余计算。
SPFA在形式上和BFS非常类似,不同的是BFS中一个点出了队列就不可能重新进入队列,但是SPFA中一个点可能在出队列之后再次被放入队列,也就是一个点松弛过其它的点之后,过了一段时间可能本身被松弛,于是要再次用来松弛其它的点,这样反复迭代下去。
spfa的队列优化
1 | /************************************************************************* |
Dijkstra算法(贪心思想)
迪杰斯特拉
哲学意义————发散思维
- 求图中给定两点v到u的最短路径,则计算v到所有其他点的最短路径,终能包含v到u的最短路径!
- 时间复杂度比Bellman-Ford小,但是无法处理负权值的情况
在稠密图中有不俗的表现.
基本思想
通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算)。
此外,引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
初始时,S中只有起点s;U中是除s之外的顶点,并且U中顶点的路径是”起点s到该顶点的路径”。然后,从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 然后,再从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 … 重复该操作,直到遍历完所有顶点。
怎么优化呢?
我会zkw线段树!
我会斐波那契堆!
我会堆!
会个鬼
我们可以用堆对dis数组进行维护,用$$O(\log_{2}n)$$的时间取出堆顶元素并删除,用$$O(\log_{2}n)$$遍历每条边,
总复杂度$$O((n+m)\log_{2}n)$$
例如:
用Dijkstra就会出错。
迪杰斯特拉的优先队列优化
1 | /************************************************************************* |
多源最短路问题
(Floyd-Warshall算法)
弗洛伊德算法
本质
动态规划
map[i,j]记录结点i到j的最短路径的距离,则
map[i,j] = min{map[i,k] + maxp[k,j], map[i,j]};
同时,map[n,n] == 0,存在负权值也适用
py贼简洁
1 | for k in range(self.V): |
其实是同一题hdu2544
1 | /************************************************************************* |
最小生成树
Minimum Spanning Tree
最小生成树是在一个给定的无向图
稠密图用prim,稀疏图用kruskal
Prim算法(bfs思想)
Kruskal算法
(以上图论算法参考《算法笔记》-图算法专题)