1

我一直在寻找树循环检测，并通过这个 PHP 代码来：

/**
 * Takes an adjacency list: an array of parent/child relationships
 * array(array(1,2));
 */
function check_for_cycles($relationships) {
    $roots = array();
    foreach ($relationships as $row) {
    $parent = $row[0];
    $child = $row[1];

    /* this is the meat of the algorithm and makes
     * use of references to  put children into sets.
     * You could draw an analogy to disjoint set
     * forests here, but thanks to the magic of
     * references the hierarchy collapses much
     * more quickly
     */
    if (isset($roots[$parent])) {
        $roots[$child] =& $roots[$parent];
    } else {
        if (isset($roots[$child])) {
        $roots[$child] = $parent;
        $roots[$parent] =& $roots[$child];
        } else {
        $roots[$parent] = $parent;
        $roots[$child] =& $roots[$parent];
        }
    }
    if ($roots[$parent] == $child) {
        return array($parent, $child);
    }
    }
    return false;
}
/**
 * Test code
 */
$lists = array('1:2,2:3,3:4',
           '1:2,2:3,3:1',
           '1:2,2:3,4:1,3:4',
           '1:2,2:1');
foreach ($lists as $list) {
    $relationships = array();
    foreach (explode(',', $list) as $pair) {
    $relationships[] = explode(':', $pair);
    }
    if (check_for_cycles($relationships)) {
    echo "Found cycle in $list\n";
    }
}

学分：https ://gist.github.com/jmullan/450465/77bdaa2a57e73ecee8ca6d9449aad3f74b379ca5

这完美地检测了树状数据结构中的线性循环，但我无法理解它使用什么算法或代码（数组引用）如何工作。

有人会帮助解释或指出它是什么算法吗？

谢谢。

4

0 回答 0