Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "directed graph case analysis of C# chart algorithm". The editor shows you the operation process through the actual case, the operation method is simple, fast and practical. I hope this article "directed graph case analysis of C# chart algorithm" can help you solve the problem.

In a directed graph, edges are unidirectional: the two vertices connected by each edge are an ordered pair, and their adjacency is unidirectional. Many applications are natural digraphs, as shown in the following figure. It's easy and natural to add this one-way restriction to implementation, and it doesn't seem to do any harm. But in fact, this combinatorial structure has a profound impact on the algorithm, which makes the processing of directed graph and undirected graph very different.

1. Terminology

Although our definition of a directed graph is almost the same as that of an undirected graph (and so are some of the algorithms and codes that will be used), the structural characteristics represented by the small literal differences in order to illustrate the direction of the edges are the focus.

Definition: a directed graph (or directed graph) consists of a set of vertices and a set of directional edges, each of which is connected to an ordered pair of vertices.

We say that a directed edge is indicated by the first vertex and points to the second vertex. In a directed graph, the degree of a vertex is the total number of edges indicated by the vertex; the degree of entry of a vertex is the total number of edges pointing to the vertex. The first vertex of a directed edge is called its head, and the second vertex is called its tail. V-> w denotes an edge in a digraph that points from v to w. There may be four kinds of relations between the two vertices of a digraph: no edges are connected; v-> w; w-> v; and w-> v.

In a directed graph, a directed path consists of a series of vertices, each of which has a directed edge pointing from it to the next vertex in the sequence. A directed ring is a directed path with at least one edge and the same starting point and end point. The length of the path or ring is the number of edges contained in it.

When there is a directed path from v to w, it is said that vertex w can be reached by vertex v. We need to understand the difference between reachability in a digraph and connectivity in an undirected graph.

two。 Data types of digraphs

Digraph API

Digraph representation

We use an adjacency list to represent a directed graph, where the edge v-> w indicates that the adjacency list corresponding to vertex v contains a w vertex. This representation is almost the same and clearer as an undirected graph, because each edge appears only once.

Directed graph inversion

A Reverse method has also been added to Digraph's API. It returns a copy of the directed graph, but reverses the direction of all edges in it. This method is sometimes useful when dealing with a directed graph because the use case can find all the edges that "point" to each vertex, while the Adj method gives all the vertices connected by the edges indicated by each vertex.

The symbolic name of the vertex

It is also easy to use symbolic names as vertices in a directed graph, see SymbolGraph.

