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

最近又要做工程又要做理论，

已经晕头转向了

这次又得请教高手们一个图论的问题

最近的一篇文章就差这一块了：

一个具有n个节点的有向图，

节点按照编号大小排列

编号小的节点可以与任意编号比它大的节点相连

即对于节点i

对于任意节点j

如果 i < j

则存在弧 i -> j

我称之为前向通路

而编号大的节点到编号小的节点则只存在有限个已知的连线

我称之为后向通路

我现在需要一个有效的算法

能够枚举出所有这样路径

该路径能够依次不重复遍历所有的节点

并且如果节点i, j之间不存在后向通路

则i, j的相对顺序在路径中不能发生改变

在我的第一个附图里面显示了6个节点和它们之间的后向通路

方便起见没有画出前向通路

第二个附图中显示了一种可能的路径，即

1 -> 4 -> 2 -> 5 -> 3 -> 6

第三个附图显示了另外一种可能的路径，即

1 -> 2 -> 3 -> 4 -> 5 -> 6

如果指定起始和中止节点，则这个是哈密尔顿回路问题，这是NP完全的。

NPC没有关系

但算法复杂度最好只是和后向通路的数量有关

只要所有的节点都能被访问就行

首先可以做一个每个节点的入口和出口集。

这个可以帮助分辨有多少可能的开始节点，多少个可能的终止节点。。比如你刚才的例子里

节点（入，出）

1（0，5）

2(2,4)

3(4,3)

4(3,4)

5(4,2)

6 (5,0)

这样这个例子里有一个是只出不入的，一个是只入不出的。分别是必然的起点1和终点6。

这两个点定了以后，可以把这两点去掉，再从新作入出表。以进一步列出可能的第二和倒数第二的节点列表。

能定点的定点。不能定的，列出可能情况。 依次向中心推。好象可以用递归算法。

用一个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;

}

123456

124356

124536

125346

134256

142356

142536

153426

startNode

在哪里定义的？没看出来。。是ArrayList的标准函数吗？

不好意思，没用过c#