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

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数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

Link-Cut-Tree(LCT)详解

LCT是一种解决动态树问题的方法,由tarjan(为什么又是他)在1982年提出,最原始的论文在这里,在论文中,tarjan除了介绍了均摊复杂度为$O(log^...

51113
来自专栏数据结构与算法

一个例子教你如何与出题人斗智斗勇

我以前出过一道题,卡了10种贪心,但还是被第11种贪心A了,  一道题不会做?贪嘛,能怎么贪怎么贪,想怎么贪怎么贪! 现在NOIP题目的数据给的不...

2636
来自专栏nnngu

算法09 五大查找之:哈希查找

前面的几篇文章分别总结了:顺序查找、二分查找、索引查找、二叉排序树。这一篇文章要总结的是五大查找的最后一个:哈希查找(也称为散列查找)。提起哈希,我的第一印象就...

2779
来自专栏温安适的blog

动态规划算法-背包问题

3458
来自专栏小樱的经验随笔

HDU 1728 逃离迷宫(DFS经典题,比赛手残写废题)

逃离迷宫 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

3107
来自专栏闵开慧

曾经做过的40道程序设计课后习题总结(一)

曾经做过的40道程序设计课后习题总结(一) 课后习题目录 1 斐波那契数列 2 判断素数 3 水仙花数 4 分解质因数 5 杨辉三角 6 学习成绩查询...

3278
来自专栏数据结构与算法

Link-Cut-Tree(LCT)详解

1580
来自专栏wym

分治算法概念

  分治算法的设计思想是,将一个难以直接诶解决的大问题,分割成一些规模较小的相同的问题,以便各个击破,分而治之。

642
来自专栏TensorFlow从0到N

讨厌算法的程序员 2 - 证明算法的正确性

第1篇介绍了插入排序算法,这里要提出一个问题:学习算法仅仅是积累一个又一个的算法实现吗? 当然不是。比算法本身更重要也更基础的,是对算法的分析:能够证明其正确...

2565
来自专栏Golang语言社区

【Go 语言社区】POJ 1047 Round and Round We Go 循环数新解

题目描述: 给定一字符串表示的高精度数,判断它是否是可循环的。如果假设字符串num的长为n,则将num从1开始乘到n,如果每次得到的结果包含的字符元素都和a是相...

33811

扫描关注云+社区