主题：再次请教河里的高手，一个图论问题 -- 棒棒糖

指定当前寻找的路径的下一个节点，可能这个名字用的不好。

ArrayList只是一个容器，可以存放任何对象，本来不适合放int类型的变量，会降低效率，我只是图省事。

原要求如果两节点无后向路径则相对位置不能变

图中4、5无后向路径所以4一定要在5前

这样的话第4个和最后一个结果不符合要求。

程序我大致看了一下

应该是基于穷举的思想吧

利用递归进行搜索

实际上形成了一棵搜索树

这样做的效率太低了

举个最简单的例子

如果这六个节点都没有反向通路

那么就只有一条路径

也就是1->2->3->4->5->6

但如果用这个程序搜索

搜索复杂度恐怕会是O(6!)左右吧

原因是：你在标题处敲回车，帖子就被发出去了。

这时，你只要去那个帖子的“修改”功能就可以把它修改成你要的样子再发出去。

没用短信提醒，是想让其他新手也注意到并避免这个问题。：）

虽然原问题应该是一个NPC

但还是希望算法在一般情况下有较好的效率

因为在实际情况下

节点数量在100个左右

指数爆炸是很可怕的事情

我的思路是dynamic programming：假设路径长度为N，先计算出N=2的所有情况，存储路径上的节点号。

然后开始利用N的结果计算N+1的路径，对于有回路的，就prune.

这里面可以优化的细节很多，首先，存储路径上节点的方式，可以帮助后来loop detection + prune。其次，存储路径上面，可以根据 i<j -> {i,j}一定存在来节省空间。最后，如果N太大，可以用divide and conquer的方法，只存储部分结果（i.e. N/2），然后用时间换空间，计算另外一半路径。

具体的程序就不写了，主要是说说思路。

你那个两点间无反向回路的约束条件不太清楚具体指什么。。

对于每个节点i构造一个集合Pi,Pi包含所有小于i且没有后向边连接的节点。这样，对于没有后向路的图，Pi分别是：

P1=[],P2=[1],...,P[N]=[1,2,...,N-1]

而对于你给出的图则有

P1=[],P2=[1],P3=[1,2],P4=[1],P5=[1,2],P[6]=[1,2,3,4,5]

枚举路径的办法同一般的深度优先遍历类似，不过每次选取节点k加入路径的时候,要求Pk为空，

选取k后，对所有的P进行扫描，删除所有的k,

如果选k时候有多个空集备选，则记下回溯点，如果没有任何集合为空则需要回溯。

如果后向边不多的话，此算法应该是近似N平方的。