搜尋
首頁Javajava教程有向圖之任務調度拓樸圖介紹

有向圖之任務調度拓樸圖介紹

Jun 25, 2017 am 10:59 AM
任務調度

1.有向圖的資料型別

#使用Bag表示有向圖,其中邊v->w表示為頂點v所對應的鄰接鍊錶包含一個w頂點,與無向圖不同的是,這裡每條邊只會出現一次.有向圖的資料結構型別如下:

public class Digraph {private final int V;private int E;private Bag<integer>[] adj;public Digraph(int V) {this.V=V;this.E=0;
        adj=(Bag<integer>[])new Bag[V];for(int v=0;v<v>();
        }
    }public int V() {return V;
    }public int E() {return E;
    }//添加一条边v->w,由于是有向图只要添加一条边就可以了public void addEdge(int v,int w) {
        adj[v].add(w);
        E++;
    }public Iterable<integer> adj(int v) {return adj[v];
    }//返回当前图的一个反向的图public Digraph reverse() {
        Digraph R=new Digraph(V);for(int v=0;v<v></v></integer></v></integer></integer>

 

2.有向圖中的可達性

無向圖的連結性相似,同利用深度優先搜尋可以解決有向圖中

單點可達性問題:即:給定一幅有向圖和一個起點s,回答是否存在一條從s到達給定頂點v的有向路徑的問題.

多點可達性問題:給定一幅有向圖和頂點的集合,回答是否存在一條從集合中的任意頂點到達給定頂點v的有向路徑?

public class DirectedDFS {private boolean[] marked;//从G中找出所有s可达的点public DirectedDFS(Digraph G,int s) {
        marked=new boolean[G.V()];
        dfs(G,s);
    }//G中找出一系列点可达的点public DirectedDFS(Digraph G,Iterable<integer> sources) {
        marked=new boolean[G.V()];for(int s:sources) {if(!marked[s]) dfs(G,s);
        }
    }//深度优先搜素判断.private void dfs(Digraph G, int v) { 
        marked[v]=true;for(int w:G.adj(v)) {if(!marked[w]) dfs(G,w);
        }
    }//v是可达的吗public boolean marked(int v) {return marked[v];
    }
}</integer>

多點可達性問題的一個重要時機應用是在典型的記憶體管理系統中,包括許多java的實作。在一個有向圖中,一個頂點表示一個對象,一邊則表示一個物件對另一個物件的參考。

這個模型很好表現了運行中的java程式的記憶體使用狀況。在程式執行的任何時候都有某些物件是可以被直接存取的,而不能透過這些物件存取到的所有物件都應該被回收以便

釋放記憶體。它會週期性的運行一個類似DirectedDFS的有向圖可達性演算法來標記所有可以被存取的物件。

 

3.有向圖的尋路

和無向圖類似,有向圖中常見的問題:

單點有向路徑。給定一幅有向圖和一個起點,回答「從s到給定目的頂點v是否存在一條有向路徑?如果有,找出這條路徑」

單點最短有向路徑。 給定一幅有向圖和一個起點,回答「從s到給定目的頂點v是否存在一條有向路徑,如果有,找出其中最短的那條(所含邊數最少)」

 

4.調度問題—拓樸排序

4.1尋找有向環

如果一個有優先限制的問題中存在有向環,那麼這個問題肯定是無解的。所以需要進行有向環的檢測。

下面的程式碼可以用來偵測給定的有向圖中是否含有有向環,如果有,則按照路徑的方向返回環上的所有頂點.

在執行dfs的時候,查找的是從起點到v的有向路徑,onStack數組標記了遞歸調用的棧上的所有頂點,同時也加入了edgeTo數組,在找到有向環的時候返回環中的所有頂點.

