首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(十) ——有向无环图与拓扑算法

作者头像
用户1327360
发布2018-03-07 10:40:24
2.2K0
发布2018-03-07 10:40:24
举报
文章被收录于专栏:决胜机器学习决胜机器学习

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

相关阅读:

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-07-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 决胜机器学习 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、有向无环图概念
  • 二、、拓扑排序
  • 相关阅读:
    • PHP数据结构(九) ——图的定义、存储与两种方式遍历
      • PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)
        • PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)
          • PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)
            • PHP数据结构(七) ——串与实现KMP算法
              • PHP数据结构(六) ——树与二叉树之概念及存储结构
                • PHP数据结构(六) ——数组的相乘、广义表
                  • PHP数据结构(五) ——数组的压缩与转置
                    • PHP数据结构(四) ——队列
                      • PHP数据结构(三)——运用栈实现括号匹配
                        • PHP数据结构(二)——链式结构线性表
                          • PHP数据结构(一)——顺序结构线性表
                          领券
                          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档