@ the Author: Runsen

In fact, there are a lot of sorting, such as the common Hill sort, bucket sort, counting sort and cardinal sort, because of the transition to the data structure digraph, so you need to understand the concept of topological sorting and adjacency matrix.

A topological sort

Topological sort itself is not a sort, sort refers to an array of data, and there is no connection between the data.

Topological sorting is a concept derived from Topology, which studies properties of topological Spaces that remain constant under continuous changes (such as stretching or bending, but not tearing or gluing). In fact, I am also half understand and not very understand state.

Let’s look at an example of topological sorting in life, from wang’s algorithm column.

We all have a certain order in which we dress, and we can think of that order as a kind of dependency between clothes. For example, you have to wear socks before you can put on shoes, and underwear before you can put on long Johns.

Suppose we now have eight pieces of clothing to wear, and the pair dependencies between them are well understood. How can we arrange a sequence of clothing that satisfies all pair dependencies?

The principle of topological sorting is very simple, the following is a cow about topological sorting multiple choice questions, as if is 2017 Didi school enrollment writing questions, in fact, is to send points.

Which of the following sequences is not a topological sort of the figure above?

A. ebfgadch
B. adchebfg
C. aebdgfch
D. aedbfgch
Copy the code

The answer is B, because H can’t come in the middle, it’s the end of the topological order, it can only come before F at most. Topological ordering is defined as follows: Topological ordering of a Directed Acyclic Graph (DAG)G is to arrange all vertices in G into a linear sequence, such that any pair of vertices U and V in the Graph, if edge (u,v)∈E(G), u will appear before V in the linear sequence.

figure

A graph is a more complex data structure than a tree.

The elements in a tree are called nodes, and the elements in a graph are called vertices. A vertex in a graph can be joined to any other vertex. We call this established relationship an edge.

Zhengge compared the picture to wechat friend relationship, in fact, very image. For example, the vertices in the figure above all represent a wechat user.

The whole wechat friend relationship can be represented by a graph. Among them, how many friends each user has is called the degree of the vertex in the graph, which is the number of edges connected to the vertex.

As for directed graph, Brother Zhengge is compared to the social relationship of microblog. Microblog only allows one-way following, that is to say, user A follows user B, but user B can not follow user A. For me who don’t play micro-blog, I just know about the one-way attention of micro-blog now.

If user A follows user B, we draw an arrowhead edge from A to B to indicate the direction of the edge. If user A and user B are looking at each other, let’s draw an edge from A to B, and another edge from B to A. We call such graphs with directional edges a directed graph.

In directed graphs, degrees are divided into in-degree and out-degree. In the case of weibo, the number of followers corresponds to the number of followers and the number of followers corresponds to the number of followers.

In the weighted graph, each edge has a weight, which can be used to indicate the closeness between QQ friends.

In the diagram, there is a very important concept called the adjacency matrix.

The underlying level of the adjacency matrix depends on a two-dimensional array. For undirected graphs, if there are edges between vertex I and vertex j, we label A[I][j] and A[j][I] as 1. For A directed graph, if there is an arrow between vertex I and vertex J pointing from vertex I to the edge of vertex J, we label A[I][j] as 1. Similarly, if we have an arrow pointing from vertex J to the edge of vertex I, we label A[j][I] as 1. For a weighted graph, the corresponding weights are stored in the array.

Directed Acyclic Graph (DAG) is one of the hot topics of blockchain projects in recent years. Go blockchain, at first, is directed acyclic graph.

In fact, directed acyclic graph is easy to understand, “directed” refers to the direction, to be precise should be the same direction, “acyclic” refers to can not reach the closed loop, like the above example of the graph. Most of the time directed graphs, most of the time directed acyclic graphs.

Note: the above text and pictures are from Wang Zheng algorithm column

The curriculum

For topology sorting, what is more impressive in Leetcode is the Leetcode 207 curriculum

You must take numCourse courses this semester, marked 0 to NUMCourse-1.

Some prerequisite courses are required before you can take certain courses. For example, to take course 0, you need to complete course 1 first. We represent them with a match: [0,1]

Given the total number of courses and their prerequisites, determine whether it is possible to complete all the courses?

Example 1: Input: 2, [[1,0]] Output: true Explanation: There are 2 courses. Before you can study course 1, you need to complete course 0. So it's possible. Example 2: input: 2, [[1,0],[0,1]] output: false explanation :  There are 2 courses in total. You need to complete Course 0 before taking course 1; And you should also complete course 1 before taking course 0. It's impossible.Copy the code

After the packaging is removed, this question is actually a directed graph to detect whether there is a ring problem, which means that the completion of the course cannot be achieved.

To judge whether there is a ring in topological sorting, is actually the realization of a search algorithm, so we can easily think of depth first search and breadth first search.

Breadth-first search

First, let’s talk about the algorithmic process of BFS breadth-first search.

Breadth-first searches can find exits in a way that diverges in all directions, that is, not depth-first. So when we get to a point, we mark that point, and then if we get to that point later, we find that the maze has a path that will never get out of it, so we can think of it as finding a directed loop.

