在无向图中找到所有大小为N的子树

Question

给定一个无向图，我想生成所有大小为N的树的子图，其中“大小”是指树中边的数量。

我知道它们很多（对于具有常数连通性的图至少呈指数增长），但这没关系，因为我相信节点和边数使得至少对于小的N值（比如10或更少）它是可处理的。

该算法应该是内存高效的——也就是说，它不应该需要一次性拥有所有图形或某个大的子集，因为即使对于相对较小的图形，这可能会超出可用内存。因此像DFS这样的算法是理想的。

在伪代码中，假设给定起始图graph和所需长度N: 从任意一个节点root作为起点并调用alltrees(graph, N, root)。

alltrees(graph, N, root)
 given that node root has degree M, find all M-tuples with integer, non-negative values whose values sum to N (for example, for 3 children and N=2, you have (0,0,2), (0,2,0), (2,0,0), (0,1,1), (1,0,1), (1,1,0), I think)
 for each tuple (X1, X2, ... XM) above
   create a subgraph "current" initially empty
   for each integer Xi in X1...XM (the current tuple)
    if Xi is nonzero
     add edge i incident on root to the current tree
     add alltrees(graph with root removed, N-1, node adjacent to root along edge i)
   add the current tree to the set of all trees
 return the set of all trees

这仅找到包含所选初始根的树，因此现在删除此节点并调用alltrees（已删除根的图形，N，新选择的任意根），并重复直到剩余图形的大小 < N （因为将不存在所需大小的树）。

我还忘记了每个访问的节点（每个alltrees调用的根）需要被标记，并且上面考虑的子项集应仅为相邻未标记的子项。 我猜我们需要考虑这样一种情况，即没有未标记的子项存在，但深度> 0，这意味着该“分支”未能达到所需深度，并且不能成为解决方案集的一部分（因此与该元组关联的整个内部循环可以中止）。

这会起作用吗？ 有什么主要缺陷吗？ 有没有更简单/已知/规范的方法来做到这一点？

上述算法的一个问题是它不满足内存有效的要求，因为递归将在内存中保持大量的树集合。

- BeeOnRope

---

你说你不想把所有的图形都保存在内存中。但是，那么所有大小为N的图形呢？ - Fantius

只是为了确保大家理解术语，以下陈述是否正确？2个相连的顶点形成一个大小为1的图。3个相连的顶点形成一个大小为3的图，有3个大小为1的子图，以及3个大小为2的子图。对吗？ - Fantius

我也不想在内存中保存所有大小为N的图形。由于分支因子（平均节点度）很高，大小为N的图形数量比所有小于N的大小的图形数量要大得多，因此这些语句基本上是等价的。 - BeeOnRope

是的，你对子树数量的描述是正确的。后一种情况也有0个大小为3的子图，因为不允许出现循环。 - BeeOnRope

你应该在问题中提到这个图是无环的，最好放在标题里。这会使得答案更容易，因为在一个无环图中，一旦确定了根节点，它就可以被处理成一个有向树。 - JCooper

Answer 1

这需要的内存量与存储图形所需的内存成比例。它将仅返回每个所需大小的树作为子图一次。

请记住，我只是在此处输入。可能存在错误。但想法是您逐个遍历节点，对于每个节点搜索包括该节点但不包括已搜索前面节点的所有树。（因为这些节点已经被耗尽）。那个内部搜索通过列出树中的节点边缘来进行递归完成，对于每个边缘决定是否将其包含在树中。 （如果会形成循环或添加已用尽的节点，则无法包含该边缘。）如果您将其包含在树中，则使用的节点增加，并且您有新的可能的边缘可以添加到您的搜索中。

为了减少内存使用，剩余待处理的边缘是由所有递归调用级别直接操作，而不是更明显的方法——在每个级别复制该数据。如果将该列表复制，则总内存使用量将达到树的大小乘以图中的边数。

