图中的路径数

Question

我有一个无向、未加权的图。让我们固定一个顶点并找到从该顶点开始的所有不同路径，这些路径覆盖了图中的所有顶点。任务是从每个顶点找到可能的此类路径的数量。
例如：让我们画一个 4 个顶点 [ 1, 2, 3, 4] 的图。而边是 (1,2), (2,3), (3,4), (4,2)。这里 answer 是 4。路径为 1>2>3>4、1>2>4>3、3>4>2>1、4>3>2>1。

我提出了一种算法，该算法使用强力技术来查找可能的此类路径的数量，由每个顶点初始化。
例如：对于上面的例子：
From vertex 1 there is 2 such path;
From vertex 2 there is no such path;
From vertex 3 there is 1 such path;
From vertex 4 there is 1 such path;
所以答案是2+1+1=4。

是否有可能以更好的时间复杂度来解决这个问题？

Answer 1

有一个O(2^n n^2)时间的算法通过修改Held--Karp DP得到。这个想法是，对于与 S 中某个端点 t 配对的顶点的每个子集 S，通过求和计算恰好访问 S 中的顶点并在 t 处结束的路径数，对于 S 中 t 的每个邻居 u，计数用于访问 S - {t} 并在 u 结束。作为基本情况，单例集的计数均为 1。在 Python 3:

中

import itertools
def count_hamilton_paths(graph):  # graph is a dict of adjacency lists
    vertices = frozenset(graph)
    table = {(frozenset({t}), t): 1 for t in vertices}
    for r in range(2, len(vertices) + 1):
        for subset_tuple in itertools.combinations(vertices, r):
            subset = frozenset(subset_tuple)
            for t in subset:
                subset_minus_t = subset - frozenset({t})
                table[(subset, t)] = sum(table[(subset_minus_t, u)]
                                         for u in graph[t]
                                         if u in subset_minus_t)
    return sum(table[(vertices, t)] for t in vertices)

print(count_hamilton_paths({1: {2}, 2: {1, 3, 4}, 3: {2, 4}, 4: {2, 3}}))

图中的路径数

Number of Paths in a Graph

algorithm

graph

graph-algorithm