Java數(shù)據(jù)結(jié)構(gòu)之有向圖的拓?fù)渑判蛟斀?/h1>

 更新時(shí)間：2022年11月03日 08:25:30   作者：JAVA旭陽(yáng)  

這篇文章主要為大家詳細(xì)介紹了Java數(shù)據(jù)結(jié)構(gòu)中有向圖的拓?fù)渑判?，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，感興趣的小伙伴可以了解一下

目錄

• 前言
• 拓?fù)渑判蚪榻B
• 檢測(cè)有向圖中的環(huán)
• 實(shí)現(xiàn)思路
• API設(shè)計(jì)
• 代碼實(shí)現(xiàn)
• 基于深度優(yōu)先的頂點(diǎn)排序
• 實(shí)現(xiàn)思路
• API設(shè)計(jì)
• 代碼實(shí)現(xiàn)
• 拓?fù)渑判?/a>
• API設(shè)計(jì)
• 代碼實(shí)現(xiàn)
• 測(cè)試驗(yàn)證

前言

在現(xiàn)實(shí)生活中，我們經(jīng)常會(huì)同一時(shí)間接到很多任務(wù)去完成，但是這些任務(wù)的完成是有先后次序的。以我們學(xué)習(xí)java

學(xué)科為例，我們需要學(xué)習(xí)很多知識(shí)，但是這些知識(shí)在學(xué)習(xí)的過(guò)程中是需要按照先后次序來(lái)完成的。從java基礎(chǔ)，到

jsp/servlet，到ssm，到springboot等是個(gè)循序漸進(jìn)且有依賴(lài)的過(guò)程。在學(xué)習(xí)jsp前要首先掌握java基礎(chǔ)和html基

礎(chǔ)，學(xué)習(xí)ssm框架前要掌握jsp/servlet之類(lèi)才行。

為了簡(jiǎn)化問(wèn)題，我們使用整數(shù)為頂點(diǎn)編號(hào)的標(biāo)準(zhǔn)模型來(lái)表示這個(gè)案例：

此時(shí)如果某個(gè)同學(xué)要學(xué)習(xí)這些課程，就需要指定出一個(gè)學(xué)習(xí)的方案，我們只需要對(duì)圖中的頂點(diǎn)進(jìn)行排序，讓它轉(zhuǎn)換為一個(gè)線性序列，就可以解決問(wèn)題，這時(shí)就需要用到一種叫拓?fù)渑判?/strong>的算法。

拓?fù)渑判蚪榻B

給定一副有向圖，將所有的頂點(diǎn)排序，使得所有的有向邊均從排在前面的元素指向排在后面的元素，此時(shí)就可以明確的表示出每個(gè)頂點(diǎn)的優(yōu)先級(jí)。下列是一副拓?fù)渑判蚝蟮氖疽鈭D:

檢測(cè)有向圖中的環(huán)

如果學(xué)習(xí)x課程前必須先學(xué)習(xí)y課程，學(xué)習(xí)y課程前必須先學(xué)習(xí)z課程，學(xué)習(xí)z課程前必須先學(xué)習(xí)x課程，那么一定是有問(wèn)題了，我們就沒(méi)有辦法學(xué)習(xí)了，因?yàn)檫@三個(gè)條件沒(méi)有辦法同時(shí)滿足。其實(shí)這三門(mén)課程x、y、z的條件組成了一個(gè)環(huán)：

因此，如果我們要使用拓?fù)渑判蚪鉀Q優(yōu)先級(jí)問(wèn)題，首先得保證圖中沒(méi)有環(huán)的存在。

實(shí)現(xiàn)思路

在API中添加了onStack[] 布爾數(shù)組，索引為圖的頂點(diǎn)，當(dāng)我們深度搜索時(shí)：

• 在如果當(dāng)前頂點(diǎn)正在搜索，則把對(duì)應(yīng)的onStack數(shù)組中的值改為true，標(biāo)識(shí)進(jìn)棧；
• 如果當(dāng)前頂點(diǎn)搜索完畢，則把對(duì)應(yīng)的onStack數(shù)組中的值改為false，標(biāo)識(shí)出棧；
• 如果即將要搜索某個(gè)頂點(diǎn)，但該頂點(diǎn)已經(jīng)在棧中，則圖中有環(huán)；

API設(shè)計(jì)

