Arrange a timetable to learn topological sorting! interesting

Originality is not easy, please support three consecutive waves of handsome guys and beauties

Preface

Hello everyone, my name is bigsai.

Topological sorting is an algorithm that many people may have heard of but do not understand . Most people who don’t know will ask questions like this:

Is this some sorting algorithm? This seems to be a graph theory algorithm? Can the graphs be sorted?

Non-linear structure is really not easy to sort in the traditional sense, and topological sorting is to arrange the vertices of a directed graph into a linear sequence. And it’s not necessarily unique.

What is topological sort?

Topological sorting of a Directed Acyclic Graph (DAG) G is to arrange all vertices in G into a linear sequence, so that any pair of vertices u and v in the graph, if the edge <u,v>∈ E(G), then u appears before v in the linear sequence. Generally, such a linear sequence is called a sequence that satisfies the topological order (Topological Order), referred to as a topological sequence. Simply put, from a partial order on a set to get a total order on the set, this operation is called topological sorting .

What is the function of topological sorting?

There are actually many applications of topological sorting. Topological sorting can obtain an effective processing sequence when there are multiple processes in some projects. In some games, task achievements must meet a matching topological sorting to unlock the next level. Set of dependencies of some projects or environments...

Of course, the above example may not be specific enough. A little bit closer to us is the course study. For example, before you learn data structure, you basically need to learn C or C++, because you need to understand and use C++ code in data structure; learn to operate Before systems and computer networks, we must learn the course of data structure, because it involves a lot of data structures and algorithms; before learning Java Web development, we must learn the two courses of JavaSE and HTML; different colleges and universities have completely different course arrangements but they can all be very good. the connected together, it is because the curriculum to meet a topological sorting.

Topological sorting still cannot be understood? Let me give a more detailed example, the tutorial part of the learning Java series may have the following order:

CodenamesubjectNeed to master before school
A1JavaSE
A2HTML
A3JSPA1, A2
A4ServletA1
A5SSMA3, A4
A6SpringBootA5

For example, learning Java classes (parts) from Java basics, to JSP/Servlet, to SSM, to SpringBoot, SpringCloud, etc. is a gradual and prerequisite process. To learn in JSP, you must first master the basics of Java and HTML. The learning framework requires mastery of JSP/Servlet and JDBC. Then, this learning process constitutes a topological sequence. Of course, this sequence is not unique , you can choose the sequence of unrelated subjects at will (for example, Html and Java can start with whichever one) .

The above sequence can be simply expressed as:

image-20210607113325346

These five are all selectable learning programs, which can be a reference for the course arrangement. These five are all topological sequences of the directed acyclic graph (DAG) above, but the small selection strategies are different (learn Java first or first It doesn't matter if you learn HTML, but you have to meet the entire sequence requirements), it does not affect the sequence of rules!

For topological sorting, there are some more professional terms that need to be kept in mind:

DAG :
Directed acyclic graph AOV network: data is at the vertices, the vertices represent activities, and the edges represent the sequence of activities, which can be understood as a kind of object-oriented.
AOE network: The data is on the edges, the vertices represent events, the directed edges represent activities, and the weights on the edges represent the duration of the activity, which can be understood as process-oriented.

Many people don't know what the AOE network is for. Topological sorting is to solve the problem of whether a project can be carried out in order, but sometimes it is necessary to solve the shortest time required for the completion of the project. And AOE is often used in the critical path (here I will not introduce the content and algorithm in detail), the picture source is https://www.cnblogs.com/svod5306/p/14723338.html).

img

The topological sorting we are talking about today is to find a sequence in the AOV that does not destroy the graph structure. For a directed acyclic graph, you need to pay attention to the figure: if A is in front of B, there is no path before B in front of A ( cannot form a ring ). In the figure, two adjacent nodes in the topological sequence only need to satisfy the context and not necessarily need to be adjacent (the nodes only need to satisfy the relative context , so the topological order is not necessarily unique).

Analysis of Algorithms

The topological sort is briefly introduced above, and the method of topological sort is explained in detail below.

image-20210607152545338


The normal steps are (the method is not necessarily unique) :

1. Find a vertex output without a predecessor from the DAG graph . You can traverse the nodes with an in-degree of 0, or you can use priority queue maintenance.

2. Delete the edge starting from this point. To delete an edge, the in-degree of its pointing node is reduced by 1, so as to find the next vertex without a predecessor node.

3. Repeat the above until the last vertex is output. If there are still vertices that are not output, it means there is a ring!

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

step1: delete node 1 (or 2) and the edge it points to, and output the node

image-20210607153332186

step2: delete node 2 (or 3) and the edge it points to, and output the node

image-20210607153733105

step2 (two steps here): delete node 3 (or 4) and the edge pointed to, output the node, and then delete the edge pointed to by node 3 (or 6), output the node.

image-20210607155359497

step3: Repeat according to the above rules until all nodes are deleted.

image-20210607160806485

In this way, a topological sorting process is completed, and a topological sequence is obtained , but this sequence is not unique . From the algorithm execution process, there are many options. The specific result depends on the design of your algorithm, but as long as it satisfies the front and back of the DAG diagram Relative relationship.

In addition, observe that the sequence of 1 2 4 3 6 5 7 8 satisfies that the nodes that are related to us point to the front, and the nodes that are pointed to the back. If it doesn’t matter at all, it’s not necessarily before and after (e.g. 1, 2)

Code

For topological sorting, how to implement it in code?

Although the ideas and processes are described in detail above, they are also very easy to understand , but in fact the implementation of the code still needs to be considered. How to achieve a better balance between space and time and achieve better efficiency?

First of all, we must consider storage. For nodes, should we use adjacency matrix or adjacency table storage? Generally, topological sorting is relatively sparse if matrix storage is used, which wastes memory space. Here we still use adjacency table to store nodes.

In addition, if the nodes in the graph are ordered numbers such as 1, 2, 3, 4, 5, and 6, we can directly use the array, but if we encounter 1, 2, 88, 9999 similarly discontinuously numbered nodes with a large span, You can also consider using Map storage to map the location.

Then our specific code idea is:

① Create a new node class , including the node value and its pointing node collection (here, use the List collection directly)

②Initialize a person's node array, enter/enumerate the relationship between nodes, and the pointed-to node has a degree of +1 ! (For example, A—>C) Then the in-degree of C is +1;

③Scan all nodes (scan array here) . Add all points with an in-degree of 0 to a container stack (queue).

④ When the stack (queue) is not empty, throw any of the nodes (as long as the in-degree is zero, you can choose the order at will). Output node, and subtract 1 from the in-degree of all nodes pointed to by node. If the in-degree of a certain point is reduced to 0, then it is added to the stack (queue) .

⑤ Repeat the above operation until the stack (queue) is empty.

Here, the stack or queue is mainly used to store nodes with an entry degree of only 0 , and only the first scan of the table is required to put the entry degree of 0 into the stack (queue).

Because there is correlation between nodes, if a node wants to have zero in-degree, then its predecessor point must be 0 in its in-degree. Remove the associated arrow to reduce its own in-degree by 1, in a directed acyclic In the graph, there will always be 1 or more nodes with an in-degree of 0.

In terms of specific implementation, there are various ways. My one is just a simple demonstration, and the efficiency is not necessarily very high. You can refer to it.

The specific implementation code is:

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];//储存节点
		int a[]=new int[9];//储存入度
		List<Integer>list[]=new ArrayList[10];//临时空间,为了存储指向的集合
		for(int i=1;i<9;i++)
		{
			nodes[i]=new node(i);
			list[i]=new ArrayList<Integer>();
		}
		initmap(nodes,list,a);
		
		//主要流程
		//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();//抛出输出
			System.out.print(n1.value+" ");
			List<Integer>next=n1.next;
			for(int i=0;i<next.size();i++)
			{
				a[next.get(i)]--;//入度减一
				if(a[next.get(i)]==0)//如果入度为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]++;
		
	}
}

