多重图中的子图

Question

下图显示了一个不那么简单的版本，但就我面临的问题的节点数量而言，它是大幅缩小的版本。

假设多重图中有一个起始节点（标记为“a”）和一个目标节点（标记为“Z”）。在“a”和“Z”之间有很多路径，如“a-Z”、“a-b-g-Z”等（图中用粗体突出显示），它们组合起来形成了自己的图表。

是否有标准算法来识别这个子图？

Answer 1

是的，有这样的算法。

顶点

v

是子图的一部分当且仅当：

v

可从

a

中的

G \ {Z}

到达，并且

v

可从

Z

中的

G \ {a}

到达。

您需要做的就是为图中的每个顶点实现“可达性算法”（简单的图遍历即可完成工作）。