##
/**
 * 有向图G是否含有有向环
 * 获取有向环中的所有顶点
 * @author Administrator
 * */public class DirectedCycle {private boolean[] marked;    private int[] edgeTo;private Stack<integer> cycle;    //有向环中的所有顶点private boolean[] onStack;        //递归调用的栈上的所有顶点public DirectedCycle(Digraph G) {
        edgeTo=new int[G.V()];
        onStack=new boolean[G.V()];
        marked=new boolean[G.V()];for(int v=0;v<g.v>();for(int x=v;x!=w;x=edgeTo[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
            }
        }//dfs方法结束,对于该点的递归调用结束.该点指向的所有点已经遍历完毕onStack[v]=false;
    }private boolean hasCycle() {return cycle!=null;
    }public Iterable<integer> cycle() {return cycle;
    }
}</integer></g.v></integer>
 

4.2 拓撲排序

拓補排序:給定一幅有向圖,將所有的頂點排序,使得所有的有向邊均從排在前面的元素指向排在後面的元素.如果存在有向環的話,那麼拓補排序無法完成.############  要實現有向圖的拓補排序,利用標準深度優先搜尋順序即可完成任務.這裡頂點會有三種排列順序: ############  1.前序:在遞歸呼叫前將頂點加入佇列############  2.後序:在遞歸呼叫之後將頂點加入佇列############  3.逆後序:在遞歸呼叫之後將頂點壓入堆疊.############  具體的操作見下面的程式碼:## #######
//有向图中基于深度优先搜索的拓补排序public class DepthFirstOrder {private boolean[] marked;private Queue<integer> pre;        //所有顶点的前序排列private Queue<integer> post;    //所有顶点的后序排列private Stack<integer> reversePost;//所有顶点的逆后序排列public DepthFirstOrder(Digraph G) {
        pre=new Queue();
        post=new Queue();
        reversePost=new Stack();
        marked=new boolean[G.V()];        for(int v=0;v<g.v> pre() {return pre;
    }public Iterable<integer> post() {return post;
    }public Iterable<integer> reversePost() {return reversePost;
    }
}</integer></integer></g.v></integer></integer></integer>
###

遍历的顺序取决于这个数据结构的性质以及是在递归调用之前还是之后进行保存。

前序:在递归调用之前将顶点加入队列。

后序:在递归调用之后将顶点加入队列。

逆后序:在递归调用之后将顶点压入栈。

 

前序就时dfs()的调用顺序;后序就是顶点遍历完成的顺序;逆后序就是顶点遍历完成顺序的逆。

拓补排序的实现依赖于上面的API,实际上拓补排序即为所有顶点的逆后序排列

拓补排序的代码如下:

public class Topological {private Iterable<integer> order;    //顶点的拓补排序public Topological(Digraph G) {
        DirectedCycle cyclefinder=new DirectedCycle(G);if(!cyclefinder.hasCycle()) {//只有无环才能进行拓补排序DepthFirstOrder dfs=new DepthFirstOrder(G);
            order=dfs.reversePost();
        }
    }public Iterable<integer> order() {return order;
    }public boolean isDAG() {return order!=null;
    }
}</integer></integer>

 

5.有向图的强连通性

定义:如果两个顶点v和w是互相可达的,则称它们为强连通的.也就是说既存在一条从v到w的有向路径也存在一条从w到v的有向路径.

如果一幅有向图中的任意两个顶点都是强连通的,则称这副有向图也是强连通的.任意顶点和自己都是强连通的.

下面的代码采用如下步骤来计算强连通分量以及两个点是否是强连通的:

  1.在给定的有向图中,使用DepthFirsetOrder来计算它的反向图GR的逆后序排列

  2.按照第一步计算得到的顺序采用深度优先搜索来访问所有未被标记的点

  3.在构造函数中,所有在同一个递归dfs()调用中被访问到的顶点都是在同一个强连通分量中.

  下面的代码实现遵循了上面的思路:

