PHP

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 等中找到了一些使用 graph/nodes 的示例。

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

function findAllPaths($from, $to)
{

}

Answer 1

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

因为你有 800 个元素，明智的做法是使用 stack on your own instead of relying on recursivity. You will need to somehow "color" 在任何当前位置已经遍历的项目，并在回溯时取消着色，这样你就可以避免循环。

这永远不会很有效，因为你在回溯，它具有指数级的复杂性，你没有任何不同的选择，因为你需要找到所有路径。

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

PHP - Find all paths within array (2 sides)

graph

nodes

graph-algorithm