What is topological sort
In fact, at the beginning of learning algorithm, I heard the word topological sorting is also meng forced, later learn to learn to slowly know what is the same thing. Here’s an explanation of the word topology found online:
The so-called “topology” is the method of abstracting the entity into “points” independent of its size and shape, and abstracting the lines connecting the entity into “lines”, and then representing the relations between these points and lines in the form of a graph. Its purpose is to study the connected relations between these points and lines. A graph that shows the relationship between points and lines is called a topological graph. Topological structure and geometric structure belong to two different mathematical concepts. In geometric structure, what we want to investigate is the position relationship between points and lines, or geometric structure emphasizes the shape and size formed by points and lines. For example, trapezoid, square, parallelogram and circle all belong to different geometric structures. However, from the perspective of topological structure, they have the same topological structure, namely ring structure, due to the same connection relation between points and lines. That is, different geometric structures may have the same topology.
Topology is the study of graphs in the computer world, and since it’s a graph, there are nodes and edges, nodes represent abstract things in real life, and edges represent relationships between those things.
If you think about it, a lot of things in real life can be abstracted into a graph in the computer world. For example, in a real map, nodes represent branches of the road, and edges represent the lines between branches. In the circle of people’s friends, we use nodes to represent people and edges to represent the relationship between people. Another example is historical events. We use nodes to represent events and edges to represent connections between events. No matter people or things, as long as the corresponding relation is found, they can always be abstracted into pictures.
Topological sorting addresses the dependency graph problem, which is A dependency graph where the relationship between nodes is dependent, so you’re going to do event A, if you’ve already done event B. Except for the chicken-and-egg problem, the dependencies of events are generally one-way, so we use directed acyclic graphs to represent dependencies. Topological sort is given according to the dependence on a to do things, or a sequence of events, for example, a friend to dinner, what are you going to cook, do you want to cook, first have to buy food, buy some food to go to the supermarket, to go to the supermarket and go out a ride, so this order is to go out a ride – – > > to the supermarket to buy food – > home cooking. Of course, you don’t need a computer to know the sequence, but some things are not easy to see directly, such as the common “how do I determine the dependencies of source code files on a very large project and give the corresponding compile order?” In other words, in learning, the thought process is often more important than the result or the answer.
Realize the principle of
A common algorithm for graph-related problems is search, depth and breadth, and topological sorting is no exception. Let’s first look at breadth-first search, which is a little easier to understand.
publicList<... > bfsTopologicalSort() {// Boundary condition detection
if(...). {return true; } Map<... , List<... >> graph =new HashMap<>();
/ / build.// This represents how many preconditions there are for each node.
int[] inDegree = new int[totalNodeNumber];
// Change the inDegree array according to the dependencies of the nodes in the figure
for(Entry.Map<... , List<... >> entry : graph.entrySet()) { ... } Queue<... > queue =new LinkedList<>();
for (int i = 0; i < numCourses; ++i) {
if (inDegree[i] == 0) { queue.offer(...) ; } } List<... > result =newArrayList<... > ();while(! queue.isEmpty()) {int cur = queue.poll();
// Record the current resultresult.add(...) ;// For the current node, unrestrict the node at the next level
for (... i : map.getOrDefault(cur, newArrayList<... >())) { inDegree[i]--;if (inDegree[i] == 0) { queue.offer(...) ; }}}return result;
}
Copy the codeFor the topological sorting problem, as we talked about earlier, it’s a graph-based algorithm, so the first thing we need to do is to abstract the problem as a graph, and here I use a HashMap to represent the graph, where Key represents a specific node, Value represents the lower nodes of this node, That is, the nodes in the List depend on the current node. The dependency is denoted in this way for the convenience of later implementation. Next, we will use an inDegree array to indicate how many dependent nodes each node has. We will select the nodes that do not depend on any node, and these nodes should be output first. Following the general breadth-first search thinking, we will open a queue and put these undependent nodes into it. Finally is breadth-first search steps, we guarantee that goes out from the queue of nodes is not dependent on or depend on the nodes have been lifted, we will be the output node, the node outputs, which rely on a layer of nodes will matter less, we change the inDegree corresponding value in the array, if after the change, The corresponding node has no dependency, indicating that the node can be output, it is added to the queue, waiting to be output. And the last thing we want to do is output the answer that we get, but the caveat here is that we have to think about the loop, like the chicken-and-egg problem, where A depends on B, and B depends on A, and we’re not going to get the answer.
Let’s look at depth-first search. The idea is slightly different from the breadth-first search. We no longer need the inDegree array, and we need to find a different way to determine if there is a ring in the graph.
public. dfsTopologicalSort() {// Boundary condition detection
if(...). { } Map<... , List<... >> graph =new HashMap<>();
/ / build.boolean[] visited = new boolean[numCourses];
boolean[] isLooped = new boolean[numCourses]; List<... > result =newArrayList<... > ();for (int i = 0; i < totalNodeNumber; ++i) {
if(! visited[i] && ! dfs(result, graph, visited, isLooped, i)) {return newArrayList<... > (); }}return result;
}
private. dfs(List<... > result, Map<... , List<... >>[] graph,boolean[] visited,
boolean[] isLoop,
... curNode) {
// Check if there is a ring
if (isLoop[curNode]) {
return false;
}
isLoop[curNode] = true;
// Traverses the front node of the current node, that is, the dependent node
for (int i : graph.get(curNode) {
if (visited[i]) {
continue;
}
if(! dfs(graph, visited, isLoop, i)) {return false;
}
}
isLoop[curNode] = false;
// record answer
result.add(curNode)
visited[curNode] = true;
return true;
}
Copy the codeOne thing to note is that when we’re building our graph, we need to reverse our breadth-first search, where Key is a node, Value is a node that it depends on, and that’s because of the way we’re doing it, we need to use recursion, recursion is a function stack, The function (node) is processed first and the result is printed. Understanding the above point, the following is to use recursion to solve the depth-first search problem, but one point is that we need to use two Boolean arrays, one (visited array) is to record the nodes we visited, to avoid repeated access, the other is to prevent the appearance of rings, how to avoid, Depth-first search is a search that goes all the way down a path, and we need to make sure that that path doesn’t go through a node twice, and I’m talking about a path here.
The two algorithms are two ways to achieve, but the purpose is the same, the idea is similar.
The problem sets
LeetCode 210. Course Schedule II
In some courses, each course has a prerequisite course, and you must complete the prerequisite course to take this course. This problem simply uses topological sorting, and I’ve listed both implementations here:
Code implementation: Depth-first search version:
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer> result = new ArrayList<>();
List<Integer>[] graph = new ArrayList[numCourses];
for (int i = 0; i < numCourses; ++i) {
graph[i] = new ArrayList<Integer>();
}
for (int i = 0; i < prerequisites.length; ++i) {
graph[prerequisites[i][0]].add(prerequisites[i][1]);
}
boolean[] visited = new boolean[numCourses];
boolean[] isLooped = new boolean[numCourses];
for (int i = 0; i < numCourses; ++i) {
if(! visited[i] && ! dfs(graph, visited, isLooped, i, result)) {return new int[0]; }}int[] output = new int[numCourses];
int index = 0;
for (int i : result) {
output[index++] = i;
}
return output;
}
private boolean dfs(List<Integer>[] graph,
boolean[] visited,
boolean[] isLooped,
int curCourse,
List<Integer> result) {
if (isLooped[curCourse]) {
return false;
}
isLooped[curCourse] = true;
for (int i : graph[curCourse]) {
if(! visited[i] && ! dfs(graph, visited, isLooped, i, result)) {return false;
}
}
isLooped[curCourse] = false;
visited[curCourse] = true;
result.add(curCourse);
return true;
}
Copy the code
Based on breadth-first search version:
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (prerequisites == null) {
return new int[0];
}
int[] inDegree = new int[numCourses];
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < numCourses; ++i) {
map.put(i, new ArrayList<Integer>());
}
for (int i = 0; i < prerequisites.length; ++i) {
map.get(prerequisites[i][1]).add(prerequisites[i][0]);
inDegree[prerequisites[i][0]] + +; } Queue<Integer> queue =new LinkedList<>();
for (int i = 0; i < numCourses; ++i) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
List<Integer> result = new ArrayList<>();
while(! queue.isEmpty()) {int cur = queue.poll();
result.add(cur);
for (int i : map.getOrDefault(cur, new ArrayList<Integer>())) {
inDegree[i]--;
if (inDegree[i] == 0) { queue.offer(i); }}}int[] output = new int[result.size()];
int index = 0;
for (int i : result) {
output[index++] = i;
}
return output.length == numCourses ? output : new int[0];
}
Copy the code
LeetCode 269. Alien Dictionary
Now that we have looked at the easy questions, let’s look at the difficult ones. This problem is the question is, now there is a new language, the input parameter is an array size order good words according to the characters, pay attention to the sorting here is based on this new language, not English, subject to output the size of a character we may order, here I used the “a” and “may” these two words, After topological sorting, there may be multiple solutions, for example, A depends on C, and B depends on C, so the output may be CAB or CBA, and we only need to output one of the solutions.
The realization of this problem can be divided into two parts, the construction of the graph, and topology sorting, the construction of the graph I use is the most direct way, let the word before and after the comparison, find out the first character of the two words are different, the character of the first word is smaller than the character of the next word. When we build the diagram, everything else is just the same.
Code implementation:
public String alienOrder(String[] words) {
if (words == null || words.length == 0) {
return "";
}
Map<Character, Set<Character>> graph = new HashMap<>();
for (int i = 0; i < words.length; ++i) {
for (char c : words[i].toCharArray()) {
if(! graph.containsKey(c)) { graph.put(c,new HashSet<Character>());
}
}
}
buildGraph(words, graph);
Set<Character> visited = new HashSet<>();
Set<Character> isLooped = new HashSet<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < words.length; ++i) {
for (char c : words[i].toCharArray()) {
if(! visited.contains(c) && ! dfs(graph, visited, isLooped, sb, c)) {return ""; }}}return sb.toString();
}
private boolean dfs(Map<Character, Set<Character>> graph,
Set<Character> visited,
Set<Character> isLooped,
StringBuilder sb,
char cur) {
if (isLooped.contains(cur)) {
return false;
}
isLooped.add(cur);
for (char c : graph.get(cur)) {
if(! visited.contains(c) && ! dfs(graph, visited, isLooped, sb, c)) {return false;
}
}
isLooped.remove(cur);
visited.add(cur);
sb.append(cur);
return true;
}
private void buildGraph(String[] words, Map
> graph)
,> {
int maxLen = 0;
for (int i = 0; i < words.length; ++i) {
maxLen = Math.max(words[i].length(), maxLen);
}
for (int i = 0; i < maxLen; ++i) {
for (int j = 1; j < words.length; ++j) {
if (words[j].length() <= i || words[j - 1].length() <= i) {
continue;
}
if (i == 0) {
if (words[j].charAt(0) != words[j - 1].charAt(0)) {
graph.get(words[j].charAt(0)).add(words[j - 1].charAt(0)); }}else {
if (words[j].substring(0, i).equals(words[j - 1].substring(0, i)) && words[j].charAt(i) ! = words[j -1].charAt(i)) {
graph.get(words[j].charAt(i)).add(words[j - 1].charAt(i));
}
}
}
}
}
Copy the code
conclusion
Topological sorting is actually a simple application of graph class problems, it is actually a fixed way to achieve, we only need to master the algorithm in these ways, I believe it is no longer a problem. Still want to talk about your understanding of problem do algorithm, we not to solve the problem in order to train our speed to solve the problem, the coding ability, more important is the inside of the learning algorithm is a way of thinking and methods, this advanced idea or thinking model can lead us toward the computer field to a broader and deeper place.