PHP-查找数组中的所有路径（2面）

Question

我在php中有一个巨大的数组（〜800个子数组）：

$arrayx = array(

[0] => array("side1" => "XTSWS", "side2" => "WRXXC", "value" => "150"),
[1] => array("side1" => "WRXXC", "side2" => "TXXBD", "value" => "110"),
[2] => array("side1" => "XTSWS", "side2" => "GVFDS", "value" => "40"),
[3] => array("side1" => "XTSWS", "side2" => "ABNMDA", "value" => "1350"),
[4] => array("side1" => "TTTSY", "side2" => "WRXXC", "value" => "1150"),
[5] => array("side1" => "WDWDD", "side2" => "KGADSD", "value" => "10050"),
[6] => array("side1" => "ZZSJH", "side2" => "PPPEIJD", "value" => "1750"),

... 800
);

对于双方，我正在尝试查找从一个值到另一个值的所有可能路径，例如：

XTSWS-> WRXXC

XTSWS-> TXXBD-> WRXXC

XTSWS-> TXXBD-> ZZSJH-> WRXXC

在PHP中，有没有有效的方法可以做到这一点？我找到了一些在Python等中使用图/节点的示例。

$values = $this->findAllPaths("XTSWS", "WRXXC");

function findAllPaths($from, $to)
{

}

Answer 1

您将需要在PHP中实现回溯，请参见https://www.geeksforgeeks.org/backtracking-algorithms/

由于您有800个元素，因此最好单独使用stack，而不要依赖递归性。您将需要以某种方式"color"在任何当前位置上已经遍历的项目，并在回溯时为它们上色，以便避免循环。

这永远不会非常有效，因为您正在回溯，因为它具有指数级的复杂性，并且您没有其他选择可做不同的选择，因为您需要找到所有路径。