PHP 拓扑排序

```php
class TopologicalGraph
{
    private $V;                 // 顶点个数
    private $inDegree;          // 记录每个顶点的入度
    private $free = [];         // 维护一个入度为0的集合
    private $adj = [];          // 邻接表
    private $nodes = [];        // 所有节点

/*public function __construct($V)
    {
        $this->V = $V;

for ($i = 0; $i < $V; ++$i)
            $this->inDegree[$i] = 0;
    }*/

public function __construct(array $graph)
    {
        foreach ($graph as $line) {
            $from = $line[0];
            $to = $line[1];
            $this->addEdge($from, $to);
        }
        $this->nodes = array_unique($this->nodes);
        $this->V = count($this->nodes);
    }

public function addEdge($from, $to)
    {
        if (!in_array($to, $this->nodes)) {
            array_push($this->nodes, $to);
            $this->inDegree[$to] = 0;
        }
        if (!in_array($from, $this->nodes)) {
            array_push($this->nodes, $from);
            $this->inDegree[$from] = 0;
        }
        $this->adj[$from][] = $to;
        ++$this->inDegree[$to];
    }

public function topologicalSort()
    {
        foreach ($this->inDegree as $k => $v) {
            // 将所有入度为0的顶点入队
            if ($v == 0)
                $this->free[] = $k;
        }

$count = 0;                             // 计数，记录当前已经输出的顶点数
        $drop = [];
        while (count($this->free) != 0) {
            $v = array_shift($this->free);     // 从队列中取出一个顶点

echo $v . " ";                     // 输出该顶点
            ++$count;
            array_push($drop, $v);

// 将所有v指向的顶点的入度减1，并将入度减为0的顶点入栈
            if (isset($this->adj[$v]))
                foreach ($this->adj[$v] as $item) {
                    if ((--$this->inDegree[$item]) == 0)
                        $this->free[] = $item;
                }
        }

if ($count < $this->V) {
            return false;
        } else {
            return true;
        }
    }

}

$g = new TopologicalGraph([
    ['A', 'C'],
    ['A', 'B'],
    ['C', 'F'],
    ['B', 'G'],
    ['C', 'G'],
    ['M', 'N'],
]);
$result = $g->topologicalSort();
echo "\n";
echo $result? 'success' : 'have loop';
```

清凉的茶

评论已关闭

标签

链接

其它