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

Question

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

我知道它们有很多(至少对于具有恒定连通性的图来说呈指数级增长)——但这没关系，因为我相信节点和边的数量使得这对于至少较小的 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(graph with root removed, N, new arbitrary chosen root)，并重复直到剩余图的大小 < N(因为没有树所需大小的将存在)。

我还忘记了每个访问过的节点(调用 alltrees 的每个根节点)都需要标记，上面考虑的子节点集应该只是相邻的未标记子节点。我想我们需要考虑不存在未标记的 child 但深度 > 0 的情况，这意味着这个“分支”未能达到所需的深度，并且不能构成解决方案集的一部分(因此整个内部循环与该元组可以中止)。

那么这行得通吗？有什么重大缺陷吗？有没有更简单/已知/规范的方法来做到这一点？

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

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)