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 中实现回溯由于您有 800 个元素，因此明智的做法是自己使用堆栈而不是依赖递归。您将需要以某种方式为已经在任何当前位置遍历的项目“着色” ，并在回溯时取消着色，这样您就可以避免循环。这永远不会非常有效，因为您正在回溯，它具有指数级的复杂性并且您没有任何选择以不同的方式执行此操作，因为您需要找到所有路径。