问题简介

    图论中的REACHABILITY问题，也就是可达性问题，是图论中非常基础的问题，这个问题我在本科的图论课程中也学过，复杂性课程上也讲了这个问题，更加细致得分析了算法的运行时间。一个图$G=(V,E)$由一个顶点集$V$和边集$E$组成，其中$V=\{1,2,\cdots,n\}$，$E=\{(i,j):i,j\in V\}$均为有限集，图的可达性问题是指给定一个图$G$和两个顶点$1,n\in V$，是否有一条从$1$到$n$的通路(也称为$path$)，这里的图定义为有向图，此问题显然为判定性问题。

可达性问题的算法

    可达性问题的算法并不复杂，具体流程如下，整个算法流程中，我们保存一个顶点集合$S$:

1. 初始时$S=\{1\}$，每个顶点或者已经被标记或者未被标记，这里点$i$被标记意味着在过去的某一时刻曾在$S$中或者目前正在$S$中。因此初始只有$1$被标记
2. 从$S$中选择一个顶点$i\in S$，并且$S\leftarrow S\backslash \{i\}$，然后找出从$i$出发的所有的边$E_i=\{(i,j):i,j\in E\}$，逐条检查，如果$j$未被标记，则标记，并且将$j$放入$S$中，如果$j$已经被标记，不做处理
3. 重复执行第2步的操作，直到$S=\emptyset$时终止，此时若点$n$被标记，则输出yes，否则输出no

    这个算法非常简单，显然，一个顶点被标记当且仅当存在一条从$1$到这个顶点的通路，因此该算法可以解决可达性问题，接下来要分析此算法的效率如何，是否一定可以终止。

    首先我们假设从$S$中选取元素，标记一个顶点以及判断一个顶点是否被标记等等，可在常数时间$t$内完成。$n$个点的图一般是用一个$n\times n$的邻接矩阵来描述的，当我们从$S$中确定了一个点之后，我们要判断与这个点相连接的点是否被标记，此时需要访问邻接矩阵的对应行，也就是$n$个值，$n$次操作，在这$n$次操作之后，集合$S$肯定要删去一个点，再加入一些新的点，且新的点与删去的点肯定不同，删去的点也不会再重新进入$S$，故集合$S$最多删除$n$个点，也就是$n$次操作最多进行$n$次，故该算法的时间损耗大约是$n(n+t)$，故此算法的时间复杂度是$O(n^2)$。
    下面分析其所用的空间资源，显然，只需要存储集合$S$和顶点的标记即可，由于$|S|\leq n$，故至多只有$n$个标记，因此该算法的空间复杂度为$O(n)$。

    显然可达性问题存在高效判定的算法。

赏

谢谢你请我喝冰露

支付宝

微信