PHP中的递归函数来查找任意节点之间的路径 [英] Recursive function in PHP to find path between arbitrary nodes

问题描述

我有一个表示节点之间连接的数组.

给定一个特定的端节点，我想返回通向该端节点的节点的子集.

例如如果我的节点定义是ab"、ac"、ce"、ef"、ek"、kz"、qz"、xq"、km"、ct"，它们代表以下内容:

我想查看通向z"的路径，它们是:

• a-c、c-e、e-k、k-z
• q-z, x-q

我有这个 PHP 代码:

";foreach ($predecessors as $pre) {getPre($array, substr($pre, 0,1));}}}?>

输出:

Array ( [5] => k-z [6] => q-z )数组( [4] => e-k )数组 ( [2] => c-e )数组 ( [1] => a-c )数组( [7] => x-q )

这至少是正确的节点列表，所以我快到了.

问题:如何在我的 $graph 数组中返回结果?

我需要在某处返回 $predecessors; 并将其与之前的结果合并.我还想添加能够指定开始节点的功能，但我认为这只是我的递归结束测试中的额外测试.

解决方案

您需要的主要事情(如您所说)是构建数组以将数据传回.如果要添加更多元素，则此代码将构建一个子元素，或者如果未找到任何内容，则仅将返回值设置为该项目.不确定输出的格式是否正是您所追求的，但您可以使用它.

function getPre($array, $char) {$graph = [];foreach ($array 作为 $pre) {如果 ( $pre[2] == $char ) {$graph[$pre] = getPre($array, $pre[0]) ?: $pre;}}返回 $graph;}

请注意，不必使用 substr() 来提取字符，您可以将字符串用作数组，[2] 是第三个字符.

这输出...

数组([k-z] =>大批([e-k] =>大批([c-e] =>大批([a-c] =>a-c)))[q-z] =>大批([x-q] =>x-q))

为了将代码输出为字符串，我使用迭代器处理了上述函数的结果.这个想法是从叶节点开始，然后回溯(使用 getSubIterator())到树的基部......

$graph = getPre($items, $end);$objects = new RecursiveIteratorIterator( new RecursiveArrayIterator( $graph ), RecursiveIteratorIterator::LEAVES_ONLY );foreach ( $objects as $name => $object ) {$path = $object;for ( $depth = $objects->getDepth() - 1; $depth >= 0; $depth-- ) {$path .= ",".$objects->getSubIterator( $depth)->key();}回声 $path.PHP_EOL;}

哪些输出...

a-c,c-e,e-k,k-zx-q,q-z

I have an array representing connections between nodes.

Given a specific end node, I'd like to return a subset of the nodes that lead to this end node.

E.g. If my nodes definitions are "a-b", "a-c","c-e", "e-f", "e-k","k-z","q-z", "x-q" "k-m", "c-t" which represent the following:

and I'd like to see the path(s) leading to 'z', which are:

• a-c, c-e, e-k, k-z
• q-z, x-q

I have this PHP code:

<?php

$end   = "z";  
$items = array("a-b", "a-c", "c-e", "e-f", "e-k", "k-z", "q-z", "x-q", "k-m", "c-t"); 

$graph = getPre($items, $end);  

print_r($graph);  // This is what I want to populate

exit();

function getPre($array, $char) {  

  $predecessors = array_filter($array, function($line) use($char) {
      return strpos(substr($line, 2, 1), $char) === FALSE ? FALSE : TRUE;
            }
          );
  if (count($predecessors) == 0) {
    return;
  } else {
      print_r($predecessors)."<br>";
    echo "<br>";
    foreach ($predecessors as $pre) {getPre($array, substr($pre, 0,1));}
  }
}

?>

which outputs:

Array ( [5] => k-z [6] => q-z )
Array ( [4] => e-k )
Array ( [2] => c-e )
Array ( [1] => a-c )
Array ( [7] => x-q )

which at least is the correct nodes list, so I'm almost there.

Question: How do I have have the results returned in my $graph array?

Somewhere I need to return $predecessors; and have it merged with the previous results. I will also want to add functionality to be able to specify a start node, but I think that will just be an extra test in my recursive end test.

解决方案

The main thing you needed (as you said) is to build the arrays to pass the data back. This code will build a sub element if there are more elements to add or just set the return value to the item if nothing is found. Not sure if the format of the output is exactly what you are after, but you may be able to work with it.

function getPre($array, $char) {
    $graph = [];
    foreach ($array as $pre) {
        if ( $pre[2] == $char ) {
            $graph[$pre] = getPre($array, $pre[0]) ?: $pre;
        }
    }

    return $graph;
}

Note than rather than having to use substr() to extract a character, you can use the string as an array and [2] is the 3rd character.

This outputs...

Array
(
    [k-z] => Array
        (
            [e-k] => Array
                (
                    [c-e] => Array
                        (
                            [a-c] => a-c
                        )

                )

        )

    [q-z] => Array
        (
            [x-q] => x-q
        )

)

To output the codes as strings, I've processed the result of the above function using iterators. The idea being to start at the leaf nodes and then to track back (using getSubIterator()) to the base of the tree...

$graph = getPre($items, $end);
$objects = new RecursiveIteratorIterator( new RecursiveArrayIterator( $graph ), RecursiveIteratorIterator::LEAVES_ONLY );
foreach ( $objects as $name => $object )    {
    $path = $object;
    for ( $depth = $objects->getDepth() - 1; $depth >= 0; $depth-- ) {
        $path .= ",".$objects->getSubIterator( $depth )->key();
    }
    echo $path.PHP_EOL;
}

Which outputs...

a-c,c-e,e-k,k-z
x-q,q-z

这篇关于PHP中的递归函数来查找任意节点之间的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！