由疫情出行延申到有关地图的计算机算法

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

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

但是比较让人揪心的是，最近又有了 2 次疫情反弹。浙江绍兴，很不巧就在笔者老家——浙江嘉兴的边上。然后我有几个比较要好的大学同学就在西安工作，现在西安也是因为疫情被封城了。

从大的角度来说，疫情对人和社会都有非常大的坏处，希望能尽早结束疫情；从我个人的角度来说，这下不得不担忧起我的春节计划。本想在回家（浙江）之前去见一见朋友，这下感觉两地都进出非常困难。也是非常希望疫情能够尽快结束。

当然目前来看趋势还是稳中带好。落笔时，此时浙江的确诊新增只有一例，基本已经阻断了疫情的传播；西安方面，快速开展多个核酸检测点，并且控制出行，防止再次传播。我认为国家关于解决这方面问题的经验还是非常充分，也对本次疫情的处理充满信心。

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

（本文讨论的疫情相关问题只为引申出算法知识，不含任何额外拓展含义。）

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

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

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

点——仅表示地点。

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

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

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

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

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

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