过滤图中的顶点

Question

假设我有一个有向无环图，有 N 个顶点和一个大小为 M 的顶点子集。

M个顶点都被标记为已访问，如何找到图中所有前辈都被访问过的所有顶点

例如：如果有 4 个顶点 a,b,c,u 和 3 条边 (a,u) (b,u) (c,u) 并且 a,b,c 被标记为已访问我需要输出 u .

我正在考虑遍历所有顶点并为每个顶点检查他的所有前辈，但我认为这效率不高..

Answer 1

从原始图中删除这M个顶点。这可以通过仅从 'visited' 节点移除出边来完成。

不在 M 中且无法从任何其他顶点到达的节点已访问其所有前任（在 M 中）。

如果图形是邻接矩阵的形式，则只需扫描每一列并检查其中是否有任何非零项即可。