设计流式算法验证有向图节点S是否为母顶点及输入读取次数

前置定义与约束 #

首先明确两个核心边界：

• 母顶点判定规则：有向图G=(V,E)中，若从节点S出发沿有向边可到达V中全部剩余节点，则S为G的母顶点；其等价表述为：反向图（所有边方向取反）中所有节点均可到达S。
• 流式算法约束：输入以(u, v)格式的有向边序列形式呈现，仅支持顺序遍历、不可随机跳读指定边；内存规模通常为节点数/边数的对数级，半流式场景下允许内存随节点数线性增长（远小于稠密图的边数规模）；单条边处理时间要求为常数级。

不同约束下的算法设计与遍历次数 #

1. 精确判定场景 #

不存在满足「严格对数内存+常数次遍历」的精确判定算法，这是由有向图可达性的通信下界决定的：如果内存不足以存储全量节点的可达状态，对抗式构造的边序列可以让算法无法判断远端节点是否可达。
工程上最常用的是半流式（允许为每个节点存储1比特可达状态，总内存O(|V|)）下的迭代遍历方案，具体逻辑如下：

• 初始化：创建布尔数组reachable，所有值初始化为false，仅设置reachable[S] = true；维护计数器total = 1，记录当前已确认可达的节点总数。
• 迭代遍历边流：
  • 每轮遍历开始前初始化本轮新增计数add = 0
  • 顺序读取每条边u -> v：如果reachable[u] == true且reachable[v] == false，则设置reachable[v] = true，add += 1
  • 若本轮add == 0，说明可达集已不再扩张，终止遍历
  • total += add
• 终止后若total == |V|，则S是母顶点，否则不是。
  该方案的遍历次数等于从S出发的BFS最大层数（即S到所有可达节点的最长最短路径长度）：
• 对绝大多数真实世界的图（社交网络、网页图、调用图等），直径为小常数（通常小于10），仅需个位数次数的遍历即可完成判定
• 最坏情况为链式有向图（S为链起点，边沿链方向依次指向后续节点，且边流顺序从链尾到链头排列），需要O(|V|)次遍历
  如果输入为邻接表格式流（同一源点的所有出边连续排列），可以通过预记录每个源点出边块的偏移位置，把遍历次数压缩到2次：第一遍扫描记录所有节点的出边位置并标记初始可达集，第二遍按BFS顺序直接读取对应节点的出边块完成全量可达标记，不需要反复扫描全量边流。

2. 单遍遍历近似判定场景 #

如果要求仅读取1次输入、内存严格为对数级，可以采用基于随机投影的概率sketch方案，具体逻辑：

• 初始化k个独立的随机哈希函数，为每个节点v生成k位的随机指纹，每一位独立以0.5概率取0或1；k的取值根据可接受的错误率调整，通常取64即可把假阳性概率降到1e-18以下。
• 初始化可达集指纹为S的指纹值，维护一个大小为k的位数组作为sketch。
• 每读入一条边u -> v：按照线性传递规则更新sketch，本质是把邻接矩阵的传递闭包运算通过随机投影压缩到位数组上，单条边更新仅需O(k)常数时间。
• 单遍遍历完成后，若计算得到的可达集sketch和全节点集合的预计算sketch匹配，则判定S为母顶点。
  该方案不存在假阴性（只要S不是母顶点，一定能检测出来），仅存在极低概率的假阳性，内存占用为O(k log |V|)，完全满足严格流式模型的约束，适合大规模图的快速预筛查场景。

常见误区说明 #

不少资料提到可以用单遍BFS/DFS完成可达性标记，这个结论仅适用于可以随机访问邻接表的内存计算场景：流式场景下边是顺序输入的，一旦错过某条边的处理位置，单遍约束下无法回头读取，除非把全量边存储到内存中，本质就退化成了离线算法，不再符合流式计算的要求。

内容的提问来源于stack exchange，提问作者F64081169