vertilia/algo-toposort

拓扑排序算法

维护者

详细信息

github.com/vertilia/algo-toposort

源代码

问题

安装: 2

依赖项: 0

建议者: 0

安全性: 0

星标: 0

关注者: 1

分支: 0

开放问题: 0

v1.0.0 2023-07-27 14:37 UTC

Requires

  • php: >=7.4

Requires (Dev)

BSD-2-Clause d6e4310560e97d58dc58ecf6066b043a53dfbc00

searchsorttopotopologicaldepth-first

This package is auto-updated.

Last update: 2024-08-27 17:15:46 UTC

README

拓扑排序 实现 深度优先搜索 算法（Tarjan 1976）。

安装

composer require vertilia/algo-toposort

用法

拓扑排序的示例树

通过构造函数传递数组来调用

$values = [
    'a' => ['b', 'd', 'c', 'e'],
    'b' => ['d'],
    'c' => ['d', 'e'],
    'd' => ['e'],
    'e' => [],
];

$a = new TopoSort($values);

$sorted = $a->sort();

print_r($sorted);

通过 addNode() 调用来形成初始数组

$a = new TopoSort();

$a->addNode('a', ['b', 'd', 'c', 'e'])
    ->addNode('b', ['d']),
    ->addNode('c', ['d', 'e']),
    ->addNode('d', ['e']),
    ->addNode('e', []);

$sorted = $a->sort();

print_r($sorted);

通过 addLink() 调用来形成初始数组

$a = new TopoSort();

$a->addLink('a', 'b')
    ->addLink('a', 'd'),
    ->addLink('a', 'c'),
    ->addLink('a', 'e'),
    ->addLink('b', 'd'),
    ->addLink('c', 'd'),
    ->addLink('c', 'e'),
    ->addLink('d', 'e');

$sorted = $a->sort();

print_r($sorted);

输出

Array
(
    [0] => a
    [1] => c
    [2] => b
    [3] => d
    [4] => e
)

结果顺序