基于Java實現無向環(huán)和有向環(huán)的檢測

更新時間：2022年04月06日 11:07:41 作者：之一Yo

這篇文章主要介紹了如何在?Java?中實現無向環(huán)和有向環(huán)的檢測，文中的示例代碼講解詳細，對我們學習Java有一定的幫助，需要的可以參考一下

無向環(huán)

一個含有環(huán)的無向圖如下所示，其中有兩個環(huán)，分別是 0-2-1-0 和 2-3-4-2：

要檢測無向圖中的環(huán)，可以使用深度優(yōu)先搜索。假設從頂點 0 出發(fā)，再走到相鄰的頂點 2，接著走到頂點 2 相鄰的頂點 1，由于頂點 0 和頂點 1 相鄰，并且頂點 0 被標記過了，說明我們饒了一圈，所以無向圖中存在環(huán)。雖然頂點 2 和頂點 1 相鄰，但是并不能說明存在環(huán)，因為我們就是從頂點 2 直接走到頂點 1 的，這二者只有邊的關系。算法如下所示：

package com.zhiyiyo.graph;

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

/**
 * 無向圖中的環(huán)
 */
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;
        }
    }

    /**
     * 圖中是否有環(huán)
     */
    public boolean hasCycle() {
        return hasCycle;
    }
}

有向環(huán)

有向圖

有向圖的實現方式和上一篇博客《如何在 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;
    }
}

檢測算法

一個含有有向環(huán)的有向圖如下所示，其中 5-4-3-5 構成了一個環(huán)：

這里使用遞歸實現的深度優(yōu)先搜索來檢測有向環(huán)。假設從頂點 0 開始走，一路經過 5、4、3 這三個頂點，最終又碰到了與頂點 3 相鄰的頂點 5，這時候如果知道頂點 5 已經被訪問過了，并且遞歸函數還被壓在棧中，就說明深度優(yōu)先搜索從頂點 5 開始走，又回到了頂點 5，也就是找到了有向環(huán)。算法如下所示：

package com.zhiyiyo.graph;

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

/**
 * 有向圖中的環(huán)
 */
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;
    }

    /**
     * 圖中是否有環(huán)
     */
    public boolean hasCycle() {
        return cycle != null;
    }

    /**
     * 圖中的一個環(huán)
     */
    public Iterable<Integer> cycle() {
        return cycle;
    }
}

以上就是基于Java實現無向環(huán)和有向環(huán)的檢測的詳細內容，更多關于Java無向環(huán) 有向環(huán)的資料請關注腳本之家其它相關文章！

您可能感興趣的文章:

HttpClient的KeepAlive接口方法源碼解析
這篇文章主要為大家介紹了HttpClient的KeepAlive接口方法源碼解析,
有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
2023-10-10
初學者易上手的SSH-struts2 01環(huán)境搭建(圖文教程)
下面小編就為大家?guī)硪黄鯇W者易上手的SSH-struts2 01環(huán)境搭建(圖文教程)。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2017-10-10
一文秒懂?kafka?HA（高可用）
這篇文章主要介紹了秒懂?kafka?HA（高可用）的相關知識，本文我們來說一說和?kafka?高可用相關的一些策略,對kafka?HA相關知識感興趣的朋友一起看看吧
2021-11-11
MyBatis官方代碼生成工具給力(解放雙手)
這篇文章主要介紹了MyBatis官方代碼生成工具給力(解放雙手)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2020-12-12
Java數據結構與算法之棧(Stack)實現詳解
這篇文章主要為大家詳細介紹了Java數據結構學習筆記第二篇，Java數據結構與算法之棧Stack實現，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2017-09-09
SpringBoot 下在 yml 中的 logging 日志配置方法
logging 配置主要用于控制應用程序的日志輸出行為,可以通過配置定制日志的格式、級別、輸出位置等,這篇文章主要介紹了SpringBoot 下在 yml 中的 logging 日志配置,需要的朋友可以參考下
2024-06-06
Spring中Cache的使用方法詳解
這篇文章主要介紹了Spring中Cache的使用方法詳解,Spring Cache 是一個框架,實現了基于注解的緩存功能,只需要簡單地加一個注解,就能實現緩存功能,Spring Cache 提供了一層抽象,底層可以切換不同的緩存實現,需要的朋友可以參考下
2024-01-01
spring boot 集成 shiro 自定義密碼驗證自定義freemarker標簽根據權限渲染不同頁面(推薦
這篇文章主要介紹了spring-boot 集成 shiro 自定義密碼驗證自定義freemarker標簽根據權限渲染不同頁面,需要的朋友可以參考下
2018-12-12
MybatisPlus查詢條件空字符串和NULL問題背景分析
文章詳細分析了MybatisPlus在處理查詢條件時,空字符串和NULL值的問題,MP 3.3.0及以上版本提供了多種解決方法,包括在Bean屬性上使用注解、全局配置等,推薦使用全局配置的方式來解決這個問題,以避免在SQL查詢中出現不必要的空字符串條件,感興趣的朋友跟隨小編一起看看吧
2025-03-03
SpringBoot2.0整合jackson配置日期格式化和反序列化的實現
這篇文章主要介紹了SpringBoot2.0整合jackson配置日期格式化和反序列化的實現，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2018-11-11