您的位置:首页 > 教程 > 服务端类 > Golang > 基于Java实现无向环和有向环的检测

基于Java实现无向环和有向环的检测

2022-04-06 15:17:45 来源:易采站长站 作者:

基于Java实现无向环和有向环的检测

目录
无向环有向环有向图检测算法

无向环

一个含有环的无向图如下所示,其中有两个环,分别是 0-2-1-0 和 2-3-4-2:

要检测无向图中的环,可以使用深度优先搜索。假设从顶点 0 出发,再走到相邻的顶点 2,接着走到顶点 2 相邻的顶点 1,由于顶点 0 和顶点 1 相邻,并且顶点 0 被标记过了,说明我们饶了一圈,所以无向图中存在环。虽然顶点 2 和顶点 1 相邻,但是并不能说明存在环,因为我们就是从顶点 2 直接走到顶点 1 的,这二者只有边的关系。算法如下所示:

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.stack.LinkStack;
import com.zhiyiyo.collection.stack.Stack;

/**
 * 无向图中的环
 */
public class Cycle {
    private boolean[] marked;
    private Graph graph;
    private boolean hasCycle;

    public Cycle(Graph graph) {
        this.graph = graph;
        marked = new boolean[graph.V()];

        for (int v = 0; v < graph.V(); ++v) {
            if (!marked[v]) {
                dfs(v);
            }
        }
    }

    private void dfs(int s) {
        if (hasCycle()) return;

        Stack<Integer> vertexes = new LinkStack<>();
        vertexes.push(s);
        marked[s] = true;

        int lastVertex = s;
        while (!vertexes.isEmpty()) {
            int v = vertexes.pop();

            for (int w : graph.adj(v)) {
                if (!marked[w]) {
                    marked[w] = true;
                    vertexes.push(w);
                } else if (w != lastVertex) {
                    hasCycle = true;
                    return;
                }
            }

            lastVertex = v;
        }
    }

    /**
     * 图中是否有环
     */
    public boolean hasCycle() {
        return hasCycle;
    }
}

有向环

有向图

有向图的实现方式和上一篇博客 《如何在 Java 中实现无向图》 中无向图的实现方式几乎一样,只是在添加边 v-w 时只在顶点 v 的链表上添加顶点 w,而不对顶点 w 的链表进行操作。如果把 LinkGraph 中成员变量的访问权限改成 protected,只需继承并重写 addEdge 方法即可:

package com.zhiyiyo.graph;


public class LinkDigraph extends LinkGraph implements Digraph {

    public LinkDigraph(int V) {
        super(V);
    }

    @Override
    public void addEdge(int v, int w) {
        adj[v].push(w);
        E++;
    }

    @Override
    public Digraph reverse() {
        Digraph digraph = new LinkDigraph(V());
        for (int v = 0; v < V(); ++v) {
            for (int w : adj(v)) {
                digraph.addEdge(w, v);
            }
        }
        return digraph;
    }
}

检测算法

一个含有有向环的有向图如下所示,其中 5-4-3-5 构成了一个环:

这里使用递归实现的深度优先搜索来检测有向环。假设从顶点 0 开始走,一路经过 5、4、3 这三个顶点,最终又碰到了与顶点 3 相邻的顶点 5,这时候如果知道顶点 5 已经被访问过了,并且递归函数还被压在栈中,就说明深度优先搜索从顶点 5 开始走,又回到了顶点 5,也就是找到了有向环。算法如下所示:

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.stack.LinkStack;
import com.zhiyiyo.collection.stack.Stack;

/**
 * 有向图中的环
 */
public class DirectedCycle {
    private boolean[] marked;
    private boolean[] onStack;
    private int[] edgeTo;
    private Graph graph;
    private Stack<Integer> cycle;

    public DirectedCycle(Digraph graph) {
        this.graph = graph;
        marked = new boolean[graph.V()];
        onStack = new boolean[graph.V()];
        edgeTo = new int[graph.V()];

        for (int v = 0; v < graph.V(); ++v) {
            if (!marked[v]) {
                dfs(v);
            }
        }
    }

    private void dfs(int v) {
        marked[v] = true;
        onStack[v] = true;

        for (int w : graph.adj(v)) {
            if (hasCycle()) return;
            if (!marked[w]) {
                marked[w] = true;
                edgeTo[w] = v;
                dfs(w);
            } else if (onStack[w]) {
                cycle = new LinkStack<>();
                cycle.push(w);
                for (int i = v; i != w; i = edgeTo[i]) {
                    cycle.push(i);
                }
                cycle.push(w);
            }
        }

        onStack[v] = false;
    }

    /**
     * 图中是否有环
     */
    public boolean hasCycle() {
        return cycle != null;
    }

