|
在图论中，可达性是指在图中从一个顶点到另一个顶点的容易程度。 如果存在一系列相邻顶点，则顶点s 可以到达顶点t （并且t 可也可以到达s），以s 为开头，以t结尾。
在无向图中，可以通过识别图的连接分量来确定所有顶点对之间的可达性。 当且仅当它们属于同一连通分量时，这种图中的任何一对顶点可以彼此到达。 可以在线性时间中识别无向图的连通分量。
用于确定可达性的算法分为两类：需要预处理的算法和不需要预处理的算法。
如果只有一个（或几个）数据需要查询，那么放弃使用更复杂的数据结构并直接计算可达性可能更有效。 这可以使用诸如广度优先搜索或迭代深化深度优先搜索的算法在线性时间完成。[1]
如果你将查询许多数据，那么可以使用更复杂的方法; 方法的选择取决于被分析的图的性质。 作为预处理时间和一些额外存储空间的交换，我们可以创建一个数据结构，然后它可以在任何一对顶点上进行可达性查询。
下面概述了三种不同的算法和数据结构。
Floyd-Warshall算法
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N)，空间复杂度为O(N*N)。
Thorup 算法
对于平面有向图，一种更快的方法是如Mikkel Thorup在2004年所提出的算法。计算复杂度为 ,其中 为增长速度非常缓慢的inverse-Ackermann函数。该算法还可以提供近似最短路径距离以及路由 信息。 Kameda算法
如果图形是平面的，非循环的，并且还表现出以下附加 属性，则可以使用由1975年的T.Kameda 提出的更快的预处理方法：所有0-indegree和所有0-outdegree顶点出现 （通常假设为外面），并且可以将该面的边界分割为两个部分，使得所有0个不等的顶点出现在一个部分上，并且所有的0度外的顶点出现在另一个部分上 （即两种类型的顶点不交替）。 |