/**
 * 该算法实现的关键:
 * 使用深度优先搜索查找给定有向图的反向图GR.根据由此得到的所有顶点的逆后序
 * 再次用深度优先搜索处理有向图G.其构造函数的每一次递归调用所标记的顶点都在
 * 同一个强连通分量中.
 * 解决问题:
 * 判断两个点是否是强连通的
 * 判断总共有多少个连通分量
 * @author Administrator
 * */public class KosarajuSCC {private boolean[] marked;//已经访问过的顶点private int[] id;        //强连通分量的标识符private int count;        //强联通分量的数量public KosarajuSCC(Digraph G) {
        marked=new boolean[G.V()];
        id=new int[G.V()];
        DepthFirstOrder order=new DepthFirstOrder(G.reverse());for(int s:order.reversePost()) {if(!marked[s]) {
                dfs(G,s);
                count++;
            }
        }
    }private void dfs(Digraph G, int v) {
        marked[v]=true;
        id[v]=count;for(int w:G.adj(v)) {if(!marked[w]) {
                dfs(G,w);
            }
        }
    }public boolean stronglyConnected(int v,int w) {return id[v]==id[w];
    }public int id(int v) {return id[v];
    }public int count() {return count;
    }
}

 

以上是有向圖之任務調度拓樸圖介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
如何將Maven或Gradle用於高級Java項目管理,構建自動化和依賴性解決方案?如何將Maven或Gradle用於高級Java項目管理,構建自動化和依賴性解決方案?Mar 17, 2025 pm 05:46 PM

本文討論了使用Maven和Gradle進行Java項目管理,構建自動化和依賴性解決方案,以比較其方法和優化策略。

如何使用適當的版本控制和依賴項管理創建和使用自定義Java庫(JAR文件)?如何使用適當的版本控制和依賴項管理創建和使用自定義Java庫(JAR文件)?Mar 17, 2025 pm 05:45 PM

本文使用Maven和Gradle之類的工具討論了具有適當的版本控制和依賴關係管理的自定義Java庫(JAR文件)的創建和使用。

如何使用咖啡因或Guava Cache等庫在Java應用程序中實現多層緩存?如何使用咖啡因或Guava Cache等庫在Java應用程序中實現多層緩存?Mar 17, 2025 pm 05:44 PM

本文討論了使用咖啡因和Guava緩存在Java中實施多層緩存以提高應用程序性能。它涵蓋設置,集成和績效優勢,以及配置和驅逐政策管理最佳PRA

如何將JPA(Java持久性API)用於具有高級功能(例如緩存和懶惰加載)的對象相關映射?如何將JPA(Java持久性API)用於具有高級功能(例如緩存和懶惰加載)的對象相關映射?Mar 17, 2025 pm 05:43 PM

本文討論了使用JPA進行對象相關映射,並具有高級功能,例如緩存和懶惰加載。它涵蓋了設置,實體映射和優化性能的最佳實踐,同時突出潛在的陷阱。[159個字符]

Java的類負載機制如何起作用,包括不同的類載荷及其委託模型?Java的類負載機制如何起作用,包括不同的類載荷及其委託模型?Mar 17, 2025 pm 05:35 PM

Java的類上載涉及使用帶有引導,擴展程序和應用程序類負載器的分層系統加載,鏈接和初始化類。父代授權模型確保首先加載核心類別,從而影響自定義類LOA

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
4 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
4 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
4 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.聊天命令以及如何使用它們
4 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

mPDF

mPDF

mPDF是一個PHP庫,可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件,並處理不同的語言。與原始腳本如HTML2FPDF相比,它的速度較慢,並且在使用Unicode字體時產生的檔案較大,但支援CSS樣式等,並進行了大量增強。支援幾乎所有語言,包括RTL(阿拉伯語和希伯來語)和CJK(中日韓)。支援嵌套的區塊級元素(如P、DIV),

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

EditPlus 中文破解版

EditPlus 中文破解版

體積小,語法高亮,不支援程式碼提示功能

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )專業的PHP整合開發工具

WebStorm Mac版

WebStorm Mac版

好用的JavaScript開發工具