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 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-201-数字范围按位与

给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

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

次小生成树

次小生成树 次小生成树 我们已经熟知了求最小生成树的方法,用kruskal,prim算法都可以搞 那么我们如何求次小生成树呢? 这里次小生成树的定义是 边...

41760
来自专栏HTML5学堂

Javascript中的Label语句

HTML5学堂:在JavaScript中,我们可能很少会去用到 Label 语句,但是熟练的应用 Label 语句,尤其是在嵌套循环中熟练应用 break, c...

42870
来自专栏landv

pudn下载地址的规律

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

洛谷P3388 【模板】割点(割顶)(tarjan求割点)

题目背景 割点 题目描述 给出一个n个点,m条边的无向图,求图的割点。 输入输出格式 输入格式: 第一行输入n,m 下面m行每行输入x,y表示x到y有一条边 ...

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

11:大整数减法

11:大整数减法 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 求两个大的正整数相减的差。 输入共2行,第1行是被减...

296100
来自专栏机器学习之旅

tf.nn.embedding_lookup记录

我觉得这张图就够了,实际上tf.nn.embedding_lookup的作用就是找到要寻找的embedding data中的对应的行下的vector。

15120
来自专栏小狼的世界

Leetcode刷题记录:计算复数乘法

10510
来自专栏HansBug's Lab

算法模板——线段树4(区间加+区间乘+区间覆盖值+区间求和)

实现功能——1:区间加法 2:区间乘法 3:区间覆盖值 4:区间求和 这是个四种常见线段树功能的集合版哦。。。么么哒(其实只要协调好三种tag的关系并不算太难—...

28730
来自专栏逆向技术

逆向知识十三讲,汇编中数组的表现形式,以及还原数组

            逆向知识十三讲,汇编中数组的表现形式,以及还原数组 讲解数组之前,要了解数组的特性 1.数据具有连续性 2.数据类型相同 比如:   i...

22070

扫码关注云+社区

领取腾讯云代金券