五一假期快到了，终于有时间写文章了😁。这篇文章启发于年前在工作中碰到的一个任务，其实是一个比较简单的算法题。有一次，业务方有个功能点需要我们支撑，大致意思就是给出几个实体（图谱数据中的实体），判断这几个实体之间是否存在某种联系，如果有孤立的实体，那么就是非关联的。针对这个问题，大致分析下，首先我们的数据底层是知识图谱数据库，这些实体以及实体与实体之间的关系构成了整个庞大的知识图谱，现在的目的就是从这张图谱中判断节点之间是否存在连接（直接或者间接），我们称之为图的连通性探测。
背景介绍
上面讲到，我们的数据底层是知识图谱数据库，而这些数据都是采用三元组形式存储的。针对图谱数据库，还对应的提供了一个图谱搜索服务，当我们输入关键字之后，就会返回我们我们想要的子图，包括不同的条件，比如1-hop，2-hop，同时还可以限制搜索范围，是搜实体还是搜属性，亦或是搜索关系。如下图所示（工作数据当然是看不到的，下图是自己用Neo4j构建的电影图谱数据），演员芭芭拉·赫希出演了《黑天鹅》电影，那么他们之间就存在一条关系，即一个三元组数据（芭芭拉·赫希，出演，黑天鹅），在这里面，演员和电影都是一个实体，只是实体类型不一样。所以当用户输入黑天鹅和芭芭拉赫希，同时我们将hop取值等于1，那么就会得到下面的这张子图。假设你想知道他们两是否存在直接联系，那么只需要判断两个节点是否存在关系即可，但是在实际情况里，我们往往想知道的是两个节点是否存在间接联系，如果不存在，则两者是没有关联的。
两个节点的关系
针对一个子图而言，如果两个节点存在一条边将两者连接起来，那么他们就是有直接关系，如果两个节点通过中间的一个节点将两者串起来，那么它们也是有关系的，这种关系视业务场景而定。在实际当中，我们往往会对搜索出来的子图做一个限制，比如刘德华和梁朝伟都演过《无间道》，他们是存在直接联系的，但是如果加上限制条件，比如说刘德华和张学友是否在同时出现在一部喜剧之中，或者伦理剧，那么结果肯定会不一样。所以这种关系，也是在特定业务场景下的关系。
连通性探测
针对上面这种场景，当我们输入两个关键字之后，我们可以得到一个子图，在得到这个子图之后，如果想要限定某种条件，我们还需要对结果数据进行删减，去掉不符合条件的节点和边，这一步称之为图的裁剪，最后留下的子图才是用来判断两个节点是否连通的真实子图。关于连通性的定义，在大学的时候，我们在数据结构课程中都学到过。假设给定一个子图，如果图中的任意两个节点都是连通的（直接或者间接），那么这个图就是连通的，我们称之为连通图，或者连通子图。
现在，我们碰到的场景是，给定一个子图，然后根据某种条件删掉一些节点和边，省下n个节点，m条边，要求是判断子图的n1（n1 < n） 个节点是否是连通的。是不是有点绕，如果是的话，请您回头在读一遍。换句话说，就是判断裁剪后的子图里某n1个节点是否位于一个连通子图中。
分析到这里，想必也可以知道要做的功能是什么意思了。其实方法也有多种，第一种就是从n1个节点中的某一个节点开始进行DFS遍历，当第一个连通子图遍历完之后，判断这n1个节点是否都在其中，如果有一个不再，那么他们就是非连通的。第二种就是随机的从某个节点开始遍历，当所有节点都遍历完之后，会得到s(s>=1)个连通子图，遍历过程中，我们将每个节点都打上连通子图的序号，表示属于第几个连通子图的节点，最后得到的s如果恒等于1，那么毫无疑问，这些节点就是连通的，如果大于1，那么就判断这n1个节点是否都属于同一个连通子图，如果是，则是连通的，如果否，则是非连通的。
方法出来了，那么代码应该怎么写呢？这里分享一种思路吧，具体的逻辑这里就不写了。我们在做图的遍历的时候，会常用到DFS和BFS，这两种算法的非递归实现在图的遍历中是非常重要和常用的，而且也会经常延伸到其他算法当中，其核心就在于借助了栈和队列作为辅助数据结构。比如DFS（深度优先遍历），借助队列实现。首先初始化的时候将第一个节点入队，然后循环判断，当队列不为空的时候，进行内部逻辑实现，首先队列的队首数据出队，然后将与队首节点有关联的第二和第三个节点入队，同时遍历第一个节点，接着重新回到循环体中判断队列是否为空，依次循环，直到辅助队列为空为止。如果是想计算出连通子图的数量，那么就设置一个辅助数组，下表表示节点编号，值为是否遍历过，初始化所有的节点都没有遍历，然后对数组的元素进行DFS遍历，如果遍历过的，就跳过，没有遍历过的就采用DFS进行遍历，最后统计使用DFS的次数，这个次数就是连通子图的个数。
结束语
当时在做这个时候，一开始是交给一个合作方的同事去弄，来来回回折腾了好几天，就是没做出来，原因是他对于图这种数据结构并不了解，不知道DFS，也不知道采用栈和队列作为辅助数据结构，最后还是得自己动手实现。之所以在这里提到众多工作中的这一话题，其实是想说数据结构的重要性。以前在学校的时候，潜意识的以为应该不会用到DFS和BFS这种算法，以及这些和图相关的东西，现在真的遇上了，才感到庆幸，有种柳暗花明又一村的舒适感。
好了，假期终于开始，祝大家五一节日快乐，明天开开心心的搞卫生，做大扫除吧！！！