3

给定非循环图（树）（E，V）。查找所有路径（路径是相邻节点的序列），其中路径上的节点总和为 0。

蛮力方法是生成所有节点对，为每对检查节点的值总和是否为 0。这需要 O(N^3) 时间和 O(N) 空间复杂度。请提出更快的解决方案。

4

2 回答 2

3

您可以在 O(n^2) 时间内通过对每个选择的起始节点运行深度优先搜索来完成此操作。

深度优先搜索计算每个节点到根起始节点的距离。只要距离为 0，就会找到一条路径。

有n个节点，每个DFS需要O(n)，所以总运行时间是O(n^2)。

一般来说，很难做得更好，因为如果所有节点的权重均为 0，那么您需要输出 O(n^2) 答案。

Python代码

import networkx as nx
G=nx.Graph()
G.add_edge(0,1)
G.add_edge(1,2)
G.add_edge(1,3)
W=[1,0,-1,-1]

def dfs(G,n,dist,parent):
    """Depth first search and yield nodes where sum is 0."""
    dist += W[n]
    if dist==0:
        yield n
    for n2 in G[n]:
        if n2!=parent:
            for e in dfs(G,n2,dist,n):
                yield e

for start in G:
    for n in dfs(G,start,0,None):
        print start,n

请注意，这将为每个路径 0->2 和 2->0 返回 2 个条目，如果节点的权重为零，则还返回路径 1->1。

您可以通过仅在 start < n 时输出答案来删除这些额外的情况。

计数解决方案

如果您只想知道解决方案的数量，您可以通过将树分成更小的部分来在 O(nlogn) 和 O(n) 空间中执行此操作。

  1. 选择图形中心的一个节点（ O(n) 来找到它，尽管我怀疑选择一个随机节点在实践中会像快速排序一样有效）
  2. 通过为每个邻居运行 DFS 并将距离存储在字典映射距离中以计算具有该距离的节点，找到包含该节点的所有零权重路径。比较字典可以让我们找到零权重的路径。上）
  3. 现在对以每个孩子为根的子图重复此算法

对于二叉树，我们将有 2 个大小最多为 n/2 的子图，因此第二阶段将进行大约相同数量的操作，并且类似地，每个阶段都需要 O(n) 直到子图包含单个节点。将有 O(logn) 个阶段，因此总体复杂度为 O(nlogn)。

对于非二叉树，子图比较多，但也比较小，所以每个阶段都会像以前一样花费O(n)，但我们应该更快地触底，所以非二叉树也应该是O(nlogn)。（同样执行 step2 稍微复杂一些，但仍然可以在 O(n) 中完成）

于 2013-11-13T21:29:56.557 回答
1

在 Python 中使用以下代码的 O(n) 解决方案。因为它是一棵树，所以我们不需要检查访问过的节点。

from collections import defaultdict

class Node(object):
    def __init__(self, id, weight):
        self.id = id
        self.weight = weight
        self.children = []

    def __repr__(self):
        return '<Node {0}: {1}>'.format(self.id, self.weight)

class Solver(object):
    def __init__(self):
        self.sums = defaultdict(list)
        self.path = []
        self.solutions = []

    def dfs(self, depth, node, acc):
        self.path.append(node)

        key = acc + node.weight
        for x in self.sums[key]:
            self.solutions.append(self.path[x+1:])

        self.sums[key].append(depth)
        for child in node.children:
            self.dfs(depth + 1, child, acc + node.weight)
        self.sums[key].pop()

        self.path.pop()

    def run(self, root):
        self.sums[0].append(-1)
        self.dfs(0, root, 0)
        return self.solutions

nodes = [
    Node('A', 5),
    Node('B', 1),
    Node('C', 2),
    Node('D', -3),
    Node('E', 1),
    Node('F', 2),
    Node('G', 0),
    Node('H', -8),
]
i = 0
while i < len(nodes) - 1:
    nodes[i].children.append(nodes[i+1])
    i += 1

s = Solver()
solutions = s.run(nodes[0])
for x in solutions:
    print x

输出是：

[<Node B: 1>, <Node C: 2>, <Node D: -3>]
[<Node C: 2>, <Node D: -3>, <Node E: 1>]
[<Node D: -3>, <Node E: 1>, <Node F: 2>]
[<Node D: -3>, <Node E: 1>, <Node F: 2>, <Node G: 0>]
[<Node G: 0>]
[<Node A: 5>, <Node B: 1>, <Node C: 2>, <Node D: -3>, <Node E: 1>, <Node F: 2>, <Node G: 0>, <Node H: -8>]

我假设添加、删除和访问键的字典方法是 O(1)。如果不是，您可以使用一些哈希来平均获得它。

解释：在任何路径（...，n_i，...，n_j，...）中，我们有从 n_i 到 n_j 的所有权重之和等于n_j.acc - n_(i-1).acc。所以我们只需要找到两个具有相同累积和的节点。我们使用哈希在 O(1) 中找到它。

当然，您可以将其调整为仅计算路径数。您只需对 self.sums 的大小求和（并且可以删除 self.path）。

于 2013-11-14T03:40:07.083 回答