def find_all_trees(graph, tree_length):
    exhausted_node = set([])
    used_node = set([])
    used_edge = set([])
    current_edge_groups = []

    def finish_all_trees(remaining_length, edge_group, edge_position):
        while edge_group < len(current_edge_groups):
            edges = current_edge_groups[edge_group]
            while edge_position < len(edges):
                edge = edges[edge_position]
                edge_position += 1
                (node1, node2) = nodes(edge)
                if node1 in exhausted_node or node2 in exhausted_node:
                    continue
                node = node1
                if node1 in used_node:
                    if node2 in used_node:
                        continue
                    else:
                        node = node2
                used_node.add(node)
                used_edge.add(edge)
                edge_groups.append(neighbors(graph, node))
                if 1 == remaining_length:
                    yield build_tree(graph, used_node, used_edge)
                else:
                    for tree in finish_all_trees(remaining_length -1
                                                , edge_group, edge_position):
                        yield tree
                edge_groups.pop()
                used_edge.delete(edge)
                used_node.delete(node)
            edge_position = 0
            edge_group += 1

    for node in all_nodes(graph):
        used_node.add(node)
        edge_groups.append(neighbors(graph, node))
        for tree in finish_all_trees(tree_length, 0, 0):
            yield tree
        edge_groups.pop()
        used_node.delete(node)
        exhausted_node.add(node)

- btilly

Answer 2

假设您可以销毁原始图形或制作可销毁副本，我想出了一些可能有效但可能非常痛苦的东西，因为我没有计算它的O-Ntiness。 对于小的子树，它可能有效。

步骤如下：

- 逐步执行以下操作： - 对图形节点进行排序，以按相邻边数升序排列的节点列表获取 - 处理所有具有相同边数的第一个节点 - 删除这些节点

例如，对于6个节点的图形，查找所有大小为2的子图（抱歉我的完全缺乏艺术表达力）：

好吧，对于更大的图形也是如此，但应该分多个步骤完成。

假设：

- 最分叉节点的Z个边的数量 - 所需的子树大小M - S步数 - 每步Ns节点数 - 假定快速排序对节点进行排序

最坏情况：S *（Ns^2 + M*Ns*Z）

平均情况：S *（NslogNs + M*Ns*(Z/2)）

问题是：无法计算真实的Omicron，因为每个步骤中的节点将减少取决于图形的状态...

使用此方法解决整个问题可能需要花费很长时间，因为在具有非常互连节点的图形上，它可能会被并行化处理，并且您可以执行一两个步骤，以移除不连续的节点，提取所有子图，然后选择另一种方法来处理剩余部分，但是您将从图形中删除大量节点，因此可能会减少剩余运行时间...

不幸的是，这种方法将使GPU受益而不是CPU，因为有很多具有相同边数的节点将在每个步骤中进行...如果不使用并行化，这种方法可能很糟糕...

也许一个反向会更适合CPU，对具有最大边数的节点进行排序和处理...这些节点可能在开始时较少，但是您将从每个节点中提取更多的子图...

另一种可能性是计算图中出现次数最少的边缘计数，并从具有该计数的节点开始，这将减轻提取子图的内存使用和迭代计数...

- Marino Šimić

---

对于一个中等规模的高度连接图，可能的答案数量是非常庞大的。除非你在生成所有结果之前能够轻松地迭代遍历它们，否则你将会耗尽内存。 - btilly

同意btilly的观点。此外，你说“处理每个节点”，但没有详细说明。在我的情况下，图是“国王的图”。例如，一个由16个节点组成的4x4网格图，有42条边。如何高效地处理所有大小为15的树？我同意删除已经完成的节点的策略是一个好方法，但第一次迭代是关键，你还没有详细说明它。 - BeeOnRope

我真的认为这很自描述：“处理每个节点”意味着“从该节点提取所有大小为x的图形”，而如果第一步太大，您可以轻松地将其分成子步骤，例如在每个步骤中最多使用10个节点。 - Marino Šimić

Marino，你的方法很好，但是你的方法有一个缺陷，它不能处理循环图，你的方法只适用于非循环图。如果图中有一个循环怎么办？你能否使用循环图修改你的答案？ - user1735921

Answer 3

如果记忆是最大的问题，您可以使用来自形式验证工具的 NP-ish 解决方案。即，猜测一个大小为 N 的节点子集，并检查它是否是一个图。为了节省空间，您可以使用二元决策图（http://en.wikipedia.org/wiki/Binary_decision_diagram）来表示原始图的节点和边。此外，您还可以使用符号算法来检查您所猜测的图是否真的是一个图 - 因此您不需要在任何时候构造原始图（或 N 大小的图）。您的内存消耗应该是（在大 O 表示法中）log(n)（其中n是原始图的大小）来存储原始图，以及另外log(N)来存储每个您想要的“小图”。另一个工具（据说甚至更好）是使用 SAT 求解器。即，构造一个 SAT 公式，当且仅当子图是图时才为真，并将其提供给 SAT 求解器。

