查找从 A 点到 B 的路径，循环次数为 n

发布于 2024-10-29 08:40:57 字数 738 浏览 1 评论 0原文

我有一个问题需要指导。我有一个数组，其中包含有关不同节点之间的边的信息。所以，

a[1][39] = 'p' -->在节点 1 中采用转移“p”到达节点 39。完整的图是这样的：

i[1][51] = 'p' 
i[1][39] = 't' 
i[39][40] = 'd' 
i[40][66] = 'p' 
i[66][51] = 'd' 
i[40][41] = 'm' 
i[41][64] = 'd' 
i[64][40] = 'd'

正如您所看到的，它是一个有向循环图。 我需要做的是拥有从点 X 到 Y 的所有路径。因此，给定 X=1 和 Y=51。我需要这样的输出：

o[0][0] = 'p'

o[1][0] = 't'
o[1][1] = 'd'
o[1][2] = 'p'
o[1][3] = 'd'

o[2][0] = 't'
o[2][1] = 'd'
o[2][2] = 'm'
o[2][3] = 'd'
o[2][4] = 'd'
o[2][5] = 'p'
o[2][6] = 'd'

第一个索引显示路径号。所以，我这里有3条路。第二个索引显示步骤。因此，第一条路径迈出一步，第二条路径迈出四步。

我正在 PHP 中执行此操作，但即使是伪代码也可以。另外，我还可以将输入数组反转为 i[1]['p'] = 51 等（如果这可能有帮助）。

谢谢。

原文

I have a problem that I need guidance with. I have an array that has information about the edges between different nodes. So,

a[1][39] = 'p' --> Take transition 'p' while in node 1 to get to node 39. The complete graph is this:

i[1][51] = 'p' 
i[1][39] = 't' 
i[39][40] = 'd' 
i[40][66] = 'p' 
i[66][51] = 'd' 
i[40][41] = 'm' 
i[41][64] = 'd' 
i[64][40] = 'd'

As you can see, it's a directed, cyclic graph. What I need to do is to have all paths from point X to Y. So, given X=1 and Y=51. I need output like so:

o[0][0] = 'p'

o[1][0] = 't'
o[1][1] = 'd'
o[1][2] = 'p'
o[1][3] = 'd'

o[2][0] = 't'
o[2][1] = 'd'
o[2][2] = 'm'
o[2][3] = 'd'
o[2][4] = 'd'
o[2][5] = 'p'
o[2][6] = 'd'

The first index shows the path number. So, I have three paths here. The second index shows the step. So, one step in the first path, four in the second.

I'm doing this in PHP but even pseudo-code code would do. Also, I can also reverse the input array to i[1]['p'] = 51 etc. if that might help.

Thanks.

分享到QQ

分享到微博