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

对于每个节点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平方的。

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

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

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

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

用一个2维数组定义所以可能的通路，比如元素paths[i,j]=0表示i节点到j节点不通，而1表示可通，那你所举的例子实现如下

int[,] paths = new int[6,6] { { 0, 1, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1, 1 }, { 0, 0, 0, 1, 1, 1 }, { 0, 1, 1, 0, 1, 1 }, { 0, 0, 1, 0, 0, 1 }, { 0, 0, 0, 0, 0, 0 } };

private ArrayList pathList = new ArrayList();

private ArrayList curPath = new ArrayList();

private void Doit()

{

for (int i = 0; i <= 5; i++)

{

GetPaths(i);

}

}

private void GetPaths(int startNode)

{

curPath.Add(startNode);

if (curPath.Count == 6)

{

pathList.Add(((int)curPath[0] + 1).ToString() + ((int)curPath[1] + 1).ToString() + ((int)curPath[2] + 1).ToString() + ((int)curPath[3] + 1).ToString() + ((int)curPath[4] + 1).ToString() + ((int)curPath[5] + 1).ToString());

curPath.Remove(startNode);

return;

}

for (int j = 0; j <= 5; j++)

{

if ((paths[startNode, j] == 1) && !curPath.Contains(j))

{

GetPaths(j);

}

}

curPath.Remove(startNode);

return;

}