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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
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?
1 2 3 4 5 6 7 8 9 10 11 12 |
|
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
遍历的顺序取决于这个数据结构的性质以及是在递归调用之前还是之后进行保存。
前序:在递归调用之前将顶点加入队列。
后序:在递归调用之后将顶点加入队列。
逆后序:在递归调用之后将顶点压入栈。
前序就时dfs()的调用顺序;后序就是顶点遍历完成的顺序;逆后序就是顶点遍历完成顺序的逆。
拓补排序的实现依赖于上面的API,实际上拓补排序即为所有顶点的逆后序排列
拓补排序的代码如下:
1 2 3 4 5 6 7 8 |
|
5.有向图的强连通性
定义:如果两个顶点v和w是互相可达的,则称它们为强连通的.也就是说既存在一条从v到w的有向路径也存在一条从w到v的有向路径.
如果一幅有向图中的任意两个顶点都是强连通的,则称这副有向图也是强连通的.任意顶点和自己都是强连通的.
下面的代码采用如下步骤来计算强连通分量以及两个点是否是强连通的:
1.在给定的有向图中,使用DepthFirsetOrder来计算它的反向图GR的逆后序排列
2.按照第一步计算得到的顺序采用深度优先搜索来访问所有未被标记的点
3.在构造函数中,所有在同一个递归dfs()调用中被访问到的顶点都是在同一个强连通分量中.
下面的代码实现遵循了上面的思路:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
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!