有向无环图(拓扑图)5分钟理清思路

我们先看解题步骤:

1.建塔:以每个未出现过的点为顶点建立金字塔。

   1.1.测环:建立过程中每个查询到的节点都记录到一个数组,如果出现重复,即有环。

   1.2保存被依赖:记录每个元素被依赖的元素。

2.去重:如果元素在金字塔底层出现,就不能在上层出现,即向上去重(被依赖的元素永远在依赖元素的上层)。

3.合并:所有金字塔根据共同元素进行合并(从上层开始遍历查找第一个共同元素)并去重。

4.定位:经过以上步骤,所有金字塔或两两之间(现在顶端可能有很多个元素,应该叫做每一栋楼)没有重复元素。找到每个元素所在的金字塔,以及所在层,与1.2中记录的被依赖元素一起保存。

经过以上步骤,所有元素在对应塔里面有了它对应的层级,以及上层依赖它的元素,无论从哪一层哪一个元素开始都可以往上找到所有依赖关系。

再看解题思路

目的:理清各个元素之间的依赖关系

解题思路:即是依赖关系,便有层级结构,以公司结构为例,普工,主管,秘书,老板,,普工依赖主管和老板,主管依赖老板,秘书依赖老板,秘书依赖主管。。。。但老板不能依赖普工,秘书不能依赖普工,否则会形成环。 这个例子当中层级关系是普工,秘书,主管,老板。    由于秘书依赖主管,所以秘书层级在主管下面,而不是老板下面(例子不合理现实别计较)。

建模:由思路得出可以用等级来解决,以大厦为模型,楼层就是级别,把所有人按分好层级,即如果有人级别高,那他依赖的人必然级别低于他,如果他被低级别的人依赖了,那他的级别必须降到低级别的人下面去。

行为方式:每个人身上都记录了自己所在的楼以及楼层,以及依赖他的人的id,也就是找到这个人就可以找到他所有依赖他的人。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。