Shulou(Shulou.com)06/01 Report--

This article shares with you the content of the sample analysis of the diagram in the Java data structure. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Directed graph

The definition of directed graph and related terms

∶ digraph is defined as a directed graph, which is composed of a set of vertices and a set of directed edges, and the edges in each direction are connected with a pair of ordered vertices.

Degree ∶ the number of edges indicated by a vertex is called the degree of that vertex.

Degree: the number of edges pointing to a vertex is called the degree of that vertex.

Directed path: consists of a series of vertices, each of which has a directed edge from which it points to the next vertex in the sequence.

The directed ring ∶-strip contains at least one edge and has the same directed path as the starting point and end point.

Two vertices v and w in a digraph may have the following four relationships:

1. No edges are connected.

⒉ has edges from v to w v-> w

3. There is an edge w-> V from w to v

4. There are both sides of w to v and edges of v to w, that is, two-way connection.

It is relatively easy to understand a digraph, but it is not so easy to see the paths in a complex digraph through the eyes.

Directed graph API design

A reverse graph is designed in api, because in the implementation of the directed graph, the other vertices pointed to by the current vertex v are obtained by the adj method. If the inverse graph can be obtained, the other vertices pointing to v can be easily obtained.

Implementation of directed graph / / digraph public class Digraph {/ / record the number of vertices private final int V; / / record the number of edges private int E; / / define the adjacency table private Queue [] adj; public Digraph (int v) {/ / initialize the number of vertices this.V = v; / / initialize the number of edges this.E = 0 / / initialize the adjacency table adj = new LinkedList [v]; / / initialize the empty queue for of the adjacency table (int I = 0; I

< v; i++) { adj[i] = new LinkedList(); } } public int V () { return V; } public int E () { return E; } //添加一条 v ->

Directed edge public void addEage (int v, int w) {adj[ v] .add (w); + + E;} / / get all vertices public Queue adj (int v) {return adj [v] pointed by vertex v } / / after reversing the directed graph, return public Digraph reverse () {/ / create a reverse graph Digraph reverseDigraph = new Digraph (V); / / get each node for (int I = 0; I) of the original directed graph

< V; i++) { //获取每个结点 邻接表的所有结点 for (Integer w : adj[i]) { //反转图记录下 w ->

V reverseDigraph.adj (w) .add (I);}} return reverseDigraph;}} topological sort

In real life, we often receive a lot of tasks at the same time, but these tasks are completed in order. Take our study of java as an example, we need to learn a lot of knowledge, but this knowledge needs to be completed in order in the process of learning. From the foundation of java, to jsp/servlet, to ssm, to springboot is a gradual and dependent process. Before learning jsp, we should first master the basics of java and html, and before learning the ssm framework, we should master jsp/servlet and so on.

To simplify the problem, we use a standard model with integer vertex numbers to represent this case:

At this point, if a student wants to take these courses, he needs to specify a learning plan. We only need to sort the vertices in the graph and convert them into a linear sequence, which can solve the problem. At this time, we need to use an algorithm called topological sorting.

Topological sorting diagram

Given a directed graph, sort all the vertices so that all directed edges point from the front element to the last element, and the priority of each vertex can be clearly expressed. The following is a schematic diagram of a topological sort:

Detect rings in a digraph

If we must learn the y course before learning the x course, the z course before the y course, and the x course before the z course, then there must be a problem, and we will have no way to learn, because these three conditions cannot be met at the same time. In fact, the conditions of these three courses x, y, z form a ring:

Therefore, if we want to use topological sorting to solve the priority problem, we must first ensure that there are no rings in the graph.

API Design for detecting directed Rings

Detection of directed ring implementation

The onStack [] Boolean array is added to API, and the index is the vertex of the graph. When we search deeply:

1. If the current vertex is being searched, change the value in the corresponding onStack array to true to identify the stack

two。 If the search for the current vertex is complete, change the value in the corresponding onStack array to false to identify the stack

3. If you are about to search for a vertex, but the vertex is already in the stack, there is a ring in the graph

The code / * checks whether there is a ring in the graph * / public class DirectedCycle {/ * index represents a vertex, which is used to record whether the vertex has been searched * / private boolean [] marked; / * to determine whether there is a ring * / private boolean hasCycle in the graph. / * uses the idea of stack to record whether the current vertex already exists on the path of the current search * existence can determine that there is a loop in the graph * / private boolean [] onStack. / * determine whether there is a cycle in the incoming digraph * @ param G * / public DirectedCycle (Digraph G) {marked = new boolean [G.V ()]; onStack = new boolean [G.V ()]; hasCycle = false / / since it is not known that there may be a ring from that point / / it is necessary to search all vertices to determine whether there is a ring for (int I = 0; I < G.V ()) {dfs (GMIT I) }} / * use depth search to determine whether there is a loop in a directed graph * onStack enters and leaves the stack, and then determines whether the currently searched vertex has already searched marked [v] = true on the search path * * @ param G * @ param v * / private void dfs (Digraph Gline int v) {/ / marked vertex For (Integer adj: G.adj (v)) {/ / determine whether v is already on the search path if (if [ADJ] & & onStack [adj]) {/ / there is a ring hasCycle = true } else {/ / adopt the idea of backtracking / / put vertices on the stack onStack [adj] = true; dfs (GMagneadj); / / backtrack vertices out of the stack onStack [adj] = false } / * determine whether there is a ring * @ return * / public boolean hasCycle () {return hasCycle;}} Vertex sorting based on depth first

If we want to generate a linear sequence of vertices in a graph is actually a very simple thing, we have learned and used depth-first search many times before, we will find that in fact, depth-first search has a characteristic, that is, on a connected subgraph, each vertex will only be searched once, if we can add a line of code on the basis of depth-first search. We can do this simply by putting the searched vertices into the data structure of the linear sequence.

Vertex sorting API Design

Implementation of vertex sorting

In the design of API, we add a stack reversePost to store vertices. When we search deeply for a graph, every time we finish searching for a vertex, we put it into the reversePost, so we can sort the vertices.

Code: / * depth first search vertex sort * / public class DepthFirstOrder {/ * index represents vertices, which is used to record whether vertices have been searched * / private boolean [] marked; / * vertices under depth first search using stack records * / private Stack reversePost Public DepthFirstOrder (Digraph G) {marked = new boolean [G.V ()]; reversePost = new Stack (); for (int I = 0; I < G.V (); iTunes +) {/ / if vertices have been searched, do not use if (! marked [I]) dfs (GMague I) }} / * * based on depth-first search, generate vertex linear sequence * @ param G * @ param v * / private void dfs (Digraph G, int v) {/ / marked vertices have been searched for marked [v] = true For (Integer w: G.adj (v)) {if (! marked [w]) dfs (GMagnew);} / / record to linear sequence reversePost.push (v);} / * * get vertex linear sequence * @ return * / private Stack ReversePost () {return reversePost Thank you for your reading! This is the end of this article on "sample Analysis of diagrams in Java data structures". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!

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.