The first node in the topology order must not have any entry edge, that is, it does not have any prerequisite course requirements. If it’s in the queue, it means the class is ready to start. The unedged nodes are then continuously added to the queue until either the queue contains all of the nodes (a sort of topological sort is achieved) or the previously edged nodes (including rings in the diagram) reappear.

Algorithm flow:

  • According to the statistics of the entry degree of each node in the course arrangement chart, the entry degree table Indegrees and adjacency matrix are generated. By default, the entry degree table Indegrees and adjacency matrix are all zeros. The adjacency matrix is a two-dimensional array, which can also be called the course arrangement chart.
  • Prerequisites for traversing the incoming topology order, in this case, the incoming resident learns the current course and replaces the value with 1. He/she then learns the next course before adding the matrix.
  • Enqueue all nodes with an entry degree of 0 with a queue. If the queue is empty, there is absolutely a loop. NumCourses == 0.
  • When queue is not empty, remove the first queue node in turn and delete this node in the course arrangement diagram pre:
    • However, this node pre is not really deleted from the adjacency list, but the entry of the node corresponding to all the adjacency nodes cur -1, namely indegrees[cur] -= 1.
    • When the entry degree of the adjacent node CUR after -1 is 0, it indicates that all the precursor nodes of CUR have been “deleted”, and cur will join the team at this time.
  • Each time pre exits the queue, numCourses–;
    • If the entire course arrangement chart is a directed acyclic graph (that is, it can be arranged), then all nodes must be in and out of the queue, that is, topological ordering is completed. To put it another way, if there are rings in the course arrangement diagram, there must be nodes whose entry degree is never 0.
    • Therefore, the number of topological sorting teams is equal to the number of courses, and numCourses == 0 is returned to judge whether the courses can be arranged successfully.

The specific breadth-first search determines whether there is a ring in the topological sort. The specific code is shown below.

"' @ Author: Runsen @ WeChat: RunsenLiu @ WeChat public number: the king of the Python @ CSDN: https://blog.csdn.net/weixin_44510615 @ making: https://github.com/MaoliRUNsen @ Date: 2020/12/27 "'
class Solution(object) :
    def canFinish(self, numCourses, prerequisites) :
        Record how many other courses you have to take before you can take the course represented by index
        indegrees  = [0 for _ in range(numCourses)]
        Adjacency matrix: a collection of lessons that can be learned after learning the lessons represented by index
        adjacency = [[] for _ in range(numCourses)]

        for cur, pre in prerequisites:
            Indegrees [cur] courses are required before taking a course
            indegrees[cur] += 1
            # After the Pre course you can learn the lessons in the Adjacency [Pre] collection
            adjacency[pre].append(cur)

        queue = []

        for course in range(numCourses):
            if indegrees [course] == 0: You do not need to take other courses first
                queue.append(course)

        while queue:
            course = queue.pop(0)
            Finish a course
            numCourses -= 1 
            for next_course in adjacency[course]:
                # next_course reduces the number of pre-courses by one because the course is finished
                indegrees [next_course] -= 1 
                if indegrees [next_course] == 0: # indicates that you do not need to take other courses first
                    queue.append(next_course)
        return numCourses == 0
Copy the code

Depth-first traversal

For depth-first traversal DFS, I feel uncomfortable. We need a list of flags to determine the state of each node I (course) :

  • Not accessed by DFS: I == 0;
  • DFS that has been started by other nodes: I == -1;
  • DFS already started by the current node: I == 1.

Depth-first traversal idea: Execute DFS on numCourses nodes one by one to check whether there is a ring in the initial DFS of each node. If there is a ring, return False.

Termination conditions for DFS process:

  • If flag[I] == -1, it indicates that the node is accessed by the DFS enabled on other nodes. You do not need to search repeatedly and return True.
  • When flag[I] == 1, it indicates that node I is accessed for the second time in this round of DFS search, that is, there is a loop in the course arrangement chart, and False is directly returned.

Set flag[I] corresponding to node I currently accessed to 1, that is, it is marked that it has been accessed by this round of DFS. Recursively accesses all adjacent nodes j of the current node I, and returns False when a ring is found;

If all adjacent nodes of the current node have been traversed and no ring is found, the flag of the current node is set to -1 and True is returned.

Returns True if the entire graph DFS ends without a ring being found.

The operation steps of DFS are as follows (recursive) : 1, initialize each node and set its access flag as 0 2, call DFS access to the first known node, as long as P is not empty, that is, the side table is not empty. If the node has not been visited, recursively call DFS to access it, and mark it as 1 after the visit, otherwise P =p->next find the next adjacent node 3 and iterate. Do the same for each node until all are accessed.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - >bool:
        def dfs(i, adjacency, flags) :
            if flags[i] == -1: return True
            if flags[i] == 1: return False
            flags[i] = 1
            for j in adjacency[i]:
                if not dfs(j, adjacency, flags): return False
            flags[i] = -1
            return True

        adjacency = [[] for _ in range(numCourses)]
        flags = [0 for _ in range(numCourses)]
        for cur, pre in prerequisites:
            adjacency[pre].append(cur)
        for i in range(numCourses):
            if not dfs(i, adjacency, flags): return False
        return True
Copy the code

Reference link: leetcode-cn.com/problems/co…

GitHub, portal ~, GitHub, portal ~, GitHub, Portal ~