有向グラフのタスク スケジューリング トポロジ グラフの概要

1. 有向グラフのデータ型

Bag を使用して有向グラフを表します。ここで、辺 v->w は、頂点 v に対応する隣接リンク リストとして表されます。これは、頂点 v とは異なります。無向グラフ 実は、ここでの各エッジは 1 回だけ表示されます。

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 が与えられると、 path from 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 配列も追加されます。

4.2 トポロジカルソート

トポロジカルソート: 有向グラフが与えられた場合、すべての有向エッジが前方の要素から後方の要素を向くようにすべての頂点をソートします。

有向グラフのトポロジカルソートを実装するには、標準の深さ優先探索順序を使用してタスクを完了できます。

1. 事前注文。 : 再帰呼び出しの前に頂点をキューに追加します

2. ポストオーダー: 再帰呼び出しの後に頂点をキューに追加します

3. 逆ポストオーダー: 再帰呼び出しの後に頂点をプッシュします Stack. 特定の操作については、以下のコードを参照してください:

/**
 * 有向图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;
    }
}

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

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

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

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

 

前序就时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 中国語 Web サイトの他の関連記事を参照してください。