introduce

Topological sorting, an algorithm that many people have probably heard of but don’t understand. Perhaps many people only know it as a sort of graph theory, as for what is not clear. Or maybe a lot of people would think it’s a sort of sort. But essentially it’s a linear sequence of vertices on a digraph.

As for the definition, the encyclopedia says:

Topological ordering for an Directed Acyclic Graph (DAG)G is to arrange all vertices in G into a linear sequence such that u and V in any pair of vertices in the Graph appear before V if edge ∈E(G). In general, such linear sequences are called Topological Order sequences, or Topological sequences. Simply put, a partial order on a set yields a full order on the set. This operation is called topological sorting.

Why is there topological sort? What does topological sort do?

For example, follow the Java series of tutorials

For example, learning Java family classes (parts) from Java basics, to JSP /servlet, to SSM, to SpringBoot, SpringCloud, etc is a step-by-step and dependent process. In JSP learning to first master the Java foundation and HTML foundation. Learning frameworks is about JSP /servlet and JDBC. This learning process, then, constitutes a topological sequence. Of course, this sequence is not unique, and you can choose which order to start with for unrelated subjects (for example, HTML or Java).

Then the above sequence can be simply expressed as:

Five of them are optional learning programs, which can be used as a reference for course arrangement. Of course, five are topological sequences. Just choose a different strategy!

Some other notes:

DGA: directed acyclic graph AOV network: data in the vertex can be understood as object-oriented AOE network: data in the side, can be understood as process-oriented!

And in a more general way, we take the vertices of the graph, according to some rule, and what can these vertices represent or have any relation.

Rules:

• Each vertex in the graph appears onlyAt a time.
• If A is in front of B, there is no path where B is in front of A. (Cannot loop ！！！！)
• The order of vertices is to ensure that all next nodes pointing to them precede the pointed node! (for example, A — >B — >C then A must come before B and B must come before C). Therefore, as long as the core rule satisfies, so the topological sorting sequence is not necessarily unique!

Topological sorting algorithm analysis

The normal step is (method may not be unique)

• Find one from the DGA diagramThere is no precursorThe vertex output of. (Can be traversed or maintained using priority queues)
• Deletes the edge starting at this point. (Its pointing edge is removed in order to find the next vertex without a precursor)
• Repeat until the last vertex is printed. If there are any vertices that are not printed, then there is a ring!

For the simple sequence in the figure above, the steps can be simply described as:

• 1: deletes output 1 or 2
  

  

• 2: deletes 2 or 3 and the corresponding edge
  

  

• 3: deletes 3 or 4 and the corresponding edge
  

  

• 3: Repeat the preceding steps
  

  

This completes a topological sort, resulting in a topological sequence, but this sequence is not unique! As you can see from the process, there are a lot of options, and it depends on the design of your algorithm. But as long as satisfies is topological sort sequence.

And if you look at the sequence 1, 2, 4, 3, 6, 5, 7, 9 that satisfies what we call the relational nodes that point to the front and are pointed to the back. If it doesn’t matter at all it doesn’t have to be before or after (e.g. 1,2)

Topology sort code implementation

How do you implement topological sorting in code? For topological sorting, although the ideas and processes are described in detail above, they are also easy to understand. But actually the implementation of the code is still very need to consider, how to get a good balance in space and time and achieve better efficiency?

The first thing to consider is storage. For nodes, first of all, it has so many attributes as connecting points. It is better to use adjacency list when encountering sparse matrix. Because a node has fewer pointing nodes, adjacency matrix is a waste of resources.

In addition, if it is 1,2,3,4,5,6, we can consider using arrays, but if it is 1,2,88,9999, we can consider using map. So,

Our specific code idea is:

• Create a new Node class that contains the value of the node and its pointer.
• An array contains nodes (which are numbered more centrally by default). Initializing, add each node to point at the same time when the node is pointing to the entry degree +1! (A – >C) then the degree of C +1;
• Scan all nodes. I’m going to add one to all the zero degreesStack (queue).
• When stack (queue) is not empty,Throw any of the nodes(Stack is the tail, queue is the head, order does not matter, the above analysis as long as the simultaneous entry is zero can arbitrarily choose the order). Output node, andAll elements pointed to by node are decrement by one.If the entry of a point is reduced to 0, it is added to the stack (queue)..
• Repeat until the stack is empty.

Here, the nodes whose input degree is only 0 are mainly stored by stack or queue, and the nodes whose input degree is 0 are only put into the stack (queue) by initial scanning of the table.

• Here you might ask why.
• Since there is correlation between nodes, if a node has zero degree of entry, then its parent node (pointing to the node) must have zero degree of entry before it is zero. Remove the association arrow. From the parent’s point of view, its disconnection may or may not result in a zero read (there are other nodes pointing to the child).

As for specific demo:

packageGraph theory;import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class tuopu {
	static class node
	{
		int value;
		List<Integer> next;
		public node(int value) {
			this.value=value;
			next=new ArrayList<Integer>();
		}
		public void setnext(List<Integer>list) {
			this.next=list; }}public static void main(String[] args) {
		// TODO Auto-generated method stub
		node []nodes=new node[9];// Storage node
		int a[]=new int[9];// Store the input
		List<Integer>list[]=new ArrayList[10];// Temporary space to store the pointed collection
		for(int i=1; i<9; i++) { nodes[i]=new node(i);
			list[i]=new ArrayList<Integer>();
		}
		initmap(nodes,list,a);
		
		// Main process
		//Queue<node>q1=new ArrayDeque<node>();
		Stack<node>s1=new Stack<node>();
		for(int i=1; i<9; i++) {//System.out.print(nodes[i].next.size()+" 55 ");
			//System.out.println(a[i]);
			if(a[i]==0) {s1.add(nodes[i]);}
			
		}
		while(! s1.isEmpty()) { node n1=s1.pop();// Throws the output
		    
			System.out.print(n1.value+"");
			
			List<Integer>next=n1.next;
			for(int i=0; i<next.size(); i++) { a[next.get(i)]--;// The input degree is reduced by 1
				if(a[next.get(i)]==0)// If the degree is 0{ s1.add(nodes[next.get(i)]); }}}}private static void initmap(node[] nodes, List<Integer>[] list, int[] a) {
		list[1].add(3);
		nodes[1].setnext(list[1]);
		a[3] + +; list[2].add(4); list[2].add(6);
		nodes[2].setnext(list[2]);
		a[4] + +; a[6] + +; list[3].add(5);
		nodes[3].setnext(list[3]);
		a[5] + +; list[4].add(5); list[4].add(6);
		nodes[4].setnext(list[4]);
		a[5] + +; a[6] + +; list[5].add(7);
		nodes[5].setnext(list[5]);
		a[7] + +; list[6].add(8);
		nodes[6].setnext(list[6]);
		a[8] + +; list[7].add(8);
		nodes[7].setnext(list[7]);
		a[8] + +; }}Copy the code

The output

2, 4, 6, 1, 3, 5, 7, 8

1, 2, 3, 4, 5, 6, 7, 8

As for the structure of the graph, because there is no condition may not be high efficiency, the algorithm may not be perfect, if there is an optimization error, please correct!

In addition, I would like you to move your handsLike and follow (Bigsai)A wave! Thank you 🙏