基于二维拓扑数的可达性查询

1. 基本概念 在一个有向无环图中，可达性查询r(u, v)是指u到v是否有一条路径，当u到v存在一条路径时，r(u, v)返回true，即u到v可达；反之返回false，即不可达。 任意一个有向图均可转化为有向无环图，详细转化方法可参考（http://blog.csdn.net/woniu317/art

1. 基本概念

在一个有向无环图中，可达性查询r(u, v)是指u到v是否有一条路径，当u到v存在一条路径时，r(u, v)返回true，即u到v可达；反之返回false，即不可达。

任意一个有向图均可转化为有向无环图，详细转化方法可参考（http://blog.csdn.net/woniu317/article/details/23658301）。易得处于同一个强连通分量中的节点转换后成为了一个节点，当查询可达性的时候可以先转化为有向无环图中的结点再进行查询即可。因此所有的可达性查询只需要研究有向无环图。

2. 基本思想

对于任意一个图的任意一种拓扑序列进行分析可得：

若结点u到结点v可达，则必然有u的拓扑序号小于v的拓扑序号；也就是说当结点u的拓扑序号大于v的拓扑序号时，则u一定不可达v。

如图2-1所示，表2-1中T1列为图的一种拓扑序列。例如a到h可达，a的序号小于h的序号；g的序号大于h的序号，因此g不可达h，从图2-1中可验证。值得注意的是，即使u的序号小于v的序号，u也不一定可达v，例如结点a与b。

不难发现利用表2-1中的拓扑顺序会存在很多的不能修剪的结点对，比如（a，b），（a，g），（a，f）。即使换一种拓扑顺序也会出现同样的状况。因此，同时采用两种拓扑顺序进行修剪效果更佳。但如何求得两种拓扑顺序使得剪枝效果最好是NPC问题，因此采用一种近似的方式求得第二个拓扑序列。

图2-1 图G

表2-1 图2-1的拓扑序列

vc6szdjGy9DywdC1xLn9wsvQp7n7oaPNvDItMcv5x/O1xLXatv60zrXEzdjGy9DyusXI57HtMi0x1tBUMsHQy/nKvqGjPC9wPgo8cD7I9HW1vXa/ybTvo6zU8rHYyLvT0HW1xMG9uPbN2MbL0PK6xbfWsfC21NOm0KHT2na1xM3YxsvQ8rrFoaPNrNH5xOO38cP8zOKjrMj0dbXEwb249s3YxsvQ8rrFsru2vNCh09p2tcTN2MbL0PK6xaOs1PJ10ru2qLK7v8m073ahozwvcD4KPGgzPjMuIL/JtO/Q1LLp0a88L2gzPgo8cD6/ybTv0NSy6dGvssnTw8nutsjTxc/IsenA+rXEt73KvaOssunRr8H3s8zI5828My0xy/nKvqGjPC9wPgo8cCBhbGlnbj0="center">

图3-1 可达性查询流程图

参考论文

ReachabilityQueries in Very Large Graphs A Fast Refined Online Search Approach