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

|| 给定一个无向图，我想生成所有子图，它们是大小为N的树，其中大小是指树中边的数量。我知道它们很多（至少对于具有恒定连通性的图来说是指数级的）-但这很好，因为我相信节点和边的数量至少对于N的较小值来说很容易处理（例如10以下）。该算法应该是内存有效的-也就是说，它不需要一次将所有图形或其中的一些大子集存储在内存中，因为即使是相对较小的图形，它也可能超出可用内存。因此，像DFS这样的东西是可取的。给定起始图graph和所需长度N，这就是我在想的伪代码。选择任意一个节点，以ѭ2为起点，然后调用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，任意选择的新根的图形），并重复直到剩余图形的大小 0，这意味着此“分支”未能达到所需的深度，并且不能构成解决方案集的一部分（因此，整个内部循环与该元组关联的内容可以中止）。那会行吗？有什么重大缺陷吗？任何更简单/已知/规范的方法可以做到这一点？上面概述的算法的一个问题是它不能满足内存效率要求，因为递归将在内存中保存大量树。

已邀请:

11 个回复

傻寺俊擒

这需要与存储图形所需的内存成比例的内存量。它将仅返回一次是所需大小的树的每个子图。请记住，我只是在这里输入了它。可能有错误。但是这个想法是，您一次走一个节点，每个节点搜索包含该节点的所有树，但没有一个先前搜索的节点。（因为那些已经用尽了。）通过列出树中节点的边，并为每个边确定是否将其包括在树中，来递归地进行内部搜索。（如果将其循环，或添加一个用尽的节点，则不能包括该边。）如果将其包含在树中，则使用的节点会增长，并且有新的可能要添加到搜索中的边。为了减少内存使用，通过所有递归调用级别来操纵留待观察的边缘，而不是采用在每个级别上复制该数据的更明显的方法。如果复制了该列表，则您的总内存使用量将达到树的大小乘以图形中的边数。

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)

烷刨画颠离

假设您可以销毁原始图形或创建可销毁的副本，那么我想到了可以使用但可能完全是悲伤的东西，因为我没有计算其O-Ntiness。它可能适用于小型子树。在每个步骤中分步执行：对图节点进行排序，以便获得按相邻边数ASC排序的节点列表处理第一个节点具有相同数量边的所有节点删除那些节点例如，一个包含6个节点的图的示例找到了所有大小为2的子图（对不起，我完全缺乏艺术表现力）：同样，对于较大的图也会这样做，但是应该以更多的步骤完成。假设：最分支节点的Z边数 M所需的子树大小 S步数 Ns步中的节点数假设对节点进行快速排序最坏的情况下： S *（Ns ^ 2 + MNsZ）平均情况： S *（NslogNs + MNs（Z / 2））问题是：无法计算实数微米，因为每一步的节点都会减少，这取决于图形的方式... 用这种方法解决整个问题可能在连接节点非常紧密的图上非常耗时，但是可以将其并行化，并且您可以执行一两个步骤，以删除错位的节点，提取所有子图，然后选择另一种方法其余的，但是您会从图中删除很多节点，这样可以减少剩余的运行时间... 不幸的是，这种方法将使GPU受益，而不是CPU，因为在每一步中都会有很多具有相同数量的边的节点....如果不使用并行化，这种方法可能很糟糕... 也许逆运算会更好地与CPU配合使用，对具有最大边缘数的节点进行排序并继续进行操作……开始时这些元素可能较少，但是您将从每个节点提取的子图更多…… 另一种可能性是计算图中最少出现的egde计数，并从具有该计数的节点开始，这将减轻提取子图时的内存使用量和迭代计数。

葛瞎说漓

除非我读的是问题，否则错误的人似乎会使它变得过于复杂。这只是“ N条边内的所有可能路径”，您正在允许循环。对于两个节点：A，B和一个边，这将是： AA，AB，BA，BB 对于两个节点，两条边的结果将是： AAA，AAB，ABA，ABB，BAA，BAB，BBA，BBB 我将每个递归为一个，然后传递一个“模板”元组

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）如果使用有序列表而不是元组，则无需担心创建对象的工厂。

倪蕊悲潍

如果内存是最大的问题，则可以使用形式验证中的工具使用NP-ish解决方案。即，猜测大小为N的节点的子集，并检查它是否为图。为了节省空间，您可以使用BDD（http://en.wikipedia.org/wiki/Binary_decision_diagram）表示原始图形的节点和边。另外，您可以使用符号算法来检查您猜到的图形是否真的是图形-因此您无需在任何时候构造原始图形（也不需要构造N尺寸的图形）。您的内存消耗应为（大O型）log(n)（其中n是原始图的大小）以存储原始图，另外一个another9ѭ用于存储您想要的每个“小图”。另一个工具（应该更好）是使用SAT解算器。也就是说，如果子图是一个图，则构造一个正确的SAT公式，并将其提供给SAT解算器。

