有向无环图检测

01

Spark背景介绍

Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环境,拥有Hadoop MapReduce所具有的优点;但不同于MapReduce的是——Job中间输出结果可以保存在内存中,从而不再需要读写HDFS,因此Spark能更好地适用于数据挖掘与机器学习等需要迭代的MapReduce的算法。

RDD,全称为Resilient Distributed Datasets,中文翻译弹性分布式数据集,是一个容错的、并行的数据结构,可以让用户显式地将数据存储到磁盘和内存中,并能控制数据的分区。RDD是Spark的灵魂,一个RDD代表一个可以被分区的只读数据集。RDD内部可以有许多分区(partitions),每个分区又拥有大量的记录(records)。

RDD之间的依赖关系是靠有向无环图(DAG)表达的,下面看下有向无环图的基本理论和算法。

02

有向无环图(DAG)

在图论中,边没有方向的图称为无向图,如果边有方向称为有向图。在无向图的基础上,任何顶点都无法经过若干条边回到该点,则这个图就没有环路,称为有向无环图(DAG图),如下图所示,4->6->1->2是一个路径,4->6->5也是一条路径,并且图中不存在顶点经过若干条边后能回到该点,可以得出下图为DAG。

入度

入度是图论算法中重要的概念之一。它通常指有向图中某点作为图中边的终点的次数之和,也就是项点的入边条数称为该项点的入度。如上图所示,顶点4的入度为0.

出度

对应于入度,顶点的出边条数称为该顶点的出度。如上图所示,顶点3的入度为2.

03

DAG应用的另一个例子

在一些任务安排和调度的问题里。不同的问题或者任务之间又一些依赖的关系,有的任务需要在某些任务完成之后才能做。就像一些学校的教学课程安排。设置某一门课程需要依赖于一个前置的课程,只有学生学习了前置课程之后才能取学习该课程。如果将一门课程当做一个节点,从它引出一个指针指向后序依赖它的课程。就可能有一个类似这样的图:

Algorithms课指向Theoretical CS,意思是选修后者需要先修完Algorithms这门课,Artificial Intelligence依赖Theoretical CS,Machine learning 依赖Artificial Intelligence,Neural Networks依赖Machine learning这门课,这称为一条路径。

还可以看到,上图中入度为0的节点有 Introduction to CS,这个节点在有向图遍历中具有重要意义,下面会说到。

04

如果上图有环,还正确吗?

如上所示,如果Machine learning再指向Theoretical CS,意思是选修Theoretical CS的同学需要先修Machine learning,这个就和原来的路径Artificial Intelligence依赖Theoretical CS,Machine learning 依赖Artificial Intelligence,违背!,并且也不合常理,Theoretical CS是一门基础性的理论课,怎么可能选修它之前要先修完machine learning呢?所以不能有环路,这个图是不正确的。所以,这个图必须为有向无环图!

05

有向图如何检测有、无环?

那么,如何检测一个有向图是否是DAG呢?

有向图的环检测,首先对照着无向图的环检测来理解,在无向图中,我们要检测一个图中间是否存在环,需要通过深度优先或广度优先的方式,对访问过的元素做标记。如果再次碰到前面访问过的元素,则说明可能存在环。只做标记,在有向图中检测环路的办法可行吗?

如下图所示,深度优先遍历方法,已经遍历了节点2和6,并marked了,现在遍历节点1的另一条边,依次遍历3,4,5,6,因为6已经遍历,所以说形成了环路,但是实际上并没有,因此,与实际不符合,只对访问过的元素做标记判断有无环路是错误的。

感觉是要加条件,加什么条件? 如果我们加一个数组保存当前节点是否位于递归栈onStack中,就可以排除上面的问题,因为2,6被标记后,依次递归出栈,然后到1,深度遍历1的另一条边(3->4->5->6),所以6此时不在onStack上,第一次被检测到,所以没有环路。

因此,有向图的无环检测,需要同时借助两个限制条件:

对访问过的元素做标记

当前节点是否位于递归栈onStack中

在上图的基础上,增加节点7和8,如下图所示,可以预见,按照深度优先搜索到节点4时,会找到子节点5,节点5的其中一个边找到7,找到8,找到4,节点4此时已经位于onStack中,所以构成环路,是有环图。

算法channel会有系统地,认真地推送:机器学习(包含深度学习,强化学习等)的理论,算法,实践,源码实现。期待您的参与!

本文来自企鹅号 - 全球大搜罗媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CVer

GitHub:目标检测最全论文集锦

目标检测(Object Detection)可以识别一幅图像中的多个物体,定位不同物体的同时(边界框),贴上相应的类别。简单来说,解决了what和where问题...

3452
来自专栏图形学与OpenGL

实验5 OpenGL模型视图变换

2、移动或者旋转它,当然了,如果它只是计算机里面的物体,我们还可以放大或缩小它(物体运动,让人看它的不同部分)。(模型变换)

813
来自专栏游戏开发那些事

【Cocos2d-x游戏开发】浅谈游戏中的坐标系

  无论是开发2D还是开发3D游戏,首先必须弄清楚坐标系的概念。在Cocos2d-x中,需要了解的有OpenGL坐标系、世界坐标系和节点坐标系。

753
来自专栏CreateAMind

Integration of Deep Learning and Neuroscience整合神经科学和深度学习

Neuroscience has focused on the detailed implementation of computation, studying...

1122
来自专栏hrscy

GPU 图形绘制管线

图形绘制管线描述 GPU 渲染流程,即"给定视点、三维物体、光源、照明模式和纹理等元素,如何绘制一幅二维图像"。

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

P1325 雷达安装

题目描述 描述: 假设海岸线是一条无限延伸的直线。它的一侧是陆地,另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上(包括海岸线),并且每个雷达都...

3196
来自专栏一棹烟波

求数组的局部极小值和极大值

最近看到一个有意思的求数组局部极小值,极大值的代码,贴出来分享一下,源代码是matlab版的,我用我的较为暴力的诸多for循环将其修改为C++版的,不得不感叹m...

3797
来自专栏HansBug's Lab

1059: [ZJOI2007]矩阵游戏

1059: [ZJOI2007]矩阵游戏 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2154  Solv...

2736
来自专栏生信宝典

NGS基础 - FASTQ格式解释和质量评估

FASTQ文件格式和命名 高通量测序之后用于下游分析的数据一般存储在FASTQ文件中。为了节省空间,又不影响下游使用,也一般用gzip压缩的格式。 单端测序每个...

2485
来自专栏PPV课数据科学社区

【学习】【R语言读书会】《R实战》读书笔记(第七章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

3149

扫码关注云+社区