PHP数据结构(十)——有向无环图与拓扑算法
(原创内容,转载请注明来源,谢谢)
有向无环图又称为DAG图。与其对应的还有有向树、有环图。如下图所示。
拓扑排序的概念很拗口,我认为这篇博客讲得很形象。
http://blog.csdn.net/dm_vincent/article/details/7714519
拓扑排序是在上述DAG图为前提的,也就是说有环图是无法进行拓扑排序,拓扑排序仅针对有向图、无环图,两个条件缺一不可。
拓扑排序是将DAG图转换成线性的顺序,保证按顺序从第一个往后提取排序结果时,每个被提取到的结果的前置的结果都已经提取过。
举个例子,假设现在需要学习制作网站。以上面的DAG图为例,第一层的节点可以表示为学习HTML/Css的基础知识,第二层的两个平级的节点,左边是学习PHP语言基础,右边是学习Javascript,第三层左下角那个,是学习数据库,右边那个是学习相关框架等。
可以看出,拓扑排序是把一个有向的结构排成线性的,作为课程学习,就可以按这个排序后的线性结构,逐个学习,而保证了每个学习内容的前置条件都已经学习到。
3、拓扑排序算法
1)在有向图中选取一个顶点,该顶点满足:只有作为弧尾指向其他节点,没有作为弧头被指向。把该节点存入结果集。
2)从有向图中删除该节点,以及以该节点作为弧尾的所有弧。
3)重复步骤1)和2),直到所有顶点都已经进入结果集。
4)检查图中是否还存在弧,如果还存在,说明该图不是有环图,拓扑排序失败。否则将顶点的结果集输出,就是拓扑排序的结果。
4、关键路径
1)AOV网
用顶点表示活动,用弧表示活动时间的有向图。
2)AOE网
带权的有向无环图,顶点表示事件,图表示活动,权表示活动的持续时间。
3)关键路径
影响最终路径节点最大的点。该节点的完成情况会影响整个项目的进度。
5、PHP实现拓扑排序
输入:一个有向无环图,包括五个节点,编号0-4,其中0指向1、2,1指向3、4,2指向3,3指向4,4没有指向。例如,0指向1和2,则数组[0][1]和[0][2]的值是1,[0][0]、[0][3]、[0][4]的值是0。
执行过程:刚开始,结果集为空,每次循环遍历出一个满足条件的节点,则结果集加1,并清空该节点所指向的点(例如节点0满足条件,则设置[0][i](0<=i<=节点数)都为0)。
循环结束条件;当结果集和节点数相同时,则退出循环,返回结果集。
限制条件:为了防止输入的是有环图,导致程序死循环,因此对循环的最大次数进行限制,当循环超出次数,停止循环,结束程序。
结果如下图所示:
源代码如下:
(注,代码接上文,本代码为部分代码,方法是在类MinTree之下,因此本代码仅为代码片段,但本机验证通过)
//拓扑排序
publicfunction topologicalOrder($arrGraph){
if(!is_array($arrGraph)){
return'请输入有向无环图!';
}
$nodeNum= count($arrGraph);//计算顶点数
$resStack= array();//存放结果集
$curNum= count($resStack);
//以下两个遍历是为了防止图是有环图,导致死循环
$allowLoopNum= $nodeNum * $nodeNum;//最大允许循环次数
$curLoopNum= 0;//当前循环次数
//当节点足够或者循环次数超出限制,退出循环
while($curNum< $nodeNum || $curLoopNum > $allowLoopNum){
for($i=0;$i<$nodeNum;$i++){
//如果该节点已经进入结果集,则不用再循环该节点
if(in_array($i,$resStack)){
continue;
}
$isTail= true;//纵向遍历,如果没有节点指向该节点,则其可以进入结果集
for($j=0;$j<$nodeNum;$j++){
//如果有指向该节点的点,则其为弧头,推出循环
if($arrGraph[$j][$i]> 0){
$isTail= false;
break;
}
}
//结果为true,说明没有点指向节点i
if($isTail){
array_push($resStack,$i);//入结果集
//删除i节点的指向
for($k=0;$k<$nodeNum;$k++){
$arrGraph[$i][$k]= 0;
}
//退出for循环
break;
}
}
$curNum= count($resStack);
$curLoopNum++;
}
//循环没超出,是有向无环图
if($curLoopNum<= $allowLoopNum){
return$resStack;
}else{
return '输入的是有环图,无法进行拓扑排序!';
}
}
//构造有向无环图,ij==0表示没有弧,1表示i是弧尾j是弧头的弧
$arrToSort = array(
0 => array(0, 1, 1, 0,0),
1 => array(0, 0, 0, 1,1),
2 => array(0, 0, 0, 1,0),
3 => array(0, 0, 0, 0,1),
4 => array(0, 0, 0, 0,0)
);
$arrOrder = $minTree->topologicalOrder($arrToSort);
echo '<br />有向无环图:';
print_r($arrToSort);
echo '<br />拓扑排序的结果是:';
print_r($arrOrder);
——written by linhxx 2017.07.08