Namespace Digraphs {public class Digraph {private int v; private int e; private List [] adj; public Digraph (int V) {this.v = V; this.e = 0; adj = new List [v]; for (var I = 0; I

< v; i++) { adj[i] = new List(); } } public int V() { return v; } public int E() { return e; } public List Adj(int v) { return adj[v]; } public void AddEdge(int v, int w) { adj[v].Add(w); e++; } public Digraph Reverse() { Digraph R = new Digraph(v); for (var i = 0; i < v; i++) foreach (var w in Adj(i)) R.AddEdge(w,i); return R; } }}3.有向图的可达性 在无向图中介绍的深度优先搜索DepthFirstSearch ，解决了单点连通性的问题，使得用例可以判定其他顶点和给定的起点是否连通。使用完全相同的代码，将其中的 Graph 替换成 Digraph 也可以解决有向图中的单点可达性问题（给定一幅有向图和一个起点 s ，是否存在一条从 s 到达给定顶点 v 的有向路径？）。 在添加了一个接受多个顶点的构造函数之后，这份 API 使得用例能够解决一个更加一般的问题 -- 多点可达性 （给定一幅有向图和顶点的集合，是否存在一条从集合中的任意顶点到达给定顶点 v 的有向路径？） 下面的DirectedDFS 算法使用了解决图处理的标准范例和标准的深度优先搜索来解决。对每个起点调用递归方法 Dfs ，以标记遇到的任意顶点。 namespace Digraphs{ public class DirectedDFS { private bool[] marked; public DirectedDFS(Digraph G, int s) { marked = new bool[G.V()]; Dfs(G,s); } public DirectedDFS(Digraph G, IEnumerable sources) { marked = new bool[G.V()]; foreach (var s in sources) { if (!marked[s]) Dfs(G,s); } } private void Dfs(Digraph G, int V) { marked[V] = true; foreach (var w in G.Adj(V)) { if (!marked[w]) Dfs(G,w); } } public bool Marked(int v) { return marked[v]; } }} 在有向图中，深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比。 有向图的寻路 在无向图中的寻找路径的算法，只需将 Graph 替换为 Digraph 就能够解决下面问题： 1.单点有向路径：给定一幅有向图和一个起点 s ，从 s 到给定目的顶点是否存在一条有向路径？如果有，找出这条路径。 2.单点最短有向路径：给定一幅有向图和一个起点 s ，从 s 到给定目的顶点 v 是否存在一条有向路径？如果有，找出其中最短的那条（所含边数最少）。 4.环和有向无环图 在和有向图相关的实际应用中，有向环特别的重要。没有计算机的帮助，在一幅普通的有向图中找出有向环可能会很困难。从原则上来说，一幅有向图可能含有大量的环；在实际应用中，我们一般只重点关注其中一小部分，或者只想知道它们是否存在。 调度问题 一种应用广泛的模型是给定一组任务并安排它们的执行顺序，限制条件是这些任务的执行方法和开始时间。限制条件还可能包括任务的耗时以及消耗的资源。最重要的一种限制条件叫做优先级限制，它指明了哪些任务必须在哪些任务之前完成。不同类型的限制条件会产生不同类型不同难度的调度问题。 下面以一个正在安排课程的大学生为例，有些课程是其他课程的先导课程： 如果假设该学生一次只能修一门课程，就会遇到优先级下的调度问题：给定一组需要完成的任务，以及一组关于任务完成的先后次序的优先级限制。在满足限制条件的前提下应该如何安排并完成所有任务？ 对于任意一个这样的问题，我们先画出一幅有向图，其中顶点对应任务，有向边对应优先级顺序。为了简化问题，我们以整数为顶点： 在有向图中，优先级限制下的调度问题等价于一个基本问题--拓扑排序：给定一幅图，将所有顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素（或者说明无法做到这一点）。 如图，所有的边都是向下的，所以清晰地表示了这幅有向图模型所代表的有优先级限制的调度问题的一个解决方法：按照这个顺序，该同学可以满足先导课程限制的条件下修完所有课程。 有向图中的环 如果任务 x 必须在任务 y 之前完成，而任务 y 必须在任务 z 之前完成，但任务 z 又必须在任务 x 之前完成，那肯定是有人搞错了，因为这三个限制条件是不可能被同时满足的。一般来说，如果一个优先级限制的问题中存在有向环，那么这个问题肯定是无解的。要检查这种错误，需要解决 有向环检测：给定的有向图中包含有向环吗？如果有，按照路径的方向从某个顶点并返回自己来找到环上的所有顶点。 一幅有向图中含有环的数量可能是图的大小的指数级别，因此我们只需找到一个环即可，而不是所有环。在任务调度和其他许多实际问题中不允许出现有向环，因此有向无环图就变得很特殊。 基于深度优先搜索可以解决有向环检测的问题，因为由系统维护的递归调用的栈表示的正是"当前"正在遍历的有向路径。一旦我们找到了一条有向边 v ->

W and w already exists in the stack, we find a ring, because the stack represents a directed path from w to v, and v-> w just completes the ring. If such an edge is not found, it means that the digraph is acyclic. Based on this idea, DirectedCycle implements:

Namespace Digraphs {public class DirectedCycle {private bool [] marked; private int [] edgeTo; private Stack cycle;// all vertices in a directed ring (if present) all vertices on the stack called recursively by private bool [] onStack;//) {onStack = new bool [G.V ()]; edgeTo = new int [G.V ()] Marked = new bool [G.V ()]; for (int v = 0; v)

< G.V(); v++) { if (!marked[v]) Dfs(G,v); } } private void Dfs(Digraph G, int v) { onStack[v] = true; marked[v] = true; foreach (var w in G.Adj(v)) { if (hasCycle()) return; else if (!marked[w]) { edgeTo[w] = v; Dfs(G, w); } else if (onStack[w]) { cycle = new Stack(); for (int x = v; x != w; x = edgeTo[x]) cycle.Push(x); cycle.Push(w); cycle.Push(v); } } onStack[v] = false; } private bool hasCycle() { return cycle != null; } public IEnumerable Cycle() { return cycle; } }} 该类为标准的的递归 Dfs 方法添加了一个布尔类型的数组 onStack 来保存递归调用期间栈上的所有顶点。当它找到一条边 v ->

