最优解决方案：图问题中所有可能的非循环路径

[poster]

我正在处理无向图。我需要在图中找到所有可能的非循环路径：

with G(V,E) find all subsets of V that are acyclic paths 我正在使用python scipy或matlab-无论哪种都合适。有什么聪明的解决方案吗？

我正在尝试通过广度优先搜索来实现它（请参阅Wiki）

我在matlab中也有此工具箱： http : //www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox，但看来我的问题没有简单的解决方案。

PS。实际上，该问题表示为：公交网络设计问题：找到这样一种交通网络，该交通网络可以将过客和运营商的成本降到最低（例如，市区最佳地铁网络）

在此先感谢Rafal



回答：


我认为您的PS中所述的问题可能是NP问题。如果是这样，那么仅对于具有非常有限的节点数（N〜