Output result

2 4 6 1 3 5 7 8
image-20210607163813249


Of course, as mentioned above, both stacks and queues can be used! If you use queues, you will get a topology sequence of 1 2 3 4 5 6 7 8

As for the structure of the graph, because there is no condition, the efficiency may not be high, and the algorithm may not be perfect. If there are optimization errors, please correct me!

Topological sorting to find ring

As mentioned earlier, topological sorting needs to be in a directed acyclic graph to get a topological sequence, but if a directed graph is given, how do you know whether it can form a topological sequence?

Of course, the topological sorting algorithm is changed. When we are doing topological sorting, all nodes with an in-degree of 0 will be deleted, but if there are loops, the number of deleted nodes is less than the number of all nodes. In the specific implementation, we only need When the stack or queue is thrown, a counter counts the number.

Of course, this question has the original question of Likou 207, you can see if your code can be ac, the description of the problem:

You must take numCourses as an elective course this semester, which is recorded as 0 to numCourses-1.
Some prerequisite courses are required before taking certain courses. The prerequisite courses are given in the array prerequisites, where prerequisites[i] = [ai, bi] means that if you want to learn the course ai, you must first study the course bi.
For example, the prerequisite course pair [0, 1] means: To study course 0, you need to complete course 1 first.
Would you please judge whether it is possible to complete all courses? If it can, return true; otherwise, return false.

The analysis has been given above, but it is more flexible when implementing the code. You don't necessarily have to create a node class, just clarify the idea.

Implementation code:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int indegree[]=new int[numCourses];
        List<Integer> next[]=new ArrayList[numCourses];
        
        for(int i=0;i<numCourses;i++){
            next[i]=new ArrayList();
        }
        for(int i=0;i<prerequisites.length;i++) {
            int preid=prerequisites[i][1];
            int courseid=prerequisites[i][0];
            indegree[courseid]++;//入度加一
            next[preid].add(courseid);//next指向
        }
        Queue<Integer>queue=new ArrayDeque<>();
        for(int i=0;i<numCourses;i++) {//加入入度为0的节点
            if(indegree[i]==0){
                queue.add(i);
            }
        }
        int nodeNum=0;//判断删除节点数量 入度为0删除 如果删除所有那么返回true
        while (!queue.isEmpty())
        {
            nodeNum++;
            int nodeId=queue.poll();
            for(int i=0;i<next[nodeId].size();i++)
            {
                int nodeIndex=next[nodeId].get(i);
                indegree[nodeIndex]--;
                if(indegree[nodeIndex]==0) {
                    queue.add(nodeIndex);
                }
            }
        }
        if(nodeNum==numCourses)
            return true;
        return false;
    }
}

Ok, here is the topological sorting content explanation, if it helps, please pay attention, like, and share a wave, thank you!

About the author: bigsai, focusing on Java, data structure and algorithm knowledge sharing, WeChat search [bigsai] follows this guy who shares dry goods, and welcomes those who have doubts or ideas about career planning, study, and postgraduate entrance examinations. Share a Google brother brushing notes: Get the link: https://pan.baidu.com/s/1JgKCexnF3EGRSGdLCoxVfw Password: oke5