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

相关文章

来自专栏灯塔大数据

每周学点大数据 | No.43 相似连接的可扩展性

No.43期 相似连接的可扩展性 小可:那么具体是怎么做的呢? Mr. 王:我们先来看看求单元函数值是如何在 MapReduce 上实现的吧。 ? 图中有三...

3367
来自专栏窗户

Scheme来实现八皇后问题(2)

  上一章讲了用1~n的排序来表示n皇后的解,然后通过枚举1~n所有的排列、判定谓词过滤所有排列得到最终的所有解。

723
来自专栏向治洪

分布式系统中的RPC请求经常出现乱序的情况 写一个算法来将一个乱序的序列保序输出

分布式系统中的RPC请求经常出现乱序的情况。  写一个算法来将一个乱序的序列保序输出。例如,假设起始序号是1,对于(1, 2, 5, 8, 10, 4, 3...

1839
来自专栏数值分析与有限元编程

CSR存储刚度矩阵

CSR(Compressed Sparse Row Storage Format)是一种非常有效的稀疏矩阵的存储方法,它按行将稀疏矩阵存储在一个一维实型数组中,...

2885
来自专栏https://www.cnblogs.com/L

【机器学习】--Python机器学习库之Numpy

NumPy(Numerical Python的缩写)是一个开源的Python科学计算库。使用NumPy,就可以很自然地使用数组和矩阵。 NumPy包含很多实用的...

672
来自专栏CDA数据分析师

数据分析师(技术编程类)常见的10道面试题解答

1、海量日志数据,提取出某日访问百度次数最多的那个IP。   首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最...

2248
来自专栏维C果糖

史上最简单的 MySQL 教程(十)「列类型 之 日期时间型」

所谓的列类型,其实就是指数据类型,即对数据进行统一的分类,从系统的角度出发是为了能够使用统一的方式进行管理,更好的利用有限的空间。

35111
来自专栏编码前线

布隆过滤器(Bloom Filter)详解

直观的说,bloom算法类似一个hash set,用来判断某个元素(key)是否在某个集合中。 和一般的hash set不同的是,这个算法无需存储key的值,对...

794
来自专栏Leetcode名企之路

布隆过滤器

之前读吴军《数学之美》的时候提到布隆过滤器,觉得蛮有意思的,所以总结一下。 在计算机中,判断一个元素是不是在一个集合中,通常是用hash来解决,这在数据量不大的...

601
来自专栏华章科技

10道Hadoop面试真题及解题思路

首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法, 比如模1000...

642

扫码关注云+社区