PHP中的拓扑排序

问题内容：

我发现了用于PHP的此拓扑排序功能：

资料来源： http: //www.calcatraz.com/blog/php-topological-sort-
function-384/

    function topological_sort($nodeids, $edges) {
        $L = $S = $nodes = array();
        foreach($nodeids as $id) {
            $nodes[$id] = array('in'=>array(), 'out'=>array());
            foreach($edges as $e) {
                if ($id==$e[0]) { $nodes[$id]['out'][]=$e[1]; }
                if ($id==$e[1]) { $nodes[$id]['in'][]=$e[0]; }
            }
        }
        foreach ($nodes as $id=>$n) { if (empty($n['in'])) $S[]=$id; }
        while (!empty($S)) {
            $L[] = $id = array_shift($S);
            foreach($nodes[$id]['out'] as $m) {
                $nodes[$m]['in'] = array_diff($nodes[$m]['in'], array($id));
                if (empty($nodes[$m]['in'])) { $S[] = $m; }
            }
            $nodes[$id]['out'] = array();
        }
        foreach($nodes as $n) {
            if (!empty($n['in']) or !empty($n['out'])) {
                return null; // not sortable as graph is cyclic
            }
        }
        return $L;
    }

我看起来很好矮。无论如何，对于某些输入-我在输出中得到重复的行-
请参见 http://codepad.org/thpzCOyn

通常，如果我删除重复项，排序似乎是正确的 array_unique()

我用两个示例检查了函数，排序本身看起来是正确的。

我应该只调用array_unique()结果吗？

问题答案：

您会得到重复的行，因为存在重复的边。我不是图论专家，但我很确定这是不合法的：

    0 => 
    array (
      0 => 'nominal',
      1 => 'subtotal',
    ),
    2 => 
    array (
      0 => 'nominal',
      1 => 'subtotal',
    ),
    ...

您可以在构造节点的部分中添加测试，如下所示：

    if ($id==$e[0] && !in_array($e[1], $nodes[$id]['out']))
    {
      $nodes[$id]['out'][]=$e[1];
    }
    if ($id==$e[1] && !in_array($e[0], $nodes[$id]['in'])) // Not needed but cleaner
    {
      $nodes[$id]['in'][]=$e[0];
    }

…或者只是确保您没有将重复的边传递给该函数。：P

PHP中的拓扑排序

微信关注