版萍层分

对于Kn的图，大约有n！任何两对顶点之间的路径。我还没有遍历您的代码，但是这是我会做的。选择一对顶点。从顶点开始，然后尝试递归到达目标顶点（类似于dfs，但不完全相同）。我认为这将输出所选顶点之间的所有路径。您可以对所有可能的顶点对执行上述操作，以获取所有简单路径。

期差骇蓟

似乎以下解决方案将起作用。将所有分区遍历为所有顶点集的两个部分。然后计算末端在不同部分的边缘数（k）；这些边缘与树的边缘相对应，它们连接第一部分和第二部分的子树。递归计算两个部分的答案（p1，p2）。然后可以将整个图的答案计算为k * p1 * p2的所有此类分区的总和。但是所有树将被视为N次：每个边缘一次。因此，总和必须除以N才能得到答案。

凡夕

我认为您的解决方案不起作用，尽管可以使它起作用。主要问题是子问题可能会产生重叠的树，因此当您将它们合并时，最终并不会得到大小为n的树。您可以拒绝重叠的所有解决方案，但最终可能会做很多不必要的工作。因为您可以使用指数运行时，并且可以写出2 ^ n个树，所以拥有V.2 ^ V算法一点也不差。因此，最简单的方法是生成n个节点的所有可能子集，然后测试每个子集是否形成一棵树。由于测试节点的子集是否形成树会花费O（E.V）时间，因此除非您有O（1）度的图，否则我们可能在谈论V ^ 2.V ^ n时间。可以通过枚举子集的方式稍微改善一下这种情况，即两个连续的子集恰好在交换一个节点时有所不同。在那种情况下，您只需要检查新节点是否连接到任何现有节点，就可以通过保留所有现有节点的哈希表来按时间与新节点的输出边缘数量成比例地完成此操作。下一个问题是如何枚举给定大小的所有子集这样成功的子集之间最多交换一个元素。我会把它留给您练习：)

惭法搽

我认为该站点上有一个很好的算法（使用Perl实现）（查找TGE），但是如果要在商业上使用它，则需要与作者联系。该算法与您在问题中的算法类似，但是通过使过程包括当前工作的子树作为参数（而不是单个节点）来避免递归爆炸。这样，可以有选择地包括/排除从子树发出的每个边，并在扩展树（具有新边）和/或缩小图（没有边）上递归。这种方法是图枚举算法的典型方法-您通常需要跟踪少数几个本身就是图的构件；如果您尝试仅处理节点和边缘，则将变得棘手。

期差骇蓟

此算法很大，不容易在此处发布。但是，这里有预订搜索算法的链接，您可以使用该算法执行您想要的操作。此pdf文件包含两种算法。另外，如果您了解俄语，也可以看看。

弦砂牧扁

因此，您有一个具有边e_1，e_2，...，e_E的图。如果我理解正确，则您希望枚举所有子树，它们是树并且包含N条边。一个简单的解决方案是生成每个E选择N个子图并检查它们是否为树。您考虑过这种方法吗？当然，如果E太大，则不可行。编辑：我们还可以利用这样的事实，即树是树的组合，即，通过将大小增加到N-1的树的边可以“长大”每棵大小N的树。令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的所有子树的集合。如果空间是一个问题，请不要保留树的完整列表，而要使用紧凑的表示形式，例如将T实现为决策树使用ID3。

慰泥悍瓶

我认为问题未明确说明。您提到图是无向的，而您要查找的子图的大小为N。缺少的是边的数量，每当您要查找二进制的树或允许有多棵树时。另外-您是否对同一棵树的镜像反射感兴趣，或者换句话说，列出同级兄弟的顺序很重要？如果您尝试查找的树中的单个节点允许有两个以上的兄弟节点，则由于您没有对初始图指定任何限制，并且提到生成的子图应包含所有节点，因此应该允许两个兄弟节点。您可以通过执行深度优先遍历来枚举具有树形式的所有子图。您需要在遍历期间为每个同级重复图形的遍历。当您需要对每个节点作为根节点重复操作时。丢弃对称树将最终导致

 N^(N-2)

图是完全连接的网格还是需要应用Kirchhoff的矩阵树定理

要回复问题请先登录或注册

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

11 个回复

发起人

algorithm

language_agnostic

graph

tree

graph_theory

问题状态

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

与内容相关的链接

11 个回复

发起人

algorithm

language_agnostic

graph

tree

graph_theory

问题状态