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

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;v++) {
            adj[v]=new Bag<Integer>();
        }
    }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++) {for(int w:adj(v)) {
                R.addEdge(w, v);
            }
        }return R;
    }
}

 

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];
    }
}

多點可達性問題的一個重要時機應用是在典型的記憶體管理系統中，包括許多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();v++) {if(!marked[v]) dfs(G,v);
        }
    }/**
 * 该算法的关键步骤在于onStack数组的运用.
 * onStack数组标记的是当前遍历的点.如果对于一个点指向的所有点中的某个点
 * onstack[v]=true.代表该点正在被遍历也就是说
 * 该点存在一条路径,指向这个点.而这个点现在又可以指向该点,
 * 即存在环的结构~
 * @param G
 * @param v */ private void dfs(Digraph G, int v) {
        onStack[v]=true;
        marked[v]=true;for(int w:G.adj(v)) {if(this.hasCycle()) return;else if(!marked[w]) {
                edgeTo[w]=v;
                dfs(G,w);
            }else if(onStack[w]) {
                cycle=new Stack<Integer>();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;
    }
}

 

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();v++) {if(!marked[v]) dfs(G,v);
        }
    }private void dfs(Digraph G, int v) {        pre.enqueue(v);marked[v]=true;for(int w:G.adj(v)) {if(!marked[w]) {
                dfs(G,w);
            }
        }        post.enqueue(v);    reversePost.push(v);}public Iterable<Integer> pre() {return pre;
    }public Iterable<Integer> post() {return post;
    }public Iterable<Integer> reversePost() {return reversePost;
    }
}

###

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

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

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

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

 

前序就时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;
    }
}

 

5.有向图的强连通性

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

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

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

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

　　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中文網其他相關文章！