小编gra*_*ard的帖子
在Python中快速找到给定大小的所有连通子图的方法？
[注意：答案中给出了快速解决方案，但需要进一步改进速度。]
\n给定一个具有n 个顶点的无向稀疏连接图G。我正在寻找一种快速方法来查找具有m 个顶点的G的所有连通子图。可以假设m \xe2\x89\xaa n且G的顶点度为deg(v) \xe2\x89\xaa n。
\n图解示例
\n对于这个例子，我们有n = 5，m = 3。
\n4个连通子图为：(0,1,2),(1,2,3),(0,2,3),(2,3,4)
\n
\n代码示例
\n下面的代码使用networkxandego_graph非常慢。对于n = 100、deg(v) = 10、m = 4的图，大约需要 100 秒。这是m \xe2\x89\xaa n和deg(v) \xe2\x89\xaa n的示例。n =10000的情况将需要永恒的时间。
import networkx as nx\nimport itertools\nimport time\n\nn=100 #nodes in graph\ndeg=10 #node degree in graph\nm=4 #nodes in …6
推荐指数
推荐指数
1
解决办法
解决办法
1141
查看次数
查看次数