3

我在这里显示了一个图表。仅针对节点 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

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

图形

4

1 回答 1

3

You can start by visiting all nodes of type A. For each A node, look at all nodes connected to it which are of type B. From there look all nodes of type C and so on, keeping track of the nodes you've visited from the last A node. Then whenever you reach a subnode that completes the criteria of your search, you add all the list of nodes from the A node until the point where you are. Essentially you're doing a depth-first search where you keep traversing into the graph as long as a node meets the criteria of what should follow and backtrack whenever there's no more valid nodes (ie. which would produce a valid subgraph) going out from your current node.

于 2013-09-24T09:55:35.797 回答