When w is in the stack, it finds a directed ring. All vertices on the ring can be obtained through links in edgeTo.

When you execute Dfs, you are looking for a directed path from the starting point to v. To save this path, DirectedCycle maintains an array onStack indexed by vertices to mark all vertices on the stack that are called recursively (set onStack [v] to true when calling Dfs and false at the end of the call). DirectedCycle also uses an edgeTo array that returns all the vertices in the directed ring when it is found.

Depth priority and topological ordering of vertices

The scheduling problem under priority constraints is equivalent to calculating the topological ordering of all vertices in a directed acyclic graph:

The basic idea of the following algorithm is that depth-first search will only visit each vertex once. If you save the parameter vertices of Dfs in a data structure, traversing the data structure can actually access all the vertices in the graph, depending on the nature of the data structure and whether it is saved before or after the recursive call. In a typical application, the vertices are arranged in three order:

Preorder: add vertices to the queue before recursive calls

Post-order: add vertices to the queue after a recursive call

Reverse order: push vertices into the stack after a recursive call.

This class allows use cases to traverse depth-first search vertices in a variety of order. This is very useful in advanced digraph processing algorithms, because the recursion of the search allows us to prove many properties of this calculation.

Namespace Digraphs {public class DepthFirstOrder {private bool [] marked; private Queue pre;// pre-order of all vertices private Queue post;// post-order arrangement of all private Stack reversePost;// vertices reverse post-order public DepthFirstOrder (Digraph G) {marked = new bool [G.V ()]; pre = new Queue () Post = new Queue (); reversePost = new Stack (); for (var v = 0; v < G.V (); vault +) {if (! marked [v]) Dfs (Gjournal v) }} private void Dfs (Digraph G, int v) {pre.Enqueue (v); marked [v] = true; foreach (var w in G.Adj (v)) {if (! marked [w]) Dfs (Gmemw) } post.Enqueue (v); reversePost.Push (v);} public IEnumerable Pre () {return pre;} public IEnumerable Post () {return post;} public IEnumerable ReversePost () {return reversePost;}

The topological sort of a directed acyclic graph is the inverse post-order of all vertices.

Topological sort namespace Digraphs {public class Topological {private IEnumerable order; public Topological (Digraph G) {DirectedCycle cycleFinder = new DirectedCycle (G); if (cycleFinder.HasCycle ()) {DepthFirstOrder dfs = new DepthFirstOrder (G); order = dfs.ReversePost () }} public IEnumerable Order () {return order;} public bool IsDAG () {return order! = null;}

This section uses DirectedCycle to detect whether there are cycles and uses DepthFirstOrder to return the reverse order of the digraph.

The time required for topological sorting of directed acyclic graphs using depth-first search is proportional to the value E. The first depth-first search ensures that there is no directed loop, and the second depth-first search produces the reverse post-order arrangement of vertices.

In practical applications, topological sorting and the detection of directed rings always appear together, because the detection of directed rings is the premise of sorting. For example, in a task scheduling application, no matter how it is scheduled, the ring contained in the digraph behind it means that there is a serious error that must be corrected. Therefore, solving task scheduling applications usually requires the following three steps:

1. Specify tasks and priority conditions

two。 Continuously detect and remove all rings in the directed graph to ensure that there is a feasible scheme

3. Topological sorting is used to solve the scheduling problem.

Similarly, after any change in the scheduling scheme, you need to check again for the existence of loops, and then calculate the new scheduling.

5. Strong connectedness in digraphs

If two vertices v and w are reachable to each other, they are called strongly connected. That is to say, there is a directed path from v to w, and there is also a directed path from w to v. If any two vertices of a digraph are strongly connected, then the digraph is also said to be strongly connected.

The following is an example of a strongly connected graph, where you can see that rings play an important role in the understanding of strong connectivity.

Strongly connected component

Like connectivity in an undirected graph, strong connectivity in a digraph is an equivalent relation between vertices:

Reflexivity: any vertex v is strongly connected to itself.

Symmetry: if v and w are strongly connected, then w and v are also.

Transitivity: if v and w are strongly connected and w and x are also strongly connected, then v and x are also strongly connected.

As an equivalence relation, strong connectivity divides all vertices into some equivalence classes, each of which is composed of the largest subset of vertices that are strongly connected to each other. We call these subsets strongly connected components. As shown in the following graph, a directed graph with V vertices contains 1 ~ V strongly connected components-a strongly connected graph contains only one strongly connected component, while a directed acyclic graph contains V strongly connected components. It should be noted that the definition of strongly connected components is based on vertices, not edges. Some edges connect two vertices in the same strongly connected component, while some edges connect two vertices that are not in the same strongly connected component.

Strongly connected component API

It is not difficult to design a square algorithm to calculate the strongly connected components, but for large graphs in practical applications, the time and space requirements at the square level are unacceptable.

Kosaraju algorithm

How to efficiently calculate the strongly connected components in a directed graph? We only need to modify the algorithm of the connected components of the undirected graph, the CC,KosarajuCC algorithm is as follows, it will complete the following tasks:

1. In a given digraph G, use DepthFirstOrder to calculate the reverse permutation of its reverse graph GR.

two。 Do a standard depth-first search in G, but access all unmarked vertices in the order just calculated rather than the standard order

3. In the constructor, all vertices accessed in the same recursive Dfs () call are in the same strongly connected component, and they are identified in the same way as CC.

Namespace Digraphs {public class KosarajuCC {private bool [] marked;// identifiers of vertex private int [] id;// strongly connected components private int count;// number of strongly connected components public KosarajuCC (Digraph G) {marked = new bool [G.V ()]; id = new int [G.V ()] DepthFirstOrder order = new DepthFirstOrder (G.Reverse ()); foreach (var s in order.ReversePost ()) {if (! marked [s]) {Dfs (Ghemes); count++ } private void Dfs (Digraph G, int v) {marked [v] = true; id [v] = count; foreach (var w in G.Adj (v)) {if (! marked [w]) Dfs (Generw) } public bool StronglyConnected (int v, int w) {return id [v] = = id [w];} public int Id (int v) {return id [v];} public int Count () {return count;}

The preprocessing time and space of the Kosaraju algorithm is proportional to the Vitere and supports the query with strong connectivity of the directed graph with constant time.

Talk about accessibility again

If two vertices V and W are connected in an undirected graph, then there is both a path from v to w and a path from w to v. If two vertices v and w are strongly connected in a digraph, then there is both a path from v to w and another path from w to v. But for a pair of non-strongly connected vertices, there may be a path from v to w, there may be a path from w to v, maybe neither exists, but it is impossible to have both.

The reachability of vertex pairs: for undirected graphs, it is equivalent to the problem of connectivity; for directed graphs, it is very different from strong connectivity. The CC implementation requires linear preprocessing time to support constant-time operations. Can this performance be achieved in the corresponding implementation of the directed graph?

The transitive closure of a digraph G is another digraph consisting of the same set of vertices. There is an edge from v to w in the transitive closure if and only if w is reachable from v in G.

By convention, each vertex is reachable to itself, so the transitive closure contains V self-loops. There are only 22 directed edges in the image above, but its transitive closure contains 102 of the possible 169 directed edges. Generally speaking, the transitive closure of a directed graph contains much more edges than the original graph. For example, the transitive closure of a directed ring with V vertices and V edges is a directed complete graph with square edges of V. Because transitive closures are generally dense, we usually represent them as a Boolean matrix, where the value of the w column in the v row is true if and only if w is reachable from v. Instead of calculating the transitive closure of a directed graph, use depth-first search to implement the following API:

The following algorithm is implemented using DirectedDFS:

Namespace Digraphs {public class TransitiveClosure {private DirectedDFS [] all; public TransitiveClosure (Digraph G) {all = new DirectedDFS [G.V ()]; for (var v = 0; v < G.V (); vault +) all [v] = new DirectedDFS (Gpenv) } public bool Reachable (int v, int w) {return all [v] .marked (w);}

This algorithm is an ideal solution for both sparse and dense graphs, but it is not suitable for large digraphs, because the space required by the constructor is proportional to the square of V and the time required is proportional to V (V + E).

Summary

This is the end of the content of "digraph example Analysis of C# Chart algorithm". Thank you for your reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.