查找图中可能组合的数量

Question

这是我要解决的问题：

给定一个无向图，通过遍历任意两个节点之间的路径并跟踪我们去过哪些节点（无需两次去任何节点），找出节点的不同无序组合的数量。

比如说邻接矩阵是：

1: 2,3
2: 1,3,4
3: 1,2,4
4: 2,3,5
5: 4

一个无序组合是 [1,2,3,4]，可以通过路径 1>3>4>2 或 1>3>2>4

获得

答案将是 17，具有以下无序集：

[1,2] [1,3] [2,3] [2,4] [3,4] [4,5] 
[1,2,3] [1,2,4] [1,3,4] [2,3,4] [2,4,5] [3,4,5] 
[1,2,3,4] [1,2,4,5] [1,3,4,5] [2,3,4,5] 
[1,2,3,4,5]

目前，我的函数在我的程序中所做的只是暴力破解所有的可能性，但我想知道如果图形有 10,000 多个节点，是否有更快的方法来做到这一点？暴力破解太慢了。

Answer 1

你可以使用这个算法：

按 name 对节点进行排序，例如 N_0,...,N_k

define an `result` set which is empty at beginning
for `i` from `0` to `k` do the following
 set node `n_i` as root
 step 1: list of all 'n_i` neighbors like `n_j` which `j>i`
 add all of these pairs to `result` set
 set `n_j` as root
 go to step 1
end

查找图中可能组合的数量

Find the number of possible combinations in a graph

algorithm

combinations

graph