類(lèi)名	DirectedCycle
成員變量	1.private boolean[] marked: 索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索2.private boolean hasCycle: 記錄圖中是否有環(huán)3.private boolean[] onStack:索引代表頂點(diǎn)，使用棧的思想，記錄當(dāng)前頂點(diǎn)有沒(méi)有已經(jīng)處于正在搜索的有向路徑上
構(gòu)造方法	DirectedCycle(Digraph G)：創(chuàng)建一個(gè)檢測(cè)環(huán)對(duì)象，檢測(cè)圖G中是否有環(huán)
成員方法	1.private void dfs(Digraph G,int v)：基于深度優(yōu)先搜索，檢測(cè)圖G中是否有環(huán)2.public boolean hasCycle():判斷圖中是否有環(huán)

代碼實(shí)現(xiàn)

/**
 * 有向圖是否存在環(huán)
 *
 * @author alvin
 * @date 2022/11/2
 * @since 1.0
 **/
public class DirectedCycle {
    //索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索
    private boolean[] marked;
    //記錄圖中是否有環(huán)
    private boolean hasCycle;
    //索引代表頂點(diǎn)，使用棧的思想，記錄當(dāng)前頂點(diǎn)有沒(méi)有已經(jīng)處于正在搜索的有向路徑上
    private boolean[] onStack;

    //創(chuàng)建一個(gè)檢測(cè)環(huán)對(duì)象，檢測(cè)圖G中是否有環(huán)
    public DirectedCycle(Digraph G){
        //初始化marked數(shù)組
        this.marked = new boolean[G.V()];
        //初始化hasCycle
        this.hasCycle = false;
        //初始化onStack數(shù)組
        this.onStack = new boolean[G.V()];

        //找到圖中每一個(gè)頂點(diǎn)，讓每一個(gè)頂點(diǎn)作為入口，調(diào)用一次dfs進(jìn)行搜索
        for (int v =0; v<G.V();v++){
            //判斷如果當(dāng)前頂點(diǎn)還沒(méi)有搜索過(guò)，則調(diào)用dfs進(jìn)行搜索
            if (!marked[v]){
                dfs(G,v);
            }
        }
    }

    //基于深度優(yōu)先搜索，檢測(cè)圖G中是否有環(huán)
    private void dfs(Digraph G, int v){
        //把頂點(diǎn)v表示為已搜索
        marked[v] = true;
        //把當(dāng)前頂點(diǎn)進(jìn)棧
        onStack[v] = true;

        for(Integer w: G.adj(v)) {
            //判斷如果當(dāng)前頂點(diǎn)w沒(méi)有被搜索過(guò)，則繼續(xù)遞歸調(diào)用dfs方法完成深度優(yōu)先搜索
            if(!marked[w]) {
                dfs(G, w);
            }

            //判斷當(dāng)前頂點(diǎn)w是否已經(jīng)在棧中，如果已經(jīng)在棧中，證明當(dāng)前頂點(diǎn)之前處于正在搜索的狀態(tài)，那么現(xiàn)在又要搜索一次，證明檢測(cè)到環(huán)了
            if (onStack[w]){
                hasCycle = true;
                return;
            }
        }
        //把當(dāng)前頂點(diǎn)出棧
        onStack[v] = false;
    }

    //判斷當(dāng)前有向圖G中是否有環(huán)
    public boolean hasCycle(){
        return hasCycle;
    }
}

基于深度優(yōu)先的頂點(diǎn)排序

實(shí)現(xiàn)思路

如果要把圖中的頂點(diǎn)生成線性序列其實(shí)是一件非常簡(jiǎn)單的事，之前我們學(xué)習(xí)并使用了多次深度優(yōu)先搜索，我們會(huì)發(fā)現(xiàn)其實(shí)深度優(yōu)先搜索有一個(gè)特點(diǎn)，那就是在一個(gè)連通子圖上，每個(gè)頂點(diǎn)只會(huì)被搜索一次，如果我們能在深度優(yōu)先搜索的基礎(chǔ)上，添加一行代碼，只需要將搜索的頂點(diǎn)放入到線性序列的數(shù)據(jù)結(jié)構(gòu)中，我們就能完成這件事。

我們添加了一個(gè)棧reversePost用來(lái)存儲(chǔ)頂點(diǎn)，當(dāng)我們深度搜索圖時(shí)，每搜索完畢一個(gè)頂點(diǎn)，把該頂點(diǎn)放入到reversePost中，這樣就可以實(shí)現(xiàn)頂點(diǎn)排序。

API設(shè)計(jì)

