algorithm - 如何确定哪些边是顶点子集之间的简单路径的一部分？

Question

问题:

• 我有一个由边列表给出的无向图(带有循环)。
• 我得到了一个顶点/节点的列表/子集(例如:下面的 [0, 9, 17])，我将其称为“重要顶点” ”。
• 我想根据每条边是否是重要顶点之间的某些简单路径 [1] 的一部分来为其着色。在下面的示例中，如果边缘是这样一个简单路径的一部分，我将其着色为红色，否则为蓝色。

[1]:简单路径意味着任何顶点在该路径中最多出现一次。

问题:

• 这个问题有名称吗？
• 是否有任何现有算法可以解决此问题？
• 最佳时间复杂度是多少？ 我的直觉告诉我，通过恒定次数访问每个边缘也许可以解决这个问题。一旦您知道一条边是否是简单路径的一部分，您可能就不需要再次访问它。

到目前为止我尝试过的:

• 对于每条边，在两个方向上执行深度优先搜索，以找出哪些重要顶点可以通过两个方向的简单路径到达。

• 如果任一方向未到达重要顶点，或者仅在两个方向上到达单个且相同的重要顶点，则边缘会将自身着色为蓝色 - 否则会将自身着色为红色。

• 这几乎有效 - 但错误地将 15-16 边缘着色为红色 - 并且缩放效果似乎非常差，这就是为什么我正在寻找更好的方法来做到这一点。

相关:

• How to find if there is a simple path from vertex x to vertex y that includes the edge e
• https://math.stackexchange.com/questions/1104849/find-edges-part-of-a-simple-path-between-two-vertices

我不认为这个问题与上述问题重复，因为这是关于任意数量的“重要顶点”，以及对所有边进行分类，而不是单个。

Answer 1

看起来你想要找到 biconnected components 。它们形成一棵树(如果图未连接则为森林；在这种情况下单独处理每棵树)。然后将该树的一些边缘和顶点涂成红色。

原图的铰接顶点对应于树的顶点，双连通子图对应于树的边。

如果重要顶点是关节顶点，则将其涂成红色。

如果双连通组件具有任何不是关节顶点的重要顶点，则将相应的树边及其两个顶点着色为红色。

如果树的两个红色顶点之间有一条路径，则将整个路径(边和顶点)涂成红色。

重复直到没有更多的边或顶点可供着色。

上面的算法似乎有一个异常(exception)情况，即当(单连通)组件中有一个重要的顶点时。易于单独检测和处理。