Introduction to task scheduling topology graph of directed graph

1. Data type of directed graph

Use Bag to represent the directed graph, where edge v->w is represented as vertex v The corresponding adjacency linked list contains a w vertex. Unlike the undirected graph, each edge here only appears once. The data structure type of the directed graph is as follows:

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. Reachability in directed graph

Connectivity in undirected graphSimilarly, depth-first search can be used to solve the

single-point reachability problem in directed graphs: that is: given a directed graph and A starting point s, answer the question of whether there is a directed path from s to a given vertex v.

Multi-point reachability problem: Given a Given a directed graph and a set of vertices, answer whether there is a directed path from any vertex in the set to a given vertex 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];
    }
}

An important application of the multi-point reachability problem is in typical memory management systems, including many Java implementations. In a directed graph, a vertex represents an object, and an edge represents a reference from one object to another.

This model well represents the memory usage of running java programs. There are certain objects that can be directly accessed at any time during program execution, and all objects that cannot be accessed through these objects should be recycled to

free up memory. It periodically runs a directed graph reachability algorithm similar to DirectedDFS to mark all accessible objects.

3. Pathfinding for directed graphs

is similar to undirected graphs. Common problems in directed graphs:

#Single-point directed path. Given a directed graph and a starting point, answer "Is there a directed path from s to the given destination vertex v? If so, find this path"

Single point shortest directed path. Given a directed graph and a starting point, answer "Is there a directed path from s to the given destination vertex v? If so, find the shortest one (containing the least number of edges)"

4. Scheduling problem—topological sorting

4.1 Finding directed cycles

If a directed cycle exists in a problem with priority constraints, then the problem must be unsolvable. Therefore, directed ring detection is required.

The following code can be used to detect whether a given directed graph contains a directed cycle. If so, return all vertices on the cycle in the direction of the path.

When executing dfs, what is searched is the directed path from the starting point to v. The onStack array marks all the vertices on the stack of the recursive call, and the edgeTo array is also added. After finding the When moving to the ring, return all the vertices in the ring.

/**
 * 有向图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 Topological sorting

Topological sorting: Given a directed graph, sort all the vertices so that all directed edges point from the elements in the front to the elements in the back. If there is a directed cycle If so, then topological sorting cannot be completed.

To implement topological sorting of directed graphs, the task can be completed using the standard depth-first search order. There will be three arrangements of vertices here:

1. Pre-order: Add the vertices to the queue before the recursive call

2. Post-order: Add the vertices to the queue after the recursive call

3. Reverse sequence: push the vertices onto the stack after the recursive call.

See the code below for specific operations:

//有向图中基于深度优先搜索的拓补排序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;
    }
}

 

The above is the detailed content of Introduction to task scheduling topology graph of directed graph. For more information, please follow other related articles on the PHP Chinese website!