類(lèi)名	DepthFirstOrder
成員變量	1.private boolean[] marked: 索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索2.private Stack reversePost: 使用棧，存儲(chǔ)頂點(diǎn)序列
構(gòu)造方法	DepthFirstOrder(Digraph G)：創(chuàng)建一個(gè)頂點(diǎn)排序?qū)ο?，生成頂點(diǎn)線性序列；
成員方法	1.private void dfs(Digraph G,int v)：基于深度優(yōu)先搜索，生成頂點(diǎn)線性序列2.public Stack reversePost():獲取頂點(diǎn)線性序列

代碼實(shí)現(xiàn)

/**
 * 頂點(diǎn)排序
 *
 * @author alvin
 * @date 2022/11/2
 * @since 1.0
 **/
public class DepthFirstOrder {
    //索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索
    private boolean[] marked;
    //使用棧，存儲(chǔ)頂點(diǎn)序列
    private Stack<Integer> reversePost;

    //創(chuàng)建一個(gè)檢測(cè)環(huán)對(duì)象，檢測(cè)圖G中是否有環(huán)
    public DepthFirstOrder(Digraph G){
        //初始化marked數(shù)組
        this.marked = new boolean[G.V()];
        //初始化reversePost棧
        this.reversePost = new Stack<>();

        //遍歷圖中的每一個(gè)頂點(diǎn)，讓每個(gè)頂點(diǎn)作為入口，完成一次深度優(yōu)先搜索
        for (int v = 0;v<G.V();v++){
            if (!marked[v]){
                dfs(G,v);
            }
        }
    }

    //基于深度優(yōu)先搜索，把頂點(diǎn)排序
    private void dfs(Digraph G, int v){
        //標(biāo)記當(dāng)前v已經(jīng)被搜索
        marked[v] = true;
        //通過(guò)循環(huán)深度搜索頂點(diǎn)v
        for (Integer w : G.adj(v)) {
            //如果當(dāng)前頂點(diǎn)w沒(méi)有搜索，則遞歸調(diào)用dfs進(jìn)行搜索
            if (!marked[w]){
                dfs(G,w);
            }
        }
        //讓頂點(diǎn)v進(jìn)棧
        reversePost.push(v);
    }

    //獲取頂點(diǎn)線性序列
    public Stack<Integer>  reversePost(){
        return reversePost;
    }
}

拓?fù)渑判?/h2>

前面已經(jīng)實(shí)現(xiàn)了環(huán)的檢測(cè)以及頂點(diǎn)排序，那么拓?fù)渑判蚓秃芎?jiǎn)單了，基于一幅圖，先檢測(cè)有沒(méi)有環(huán)，如果沒(méi)有環(huán)，則調(diào)用頂點(diǎn)排序即可。

API設(shè)計(jì)

類(lèi)名	TopoLogical
成員變量	1.private Stack order: 頂點(diǎn)的拓?fù)渑判?/td>
構(gòu)造方法	TopoLogical(Digraph G)：構(gòu)造拓?fù)渑判驅(qū)ο?/td>
成員方法	1.public boolean isCycle()：判斷圖G是否有環(huán)2.public Stack order():獲取拓?fù)渑判虻乃许旤c(diǎn)

代碼實(shí)現(xiàn)

/**
 * 拓?fù)渑判?
 *
 * @author alvin
 * @date 2022/11/2
 * @since 1.0
 **/
public class TopoLogical {
    //頂點(diǎn)的拓?fù)渑判?
    private Stack<Integer> order;

    //構(gòu)造拓?fù)渑判驅(qū)ο?
    public TopoLogical(Digraph G) {
        //創(chuàng)建一個(gè)檢測(cè)有向環(huán)的對(duì)象
        DirectedCycle cycle = new DirectedCycle(G);
        //判斷G圖中有沒(méi)有環(huán)，如果沒(méi)有環(huán)，則進(jìn)行頂點(diǎn)排序：創(chuàng)建一個(gè)頂點(diǎn)排序?qū)ο?
        if (!cycle.hasCycle()){
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
            order = depthFirstOrder.reversePost();
        }
    }

    //判斷圖G是否有環(huán)
    private boolean isCycle(){
        return order==null;
    }

    //獲取拓?fù)渑判虻乃许旤c(diǎn)
    public Stack<Integer> order(){
        return order;
    }
}

測(cè)試驗(yàn)證

public class TopoLogicalTest {

