Shulou(Shulou.com)05/31 Report--

Today, I would like to share with you the relevant knowledge points about how to achieve topological sorting in Java. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article.

Lay the groundwork

Directed graph: the algorithm we are going to talk about in this section involves directed graph, so I'll talk about some concepts of directed graph first, but I won't explain it later in the article. First of all, the nodes of the digraph are connected by a line with arrows. The node has the concept of exit degree and entry degree, the exit degree of the node pointed at the tail of the connection is plus 1, and the head of the connection, that is, the node entry degree pointed to by the arrow, is added by 1. Take a look at the following example. The entry degree of An is 0, the exit degree is 2, the entry degree of B is 1, the entry degree of exit degree is 1, the entry degree of exit degree is 1, the entry degree of D is 2, and the exit degree is 0.

Adjacency table: the adjacency table is an effective way to store the graph structure, as shown in the following figure, the left node array stores all nodes in the graph, and the right adjacency table stores the neighboring nodes of the nodes.

Brief introduction

In this article, we are going to talk about topological sorting, which is an algorithm for directed acyclic graphs, mainly to solve the relationship between the predecessor and the successor, that is, what we need to accomplish first when we finish the current task. in fact, this is used a lot in our process control. Looking at the diagram below, we need to complete item A before we can complete the BMague C project. BMagol C items are juxtaposed and have no order, but for D items need to be completed after the BMague C project is completed. The topological sorting can help us to find the reasonable order of the completed items. At the same time, we look at the above example. After the completion of the An item, there is no order for the B and C items, no matter the B or C items are completed first. Therefore, the sequence of the topological sorting is not completely certain.

Working process

First of all, the corresponding operation of topological sorting is a directed acyclic graph. If there is an acyclic graph, there must be at least one node with a degree of 0. In the current situation, we need to find a node with a degree of 0 to operate, which means that the current node does not have a precursor node, or the precursor node has been processed and can be operated directly. After the operation is completed, all the successor nodes of the current node are subtracted by 1, and the nodes with the entry degree of 0 are found again for operation. after that, there is a recursive process, constantly dealing with the nodes with the entry degree of 0 in the current situation. until all nodes are processed.

Data structure

The structure of the directed graph is as follows, where node stores all the nodes contained in the current graph, and adj stores the adjacency points of the corresponding subscript nodes. When initializing the graph, we need to initialize the number of nodes in the graph, the array of storage nodes and the corresponding adjacency array of nodes. At the same time, an addEdge method is provided, which is used to add edges directly to two nodes, which is to put the successor node into the adjacency table of the precursor node.

Number of public static class Graph {/ * nodes * / private Integer nodeSize; / * * nodes * / private char [] node; / * adjacency table * / private LinkedList [] adj; public Graph (char [] node) {this.nodeSize = node.length This.node = node; this.adj = new LinkedList [nodeSize]; for (int I = 0; I < adj.length; iTunes +) {adj [I] = new LinkedList () }} / * add edges between nodes, and the precursor node points to the subscript of the successor node * @ param front precursor node * @ param end the subscript of the successor node * / public void addEdge (int front, int end) {[front] .add (end);}} topological sort

Topological sorting first initializes two temporary arrays, one queue and one inDegree array to store the entry degree of the corresponding subscript node, because each visiting node requires that the precursor node has been completed, that is, the entry degree is 0, with this array, we can find these nodes more quickly; the other is the visited array, which indicates whether the current node has been accessed and prevents multiple visits. A nodes queue holds all nodes with a degree of 0 in the current situation. (note that for convenience of access, we all store node subscript step1: initialize inDegree array and visited array; step2: traverse inDegree array and put all nodes with degree 0 into nodes queue; step3: dequeue nodes in turn; determine whether the current node has been accessed according to visited. Yes, return step3, No, proceed to the next step. Check whether the adjacency of the current node is 0, put it into the nodes queue directly, and return step3 if it is 0.

/ * * @ param graph directed acyclic graph * @ return topological sort result * / public List toPoLogicalSort (Graph graph) {/ / use an array to mark the entry degree of all nodes int [] inDegree = new int [graph.nodeSize]; for (LinkedList list: graph.adj) {for (Object index: list) {+ + inDegree [(int) index] }} / / use an array to mark whether all nodes have been accessed boolean [] visited = new boolean [graph.nodeSize]; / / start traversing Deque nodes = new LinkedList (); / / queue for with 0 nodes (int I = 0; I < graph.nodeSize) Nodes.offer +) {if (inDegree [I] = = 0) {nodes.offer (I);}} List result = new ArrayList (); / / while (! nodes.isEmpty ()) {int node = nodes.poll (); if (visited [node]) {continue } visited [node] = true; result.add (graph.node [node]); / / put the adjacency node of the current node into the degree-1 For (Object list: graph.adj [node]) {--inDegree [(int) list]; if (inDegree [(int) list] = = 0) {/ / all the precursor nodes have been accessed with a penetration of 0 nodes.offer ((int) list);} return result } Test sample 1public static void main (String [] args) {ToPoLogicalSort toPoLogicalSort = new ToPoLogicalSort (); / / initialize a graph Graph graph = new Graph (new char [] {'A','B','C','D'}); graph.addEdge (0,1); graph.addEdge (0J 2); graph.addEdge (1J 3); graph.addEdge (2J 3); List result = toPoLogicalSort.toPoLogicalSort (graph) }

Execution result

Test sample 2public static void main (String [] args) {ToPoLogicalSort toPoLogicalSort = new ToPoLogicalSort (); / / initialize a graph Graph graph = new Graph (new char [] {'A','B','C','D')); graph.addEdge (0, 1); graph.addEdge (0, 2); graph.addEdge (0, 3); graph.addEdge (1) Graph.addEdge (2); graph.addEdge (3); graph.addEdge (4); graph.addEdge (4); graph.addEdge (7); graph.addEdge (6); List result = toPoLogicalSort.toPoLogicalSort (graph);}

Execution result

These are all the contents of the article "how to achieve topological sorting in Java". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.