可视化图的基本算法

0. About

关于图的基本表示与基本算法,包括图的邻接表和邻接矩阵表示法;图的广度优先(BFS)与深度优先(DFS)搜索算法;最小权生成树问题的 Kruskal 算法与 Prim 算法;单源最短路径的 Dijkstra 算法。

1. 邻接表与邻接矩阵表示

邻接表表示法就是将图的每个节点保存在数组中,每个节点指向与之相邻的节点所组成的链表:

邻接表无向图

邻接表有向图

邻接矩阵表示法则是用一个 N 阶矩阵来表示,其中任意两个节点所对应的矩阵中的值为0或1表示两个节点是否相连通:

这两种表示方法都可以很容易地扩展为加权图,对于比较稀疏的图(定点数远大于边的数量)通常采用邻接表表示法,后面涉及到的算法均采用邻接表表示法。

2. 广度优先搜索与深度优先搜索

广度优先搜索就是按层遍历树时用到的思想,即先尽可能多地访问直接相连的节点,再向深处延伸,因此需要使用队列存储访问过的节点。

返回的 parent 保存了每个被访问节点的上一个节点,可以通过递归找出访问路径:

深度优先搜索则是先尽可能深远地搜索每一个相连通的节点,因此可以使用栈结构或递归的方式进行搜索:

3. 最小生成树

最小生成树实际上是“最小权值生成树”的缩写,与后面的单源最短路径问题一样,都是基于加权图的算法,因此需要先定义加权图的邻接表表示法:

最小生成树问题是指在给定的加权图中选择部分边,满足所有节点可以互相连通(即可以生成原有的图)同时所有边的权值之和最小。

Kruskal 算法首先将所有节点看作是一群孤立的树(即森林),然后将所有边按照权值存入优先队列,之后依次取出权值最小的边,并检查这个边的两个节点是否已经在同一棵树上,如果不是则将两点所在树合二为一。这里的森林和树通过集合进行操作。

对结果中的边进行染色标记:

Prim 算法与后面的 Dijkstra 算法有些类似,保存一个 k[node]node 与最小生成树中所有节点之间最小权值,然后从起点开始,以 k[node] 为键存入优先队列,然后从队列中依次取出的最小元素,找到与树外相邻节点的最小权值,并将其纳入树中。

这里为区分树内树外可以直接检查优先队列,Python 中的优先队列实际上就是对最小堆的简单封装,本质上还是一个列表,因此我们可以直接利用 heapq 进行改造获得一个可查询的优先队列:

返回结果为一颗父指针树,也可以基于此对边进行染色:

4. 单源最短路径问题

单源最短路径问题是指从给定节点出发到剩余所有节点的加权最短路径,以加权有向图为例:

Dijkstra 算法同样从起点开始构建最短路径,将所有节点与最短路径之间的距离作为键值存入优先队列,依次选择队列中的最小值,并与所有邻接点进行比较,看是否通过该点将其纳入最短路径是权值最小的:

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

4 4 收藏 3 评论

关于作者:Yusheng

关注微信公众号 PyHub! 个人主页 · 我的文章 · 24 ·   

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部