    @Test
    public void test() {
        //準(zhǔn)備有向圖
        Digraph digraph = new Digraph(6);
        digraph.addEdge(0,2);
        digraph.addEdge(0,3);
        digraph.addEdge(2,4);
        digraph.addEdge(3,4);
        digraph.addEdge(4,5);
        digraph.addEdge(1,3);

        //通過(guò)TopoLogical對(duì)象堆有向圖中的頂點(diǎn)進(jìn)行排序
        TopoLogical topoLogical = new TopoLogical(digraph);

        //獲取頂點(diǎn)的線性序列進(jìn)行打印
        Stack<Integer> order = topoLogical.order();
        StringBuilder sb = new StringBuilder();
        while (order.size() != 0) {
            sb.append(order.pop()+"->");
        };
        String str = sb.toString();
        int index = str.lastIndexOf("->");
        str = str.substring(0,index);
        System.out.println(str);
    }
}

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之有向圖的拓?fù)渑判蛟斀獾奈恼戮徒榻B到這了,更多相關(guān)Java有向圖 拓?fù)渑判騼?nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

• 詳解Java實(shí)現(xiàn)拓?fù)渑判蛩惴?/a>
• Java實(shí)現(xiàn)拓?fù)渑判虻氖纠a
• Java實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ氖纠a
• Java數(shù)據(jù)結(jié)構(gòu)之圖的基礎(chǔ)概念和數(shù)據(jù)模型詳解
• Java數(shù)據(jù)結(jié)構(gòu)之圖的兩種搜索算法詳解
• Java數(shù)據(jù)結(jié)構(gòu)之圖的路徑查找算法詳解
• Java數(shù)據(jù)結(jié)構(gòu)之有向圖設(shè)計(jì)與實(shí)現(xiàn)詳解

• Java
• 有向圖
• 拓?fù)渑判?/a>

相關(guān)文章

• 

  Mybatis如何獲取insert新增數(shù)據(jù)id值

  這篇文章主要介紹了Mybatis如何獲取insert新增數(shù)據(jù)id值問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教

  2024-05-05
• 

  關(guān)于SpringCloud的微服務(wù)以及組件詳解

  這篇文章主要介紹了關(guān)于SpringCloud的微服務(wù)以及組件詳解,是一個(gè)更高層次的、 架構(gòu)視角的綜合性大型項(xiàng)目， 他的目標(biāo)是構(gòu)建一套標(biāo)準(zhǔn)化的微服務(wù)解決方案,需要的朋友可以參考下

  2023-05-05
• 

  java仿windows記事本小程序

  這篇文章主要為大家詳細(xì)介紹了java仿windows記事本小程序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

  2019-03-03
• 

  redis incr和incrBy的使用說(shuō)明

  這篇文章主要介紹了redis incr和incrBy的使用說(shuō)明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧

  2020-11-11
• 

  Java中過(guò)濾器 (Filter) 和 攔截器 (Interceptor)的使用

  這篇文章主要介紹了Java中過(guò)濾器 (Filter) 和 攔截器 (Interceptor)的使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

  2021-05-05
• 

  Java結(jié)合redistemplate使用分布式鎖案例講解

  在Java中使用RedisTemplate結(jié)合Redis來(lái)實(shí)現(xiàn)分布式鎖是一種常見(jiàn)的做法,特別適用于微服務(wù)架構(gòu)或多實(shí)例部署的應(yīng)用程序中,以確保數(shù)據(jù)的一致性和避免競(jìng)態(tài)條件,下面給大家分享使用Spring Boot和RedisTemplate實(shí)現(xiàn)分布式鎖的案例,感興趣的朋友一起看看吧

  2024-08-08
• 

  nacos單機(jī)版啟動(dòng)失敗問(wèn)題以及解決

  這篇文章主要介紹了nacos單機(jī)版啟動(dòng)失敗問(wèn)題以及解決,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教

  2024-07-07
• 

  Java中Properties的使用詳解

  這篇文章主要介紹了Java中Properties的使用詳解的相關(guān)資料,需要的朋友可以參考下

  2016-05-05
• 

  Spring+Mybatis+Mysql搭建分布式數(shù)據(jù)庫(kù)訪問(wèn)框架的方法

  這篇文章主要介紹了Spring+Mybatis+Mysql搭建分布式數(shù)據(jù)庫(kù)訪問(wèn)框架的方法，非常不錯(cuò)，具有參考借鑒價(jià)值,需要的朋友可以參考下

  2018-03-03
• 

  mybatis新增save結(jié)束后自動(dòng)返回主鍵id詳解

  這篇文章主要介紹了mybatis新增save結(jié)束后自動(dòng)返回主鍵id詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

  2021-12-12

最新評(píng)論