    /**
     * 图中的一个环
     */
    public Iterable<Integer> cycle() {
        return cycle;
    }
}

以上就是基于Java实现无向环和有向环的检测的详细内容,更多关于Java无向环 有向环的资料请关注易采站长站其它相关文章!

如有侵权,请联系QQ:279390809 电话:15144810328

相关文章

  • golang用什么开发工具?

    golang用什么开发工具?

    golang用的开发工具有:1、Go Revive,是一个Go语言的代码质量检测工具;2、Go Callvis,可以用来可视化Go程序的调用图;3、Gaia,高效,快速,轻量级,并且对开发人员友好。golang用的开发工具有:1、Go Reviverevive 是一个 Go 语言的代码质量检测工具(Linter for Go),具有快速、可配置、可扩展、灵活和美观等特性,可作为 golint 的替
    2020-08-07
  • golang是多线程模式吗?

    golang是多线程模式吗?

    golang是多线程模式的,golang的线程模型是M P G模型,整体上Go程与内核线程是多对多对应的,因此首先来讲就一定是多线程的。golang是多线程模式。 由于gmp中的p与m是将p绑定与m内核线程上,而后p的最大数量有GOPROCESS确定,而M内核线程的数量会由go去限制为10K个,但是由于内核原因做不到这么多,所以这个限制就当做没有吧。拿个图明确一下Golang有些所谓的M比N模型,
    2020-08-07
  • golang用什么开发工具?

    golang用什么开发工具?

    golang用的开发工具有:1、Go Revive,是一个Go语言的代码质量检测工具;2、Go Callvis,可以用来可视化Go程序的调用图;3、Gaia,高效,快速,轻量级,并且对开发人员友好。golang用的开发工具有:1、Go Reviverevive 是一个 Go 语言的代码质量检测工具(Linter for Go),具有快速、可配置、可扩展、灵活和美观等特性,可作为 golint 的替
    2020-08-07
  • golang是单进程的吗?

    golang是单进程的吗?

    golang不是单进程的,而是多线程;golang的线程模型是M P G模型,整体上Go程与内核线程是多对多对应的,因此首先来讲就一定是多线程的。golang不是单进程的,而是多线程。Golang有些所谓的M比N模型,M个线程下可以创建N个go routine,一般而言N远大于M,本质上属于多线程模型,但是协程的调度由Go的runtime决定,强调开发者应该使用channel进行协程之间的同步。至
    2020-08-07
  • 代码详解使用Go基于WebSocket构建视频直播弹幕系统

    代码详解使用Go基于WebSocket构建视频直播弹幕系统

    (1)业务复杂度介绍开门见山,假设一个直播间同时500W人在线,那么1秒钟1000条弹幕,那么弹幕系统的推送频率就是: 500W * 1000条/秒=50亿条/秒 ,想想B站2019跨年晚会那次弹幕系统得是多么的NB,况且一个大型网站不可能只有一个直播间!使用Go做WebSocket开发无非就是三种情况:使用Go原生自带的库,也就是 golang.org/x/net ,但是这个官方库真是出了奇Bu
    2020-08-07
  • PHP语法和Go语法有什么差异?对比介绍

    PHP语法和Go语法有什么差异?对比介绍

    本篇文章给大家对比一下PHP语法和Go语法,带大家了解一下PHP语法和Go语法之间的差异。有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。Go 是由 Google 设计的一门静态类型的编译型语言。它有点类似于 C,但是它包含了更多的优点,比如垃圾回收、内存安全、结构类型和并发性。它的并发机制使多核和网络机器能够发挥最大的作用。这是 GoLang 的最佳卖点之一。此外,Go 速度快,
    2020-08-07
  • golang需要什么基础?

    golang需要什么基础?

    golang需要什么基础?golang需要的基础是:Go语言语法特别简单简洁,有C的底子更好,差一些也没关系。前提是你要真心想学,才有足够的动力去学。1、初学Go语言首先弄懂基础语法和概念:基本数据类型、Struct、Array、map、Slice、指针、接口、map、内置函数,常用工具包等,还有接口和Slice的底层数据结构。这些不需要弄特别懂,能自己理解并自己描述我觉得就可以了,关键在实践和应
    2020-08-07
  • golang为什么那么火?

    golang为什么那么火?

    golang为什么那么火?golang那么火的原因:1, Concurrency的原生支持通过语言原生的Goroutine和Channel,很好的支持了Concurrency。你可以把Goroutine理解为非常轻量级的Thread。一个Goroutine只占用2KB的内存,但是一个Thread要占用1MB的内存。Goroutine的创建、销毁和切换的开销,相对于线程来说特别低。你可以随时起上千个
    2020-08-07