在图中寻找子图

Question

我这里有一个图表。请注意，节点B_0、B_1属于类型B的节点，C_0、C_1、C_2、C_3属于类型C的节点，以此类推。 现在，我想要找到多个子图，满足像这个例子所定义的标准 -

标准 -

1. 子图包含1个A类型节点、1个B类型节点、1个C类型节点和1个D类型节点。
2. 子图具有从A类型节点到B类型节点的一条边，连接类型B和类型C的一条边，以及连接类型C和类型D的一条边。
3. 子图包含从类型A出发的一条边，从子图到类型B节点的一条边，从类型B到类型C节点外部的一条边，以及从类型D到类型E外部的一条边。

现在，这个描述应该给出以下结果 -

1. 子图 :: A_0、B_0、C_1、D_1
2. 子图 :: A_0、B_0、C_0、D_0
3. 子图 :: A_0、B_1、C_2、D_2
4. 子图 :: A_0、B_1、C_3、D_3

我想知道是否有任何算法，可以找到这样的子图？ 我尝试通过制作所有可能的组合来找出算法。然而，这将是指数级的子图节点数。因此，我想知道是否存在一种有效的方法来计算它。或者在图论中是否存在类似性质的问题？

- Raj

---

看起来像是偏序集。如果是这种情况，那么深度优先搜索会起作用。 - Ante

Answer 1

你可以从访问所有 A 类型的节点开始。对于每个 A 节点，查看与之连接的所有 B 类型的节点。然后查看所有 C 类型的节点等等，保持跟踪您从上一个 A 节点访问过的节点。每当您到达符合搜索标准的子节点时，您就将从 A 节点开始直到当前位置的所有节点添加到列表中。实际上，您正在进行深度优先搜索，只要满足应该遵循的条件，就会一直遍历图形，并在没有更多有效节点（即不会产生有效子图）从当前节点出去时回溯。

- Gato

---

谢谢你提供这个想法。我认为，它看起来像一个深度优先搜索（DFS）问题。但是如果我不得不选择像2C，3D和2E这样的点，这仍然会是一个类似于DFS的问题吗？因为它应该会生成许多子图，如“C_0，C_1，D_0，D_1，D_2，E_0，E_1”是其中之一解决方案。我们可以想象其他可能性。 - Raj