有关地图的计算机算法

来源：成都少儿编程培训学院时间：2023/1/2 13:55:57

　　现在距离春节还有一个多月。

　　有句古话叫做：每逢佳节倍思亲。我现在确实也有种恨不得立马回家的冲动。

　　我们本次就以疫情下的出行，从计算机算法的角度，去做一些非常简单展现。当然设计到的算法语法内容会比较多，可能同时也比较简陋。希望读者多多包涵。

　　图的存储

　　首先我们要明确一个问题。地图是怎么表示的。一般来说，地图的表示方式多种多样，简单提炼一下，便是一个个的地点(点)和一条条的路径(边)。

　　所以我们可以用 n 个点和 m 条边来简单的描述一张图。具体的，点包含什么信息(有多少人，什么建筑等等)，边包含多少信息(道路宽度、长度、是否单行，速度上限等)还是需要根据具体问题具体分析。

　　今天就只看较简单的模型，假设因为疫情原因出现封区，封城，我想知道现在 2 个地点是否可以互相到达。

　　点——仅表示地点。

　　边——仅表现一条双向路径，连接 2 个点，表示这 2 个点互相可达。

　　在这种情况下，我们就可以用一种较简单的方式来经行图的存储——二维数组。

　　AUT UMN

　　判断连通

　　现在我们是明确知道了任意 2 个地点之间是否有边相连。那么进一步，怎么判断任意 2 个地点(x 和y)是否连通呢?

　　例如：1 连通 2;2 连通 3。虽然 1 和 3 没有直接边可以到达，但是 1 可以先到达 2，再到达 3。

　　方法其实比较多，有并查集维护连通性、直接搜索等等。本次也用较为简单和好理解的深搜/递归/洪水填充(floodfill)算法来解决。

　　我们利用数组给出发点 x 染色为1。

　　然后以 x 为触发点开始做递归深搜。

　　那么较终，只需要看目标点 y 和 x 的颜色是否相同即可。

　　这样就可以判断两点是否可达到。甚至于如果提前对整张图染色，那么之后每次询问都可以利用 color 数组在 O(1) 的时间内直接返回结果。

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/974/news/588839/违者必究！ 以上就是成都少儿编程培训学院 小编为您整理 有关地图的计算机算法的全部内容。