有向图的环和有向无环图

本篇主要分享关于有向图的环和有向无环图(DAG,估计做大数据的同学到处都可以看到),所以相关概念我就不做详细介绍了。

用有向图中各个节点代表着一个又一个的任务,而其中的方向代表的任务的执行顺序。而方向代表着这个在执行这个任务之前必须完成其他节点,例如上图中在5执行必须执行3和0 节点。

所以可以想到有向图中有向环的检测非常重要,例如上面 要是5之前 3要执行,3之前4要执行,4之前5要执行,那么着三个限制条件永远事不可能被执行的,要是一个优先级限制的问题中存在有向环,那么这个问题肯定是无解的。

有向环的检测的理念是我们找到了一条边v-》w 要是w已经存在在栈中,就找到了一个环,因为栈中表示的是一条有w-》v的路径,而v-》w正好补全了这个环。也就是存在有向环。所以这个优先任务是有问题的。

public classDirectedCycle {

private boolean[] marked;

private int[] edgeTo;

privateStack cycle;

private boolean[] onStack;

publicDirectedCycle(Digraph G) {

onStack =new boolean[G.V()];

edgeTo =new int[G.V()];

marked =new boolean[G.V()];

for(intv =;v

if(!marked[v]) {

dfs(G,v);

}

}

}

private voiddfs(Digraph G, intv) {

onStack[v] =true;

marked[v] =true;

for(intw : G.adj(v)) {

if(this.hasCycle()) {

return;

}else if(!marked[w]) {

edgeTo[w] = v;

dfs(G,w);

}else if(onStack[w]) {

cycle =newStack();

for(intx = v;x != w;x = edgeTo[x]) {

cycle.push(x);

}

cycle.push(w);

cycle.push(v);

}

}

onStack[v] =false;

}

public booleanhasCycle() {

returncycle !=null;

}

publicIterable cycle() {

returncycle;

}

}

猜你喜欢

大数据和云计算技术周报(第56期)

加入技术讨论群

《大数据和云计算技术》社区群人数已经3000+,欢迎大家加下面助手微信,拉大家进群,自由交流。

喜欢QQ群的,可以扫描下面二维码:

欢迎大家通过二维码打赏支持技术社区(英雄请留名,社区感谢您,打赏次数超过108+):

  • 发表于:
  • 原文链接:https://kuaibao.qq.com/s/20180725B080IQ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券