判定大型图中可到达性的随机区间标记索引

提出一种基于随机区间标记理论的可到达判定的方法 RIABG,它可以有效地处理非常大型的图,并且具有良好的可扩展性。RIABG具有线性的检索时间和空间复杂度,查询时间可以是常数时间,也可以根据图的大小而进行线性变化。真实数据集上的实验表明,RIABG可以有效处理大规模有向图的可达性判定问题。