Directed rings, topological sorting and Kosaraju algorithm
First of all, take a look at today’s content outline, the content is very much, mainly on the algorithm ideas and sources, illustrated, I hope to help you ~
1. The concept and representation of directed graph
concept
In contrast to the undirected graph in the previous article, directed graphs have directional edges, and the two vertices connected by each edge are an ordered pair, and their adjacency is unidirectional.
A directed graph (or directed graph) consists of a set of vertices and a set of directed edges, each of which is connected to a pair of ordered vertices.
In fact, we don’t have much to say about the definition of a digraph, because you might think it’s natural, but we should always remember that there is direction!
Data representation
We still use the adjacency list to store the directed graph, where v–>w is denoted as the adjacency list of vertices v contains one vertex W. Notice that each edge only appears once because of direction!
Let’s take a look at how the data structure of a Directed Graph is implemented. Here’s a Directed Graph of the Digraph class
package Graph.Digraph; import java.util.LinkedList; public class Digraph{ private final int V; Private int E; Private LinkedList<Integer> adj. []; Public Digraph(int V){public Digraph(int V){this.v =V; this.E=0; adj=new LinkedList[V];for(int v=0; v<V; ++v){ adj[v]=new LinkedList<>(); } } public intV() {returnV; }// Get vertices public intE() {returnE; Public void addEdge(int v,int w){addEdge(int v,int w){addEdge(int v,int w){addEdge(int v,int w); // add w to v's list E++; } public Iterable<Integer> adj(int v){returnadj[v]; } // Public Digraph for Digraphreverse(){
Digraph R=new Digraph(V);
for(int v=0; v<V; v++){for(int w:adj(V)) R.addEdge(w, v); // Change the order of addition}returnR; }}Copy the codeIf you’re already familiar with the data representation of undirected graphs, you’ll notice that directed graphs are just renamed, with only two exceptions: the addEdge(v,w) method and the reverse() method. When we add an edge because we have a direction, we only need to add it once in our adjacency list; The reverse() method returns the reverse of a graph (that is, every direction is reversed), which will be useful in future applications, but for now we just need to get an impression.
2. Accessibility of digraphs
In the undirected graph (last article), we used depth-first search to find a path, and breadth-first search to find the shortest path between two points. If you think about it, do they apply to digraphs? Yes, the same code does the job, and we don’t need to make any changes (except for Graph to Digraph).
Because these contents have been introduced in detail in the last article, so I will not expand, if you are interested, you can refer to the last article, there are detailed illustrations.
3. Ring and directed acyclic graphs
We may face such a problem in real life: scheduling problem under priority constraints. In human language, you need to do some things, such as A,B,C, but there is A certain order to do these three things, before doing B must complete A, before doing C must complete B………… Your task is to come up with a solution (how to order things) so that constraints don’t conflict.
The first and second scenarios are easier, but the third scenario? Is something wrong!!
For the scheduling problem above, we can abstract it through a directed graph, with vertices representing tasks and the direction of arrows indicating priorities. It is not difficult to find that as long as there is a directed loop in a directed graph, the task scheduling problem is impossible! So, we are going to solve two problems:
- How to detect directed rings (just check for existence, not how many)
- How to Sort a directed graph without directed rings to find a solution (Task Scheduling Problem)
1. Look for directed rings
Our solution is to use depth-first search. Because the recursive call stack maintained by the system represents the directed path that the “current” is traversing. Once we find a directed edge 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 completes the loop. Also, if no such edge is found, it means that the directed edge is acyclic.
The data structure we used:
- The basic
dfsalgorithm - A new
onStack[]Arrays are used to explicitly record vertices on the stack (that is, whether a vertex is on the stack)
Let’s take a specific process as an example
I think the specific code has not difficult to you, let’s have a look
package Graph.Digraph; import java.util.Stack; public class DirectedCycle { private boolean [] marked; private int [] edgeTo; private Stack<Integer> cycle; // All vertices in a directed ring (if any) private Boolean [] onStack; Public DirectedCycle(Digraph G){onStack=new Boolean [G.V()]; edgeTo=new int[G.V()]; 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){ onStack[v]=true; // When entering DFS, vertex v is 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]){// Key cycle=new Stack<Integer>();for(int x=v; x! =w; x=edgeTo[x]) cycle.push(x); cycle.push(w); cycle.push(v); }} // When exiting DFS, push vertex V off stack onStack[v]=false;
}
public boolean hasCycle() {returncycle! =null; } public Iterable<Integer>cycle() {returncycle; }}Copy the codeThis class adds a Boolean array onStack[] to the standard recursive DFS () method to hold all vertices on the stack during a recursive call. When it finds an edge v → w and w is in the stack, it finds a directed ring. All vertices on the ring can be obtained by links in edgeTo[].
When DFS (G,v) is performed, it looks for a directed path from the starting point to v. To hold this path, DirectedCycle maintains an array of vertices indexed onStack[] to mark all vertices on the stack of recursive calls (onStack[v] is set to True when DFS (G,v) is called and false when the call ends). DirectedCycle also uses an edgeTo[] array that returns all vertices in a DirectedCycle when it finds one,
2. Topology sort
How to solve the scheduling problem with priority limits? This is actually topological sorting
Definition of topological sort: Given a directed graph, sort all vertices such that all directed edges point from the first element to the next (or state that this cannot be done)
Here is a typical example (scheduling problem)
It also has some other typical applications, such as:
Now, the preparation is almost complete, so please pay attention, the idea here may not be easy to understand. Follow my lead.
Now suppose we have a directed acyclic graph, to make sure we can sort topologically; Through topological sorting, we finally want to get a sequence of vertices, the first element points to the next element, that is, for any edge v — >w, we should get a result that vertex V precedes vertex W;
We use DFS to solve this problem. When calling DFS (v), one of three things must happen:
dfs(w)Has already been called and has already returnedwAlready marked)dfs(w)Has already been called and has not yet returned (which is impossible if you think about it)dfs(w)Not yet called (wNot marked yet), the situation is not complicated and will be calleddfs(w)And then returndfs(w)And then calldfs(v)
In short, we can draw an important conclusion: DFS (w) always completes before DFS (v). In other words, the vertices that complete DFS first come later
Make sure you fully understand the idea above, it’s relatively easy to follow. We create a stack, and whenever a vertex DFS completes, we push that vertex onto the stack. Finally, out of the stack is the order we want
In fact, topological sorting has basically been solved by us at this point, but let’s expand it and give you some common sorting methods, and what we just talked about is actually called inverse post-sorting. They are all based on DFS.
- Preordering: Queues vertices before recursive calls
- Post-ordering: Queues vertices after a recursive call
- Reverse post-ordering: Pushing vertices onto the stack after a recursive call
We’re implementing all three of these sorts together here, and they’re pretty simple recursively
package Graph.Digraph; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class DepthFirstOrder { private boolean [] marked; private Queue<Integer> pre; Private Queue<Integer> POST; Private Stack<Integer> reversePost; Public DepthFirstOrder(Digraph G){pre=new LinkedList<>(); post=new LinkedList<>(); 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.offer(v); marked[v]=true;
for(int w:G.adj(v))
if(! marked[w]) dfs(G, w); post.offer(v); reversePost.push(v); } public Iterable<Integer>pre()
{ return pre; }
public Iterable<Integer> post()
{ return post; }
public Iterable<Integer> reversePost()
{ returnreversePost; }}Copy the codeCongratulations, at this point we are fully capable of implementing Topological sorting. The following Topological classes do this. The order() method returns NULL if the given digraph contains a ring, otherwise it returns an iterator that gives topologically ordered vertices (of course, you can simply print the ordered vertices). The specific code is as follows:
package Graph.Digraph; public class Topological { private Iterable<Integer> order; Public Topological(Digraph G){// Determine whether a given graph G has a cycle cycleFinder =new DirectedCycle(G);if(! cyclefinder.hasCycle()){ DepthFirstOrder dfs=new DepthFirstOrder(G); order = dfs.reversePost(); } } public Iterable<Integer>order() {returnorder; } public Boolean if graph G is a directed acyclic graphisDAG() {return order!=null;
}
}
Copy the codeAt this point, the detection of directed rings and topological sorting are finished, and then we need to consider the problem of strong connectivity of directed graphs
4. Strongly connected component
1. Definition of strong connectivity
Think back to our undirected graph, where we solved the connectivity problem of an undirected graph using depth-first search. This problem can be easily solved by deep searching to reach all connected vertices. But when the problem becomes a digraph, it’s not so simple! Here are two examples of undirected and directed graphs:
Definition. Two vertices V and W are said to be strongly connected if they are mutually reachable. That is, there is a directed path from v to w, and there is a directed path from w to v. A directed graph is also strongly connected if any two vertices in it are strongly connected.
Here are some other examples of strong connectivity:
2. Strongly connected component
In directed graphs, strong connectivity is really an equivalence relation between vertices because it has the following properties
- Reflexivity: Any vertex V is strongly connected to itself
- Symmetry: If V and W are strongly connected, then w and V are also strongly connected
- Transitivity: if V and W are strongly connected and w and x are also strongly connected, then v and x are also strongly connected
Because of equivalence, like an undirected graph, we can divide a graph into several strongly connected components, and all vertices in each strongly connected component are strongly connected. In this case, given any two vertices to judge the strongly connected relation between them, we can directly determine whether they are in the same strongly connected component!
Next, we need to design an algorithm to achieve our goal ———— to divide a graph into several strongly connected components. Let’s start by summarizing our goals:
3. Kosaraju algorithm
Kosaraju algorithm is a classic algorithm to solve the problem of strong connectivity. Its implementation is very simple, but it is difficult to understand why. I hope you can cheer up and explain it clearly (I just hope that I will try my best.
Recall how we solved the connectivity problem in the part of the undirected graph. One DFS can traverse exactly one connected component, so we can count by DFS and get the ID of each vertex []; Therefore, when we solve the problem of strong connectivity of directed graphs, we also hope to use the property that DFS can exactly traverse a connected component. In directed graphs, however, it fails. Take a look at figure 1:
In Figure 1, there are two cases of DFS traversal:
In the first case, if the starting point of DFS is vertex A, then A DFS traversal will traverse the whole region 1 and 2, but region 1 is not strongly connected with region 2, which is the difficulty that the directed graph brings to us!
Second case: if the DFS starts at vertex D, then the first DFS traverses region 2 and the second DFS traverses region 1, isn’t that what we want?
So, the second situation gives us something to work on! That is, if we artificially change all the possible scenarios into the second scenario, things will be solved!
With directions, then, let’s look at a real digraph, as shown in Figure 2. This is a digraph whose strongly connected components are marked in gray; What happens when we treat each strongly connected component as a vertex? Our original directed graph becomes a directed acyclic graph!
Ps: Why can’t there be rings? If there is A ring between vertex A and vertex B, then A and B will form A larger strongly connected component! They’re supposed to belong to the same vertex!
After obtaining a directed acyclic graph (DAG), things are not so complicated. Now, let’s recall our purpose ———— in Figure 1, we want region two to do DFS first, that is, the region pointed to by the arrow to do DFS first. After abstracting the regions into points, the problem comes down to finding an order in a directed acyclic graph where the rule is that the vertices the arrows point to come first!
Now, let’s think about it a little bit. Our task is to find a sequence for DFS. Is this sequence very similar to the sort we talked about earlier? I think you can easily think of, is topological sort! But it’s the opposite of topological sort.
We interpret the arrow as A priority, and for vertex A to point to vertex B, A has A higher priority than B. So for topological sorting, the one with the highest priority is the first; For our task, the lower priority is first (we want DFS to not run from the lower priority to the higher priority)
For Figure 2: The result we want is shown in Figure 3:
If we do DFS from vertex 1 and go to the right, nothing we don’t want will ever happen! Because the arrows go one way!
I think you get the idea here. We have one final trivia problem ———— how to get the reverse order of topological sort?
In fact, the solution is very simple: for a directed graph G, we first reverse (reverse method), reverse the order of all the edges of the graph G, and then obtain the reverse order of the inverted graph (we can not call it topological sort, because the real situation is cyclic). Finally, we can DFS the original graph G by using the order of vertices obtained just now. At this time, its principle is exactly the same as that of undirected graph in the previous article!
Finally, the realization steps of Kosaraju algorithm are summarized as follows:
- 1. In a given digraph G, use DepthFirstOrder to calculate the inverse backorder of its reverse graph GR.
- 2. Perform a standard depth-first search in G, but access all unlabeled vertices in the order just computed instead of the standard order.
The actual implementation code only adds two lines of code to the undirected graph implementation CC class (changing the order of the DFS)
package Graph.Digraph; 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()); / / the keyfor(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;}
}
Copy the codeFinally, a detailed operation process is attached:
With Kosaraju, it’s easy to tell
- Given the connectivity of two vertices (above code
stronglyConnected) - How many strongly connected components are there in the graph (code above
count)
Afterword.
Well, that’s it for digraphs, and I hope you’ve been able to understand all three algorithms thoroughly through this article! Next article Xiao Chao will be there for you!
Finally, I give you a mind map of the graph algorithm
Xmind format can be obtained, I just want to say: really a lot of content! 😥
Code word drawing is not easy, if you feel that this article is helpful to you, pay attention to the author is the biggest support! Easy to point to see more grateful!
Welcome to follow my official account: Xiao Chao said, I will continue to create algorithms and data structures and basic computer knowledge articles. Can also add my wechat chao_hey (note: professional-city), we communicate together, progress together!
Reference: Algorithms (4th Edition)