- Guy

---

内存是一个问题，但不是你所想的那种方式。将图形本身（例如具有约16个节点和约42个边缘的图形）保存在内存中很容易，但即使这个图形至少有数万亿个子图。我无法在内存中保存数万亿个图形 :( - BeeOnRope

也许我误解了你的解决方案，但我不担心重复输出，我担心的是重叠的解决方案。如果您的原始图形是一棵树，那么这不是问题，否则，假设您有一个菱形图形，其边缘为(0,1)，(0,2)，(1,3)，(2,3)。 - Amit Prakash

Answer 4

除非我理解问题有误，否则人们似乎过于复杂化了它。 这只是“N条边内的所有可能路径”，并且您允许循环。 对于两个节点A、B和一条边，您的结果将是： AA、AB、BA、BB

对于两个节点、两条边，您的结果将是： AAA、AAB、ABA、ABB、BAA、BAB、BBA、BBB

我会递归进入每个for循环，并传递一个“模板”元组。

N=edge count
TempTuple = Tuple_of_N_Items ' (01,02,03,...0n) (Could also be an ordered list!)
ListOfTuple_of_N_Items ' Paths (could also be an ordered list!)
edgeDepth = N

Method (Nodes, edgeDepth, TupleTemplate, ListOfTuples, EdgeTotal)
edgeDepth -=1
For Each Node In Nodes
    if edgeDepth = 0 'Last Edge
        ListOfTuples.Add New Tuple from TupleTemplate + Node ' (x,y,z,...,Node)
    else
        NewTupleTemplate = TupleTemplate + Node ' (x,y,z,Node,...,0n)
        Method(Nodes, edgeDepth, NewTupleTemplate, ListOfTuples, EdgeTotal
next

这将为给定的边数创建每个可能的顶点组合。

缺少的是生成给定边数的元组的工厂。

最终你会得到一个可能路径的列表，操作是Nodes^(N+1)。

如果使用有序列表而不是元组，则无需担心创建对象的工厂。

- Matthew

---

抱歉，马修 - 我最初在我的问题中包含了单词“路径”，然后删除了大部分引用（用“树”替换），但我看到我错过了一些 - 我已经重新编辑以更正。因此，澄清一下，我不感兴趣的是路径（有向或无向），而只是原始图形的子树，这些子树是指定大小的所有_连通的，无环_子图。在您的示例中，将包含A-B边的大小为1的单个树。 两个节点的两个边缘情况是不可能的，因为该图没有多重边，因此最多只有一条边。 - BeeOnRope

Answer 5

你有一个带有边缘e_1，e_2，...，e_E的图。

如果我理解正确，你想枚举包含N条边的所有子树。

一个简单的解决方案是生成E中选择N个子图，并检查它们是否为树。你考虑过这种方法吗？当然，如果E太大，那么这种方法就不可行了。

编辑：

我们还可以利用树是树的组合这一事实，即每个大小为N的树都可以通过向大小为N-1的树添加一条边来“生长”。令E为图中的边集。然后算法可能会像这样进行。

T = E
n = 1
while n<N
    newT = empty set
    for each tree t in T
        for each edge e in E
            if t+e is a tree of size n+1 which is not yet in newT
                add t+e to newT 
    T = newT
    n = n+1

在此算法结束时，T 是大小为 N 的所有子树的集合。如果空间有限，请不要保留完整的树列表，而是使用紧凑的表示形式，例如使用 ID3 将 T 实现为决策树。

- mitchus

---

这确实可行，但在我的情况下，与子图数量相比的树的分数将会非常小（这可能适用于大多数图形），因此它不符合O（实际图形数量）的标准。 - BeeOnRope

好吧，公平地说，你在问题中没有包括那个标准 :) 你只谈到了空间复杂度。 - mitchus

Answer 6

对于一个K_n图，任意两个顶点之间大约有n!条路径。我还没有仔细看过你的代码，但这是我会做的。

1. 选择一对顶点。
2. 从一个顶点开始，尝试递归地到达目标顶点（类似于dfs但不完全相同）。我认为这将输出所选顶点之间的所有路径。
3. 您可以针对所有可能的顶点对执行上述操作，以获取所有简单路径。

- jack_carver

---

你如何有效地限制路径长度为N？此外，我认为这不会找到所有的子树，它只会找到两个顶点之间的路径（例如，它永远不会产生任何顶点度数大于2的路径，对吗？）。所以我意识到我的描述是错误的，实际上我想要找到所有的子图，它们都是树，而不是限制在路径上。 - BeeOnRope

大小N是什么意思？树的直径（最长路径）是什么？ - jack_carver

树中的边数，将在上面进行澄清。 - BeeOnRope

Answer 7

看起来以下解决方案可行。

将所有顶点的集合分为两部分，遍历所有分区。然后计算结束于不同部分的边的数量（k）；这些边对应于树的边，它们连接第一部分和第二部分的子树。递归地计算两个部分的答案（p1、p2）。然后整个图的答案可以计算为k*p1*p2的所有这样的分区之和。但是所有树都将被考虑N次：每条边一次。因此，必须将总和除以N才能得到答案。

- fdermishin

---

请注意，我不想计算树的数量，而是要生成它们。 - BeeOnRope

Answer 8

这个算法很复杂，不容易在这里贴出来。但是这里有一个链接预订搜索算法，你可以用它来做你想做的事情。这个pdf文件包含了两个算法。如果你懂俄语，你也可以看一下这个。

- Mihran Hovsepyan

Answer 9

你的解决方案并不可行，虽然可以做出来。主要问题是子问题可能会产生重叠的树，因此当你将它们合并时，你得不到大小为n的树。你可以拒绝所有存在重叠的解决方案，但你可能需要比实际需要更多的工作。

由于你可以接受指数级运行时间，并且可能写出2^n棵树，因此具有V.2^V算法也不是什么坏事。所以最简单的方法是生成所有可能的n个节点子集，然后测试每一个子集是否形成一棵树。由于测试一组节点是否形成一棵树需要O(E.V)时间，因此我们潜在地谈论的是V^2.V^n时间，除非你有一个具有O(1)度的图。这可以通过以两个连续的子集差异恰好为一个被交换的节点的方式枚举子集来略微改进。在这种情况下，你只需检查新节点是否与任何现有节点相连即可，这可以通过保持所有现有节点的哈希表来完成，时间与新节点的出边数成正比。

下一个问题是如何枚举给定大小的所有子集，使得在连续的子集之间交换不超过一个元素。我将把这留给你自己去思考：）

- Amit Prakash

---

你能给出一个具体的例子，证明我的算法会产生重复的输出吗？我看不到，但确实应该有一个小例子。我不明白我们如何检查N个节点的子集，因为N个节点并没有定义一个图。你选择哪些边，是从与这N个节点相邻的边中选择吗？也就是说，“这些N个节点形成一棵树”的说法并不是很完整，因为它可能是真的或假的，这取决于你选择哪些边。 - BeeOnRope

我不担心重复输出，我担心的是重叠的解决方案。如果您的原始图形是一棵树，则没有问题，否则，假设您有一个菱形图形的图形，其边缘为（0,1），（0,2），（1,3），（2,3）。假设您在节点0上运行子例程，并且N = 2。您的下一个递归调用级别将返回树{(1,3)}和{(2,3)}。当您尝试将它们放在一起时，您不会得到一棵树，因为节点3是两个子树的一部分。 - Amit Prakash

关于选择哪些边，您需要选择原图中两端节点都在子图中的所有边。如果您已经有了邻接表，子图可以是隐式的，或者如果您有一种O（1）时间的查找方式来查找哪些节点在您的子图中，则可以在O（E + V）时间内构建它。 - Amit Prakash

Answer 10

我认为在这个网站上有一个很好的算法（使用Perl实现）（寻找TGE），但如果您想商业使用它，您需要联系作者。该算法与您在问题中的算法类似，但通过将当前工作子树作为参数（而不是单个节点）包含在过程中，避免了递归爆炸。这样，从子树发出的每条边都可以被选择性地包含/排除，并且可以对扩展树（具有新边）和/或减少图形（无边）进行递归。

这种方法是图枚举算法的典型方法--通常需要跟踪一些构建块，它们本身就是图形；如果您尝试仅处理节点和边，则会变得难以处理。

- Zac Thompson