<?php
$graph = [
//图的顶点个数
'count' => 9,
//图的顶点列表
'vertexs' => [
//['name' => "活动名称", 'days' => 完成活动所需时间, 'sTime' => 活动最早开始时间, 'inCount' => 活动的前驱节点个数, 'adjacentNode' => 相邻活动列表(节点索引), 'adjacent' => 相邻活动的个数]
['name' => "P1", 'days' => 8, 'sTime' => 0, 'inCount' => 0, 'adjacentNode' => [2, 6], 'adjacent' => 2],
['name' => "P2", 'days' => 5, 'sTime' => 0, 'inCount' => 0, 'adjacentNode' => [2, 4], 'adjacent' => 2],
['name' => "P3", 'days' => 6, 'sTime' => 8, 'inCount' => 2, 'adjacentNode' => [3], 'adjacent' => 1],
['name' => "P4", 'days' => 4, 'sTime' => 14, 'inCount' => 2, 'adjacentNode' => [5, 8], 'adjacent' => 2],
['name' => "P5", 'days' => 7, 'sTime' => 5, 'inCount' => 1, 'adjacentNode' => [3, 5], 'adjacent' => 2],
['name' => "P6", 'days' => 7, 'sTime' => 18, 'inCount' => 2, 'adjacentNode' => [], 'adjacent' => 0],
['name' => "P7", 'days' => 4, 'sTime' => 8, 'inCount' => 1, 'adjacentNode' => [7], 'adjacent' => 1],
['name' => "P8", 'days' => 3, 'sTime' => 12, 'inCount' => 1, 'adjacentNode' => [8], 'adjacent' => 1],
['name' => "P9", 'days' => 4, 'sTime' => 18, 'inCount' => 2, 'adjacentNode' => [], 'adjacent' => 0],
]
];
function sortQueue(&$q){
$sTime = [];
foreach($q as $k => $v){
$sTime[$k] = $v['sTime'];
}
uasort($q, function($a, $b) {
if ($a['sTime'] == $b['sTime']) {
return 0;
}
return ($a['sTime'] < $b['sTime']) ? -1 : 1;
});
}
function EnQueue(&$q, $node, $sTime){
$item = ['node' => $node, 'sTime' => $sTime];
array_push($q, $item);
//优先级队列
sortQueue($q);
}
function DeQueue(&$q){
$element = array_shift($q);
$node = $element['node'];
return $node;
}
function TopologicalSorting($g, &$sortedNode){
$nodeQueue = [];
for($i = 0; $i < $g['count']; $i++){
if($g['vertexs'][$i]['inCount'] == 0){
EnQueue($nodeQueue, $i, $g['vertexs'][$i]['sTime']);
}
}
while(!empty($nodeQueue)){
$node = DeQueue($nodeQueue); //按照开始时间优先级出队
array_push($sortedNode, $node);
//遍历节点node的所有邻接点，将表示有向边inCount值减1
for($j = 0; $j < $g['vertexs'][$node]['adjacent']; $j++){
$adjNode = $g['vertexs'][$node]['adjacentNode'][$j];
$g['vertexs'][$adjNode]['inCount']--;
//如果inCount值为0，则该节点入队列
if($g['vertexs'][$adjNode]['inCount'] == 0){
EnQueue($nodeQueue, $adjNode, $g['vertexs'][$adjNode]['sTime']);
}
}
}
return count($sortedNode) == $g['count'];
}
function PrintSorting($g, $sortedNode){
foreach($sortedNode as $v){
echo $g['vertexs'][$v]['name'].' ';
}
echo PHP_EOL;
}
function main(){
global $graph;
$sortedNode = [];
if(!TopologicalSorting($graph, $sortedNode)) {
echo "Graph has circle!".PHP_EOL;
}
PrintSorting($graph, $sortedNode);
}
main();