标识强连通分量的入口和出口的技术

摘要

在此描述了有效识别强连通分量并同时识别入口、出口以及相应的边的图遍历系统。入口和出口节点可通过在识别强连通分量之后扫描每个节点来识别，但重新访问这些节点引起了不期望的开销。本图遍历系统在当正在识别强连通分量时在单次遍历中识别入口和出口。此外，本系统修改了用于一些应用的语义，使得单个节点独自不被认为是强连通分量。因此，本图遍历系统允许以可被应用于使用有向图作为数据结构的大量计算机软件问题的方式从强连通分量中有效识别入口和出口。

主权项

一种用于在图中标识强连通分量的同时标识入口和出口的计算机可执行方法，其特征在于，所述方法包括：接收待标识强连通分量、入口和出口的图数据结构的节点(310)；将所接收的节点的索引设置为递增值，当遇到图数据结构中所标识的节点时，所述递增值跟着所述节点的计数(320)；将所接收的节点的低链接值初始化为比图数据结构中的节点数目更大的数目(330)，其中低链接值跟踪通过跟着连接到节点的边可到达的其它节点的最低索引；将该节点与可能是强连通分量集的一部分的任何其它节点一起存储在临时储存设备中(340)；确定所接收的节点是否具有任何派生节点(350)；当确定所接收的节点具有派生节点时，处理所接收的节点的派生节点以确定每个派生节点其自身是否是强连通分量集的根(350)；以及如果节点索引等于节点低链接值(370)，将节点标识为强连通分量集的根(380)；以及将之前存储在临时储存设备中的节点移除，直至移除所接收的节点(395)，其中所移除的节点是一强连通分量集；其中以上步骤由至少一个处理器来执行。