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

This article mainly explains "the concept and storage of java diagram". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn the concept and storage of java diagrams.

The concept of graph and its storage

Graph (Graph) is the most complex data structure. Linear table describes one-to-one relationship, tree describes one-to-many relationship, and graph describes many-to-many relationship. Whether it is one-to-one or one-to-many, there is a clear entry point, but the diagram does not have this simple attribute. Because of this, the basic knowledge about the graph is also the most, so let's sort out these basic knowledge first.

The definition of concept graph of graph

A graph (Graph) is composed of a finite nonempty set of vertices and a set of edges between vertices, which is usually expressed as G (V, E), where G denotes a graph, V is a set of vertices in G, and E is a set of edges in G. Vertices are the data elements in the graph, and edges are used to represent the logical relationship between the data. The vertex is finite and non-empty, while the edge can be an empty set.

Directed edge and undirected edge

Edges, according to whether there is a direction, are divided into undirected edges and directed edges. An undirected edge means that the edge between vertices vi and vj has no direction, denoted by (vi, vj). Directed edges refer to the direction of the edges between vertices vi and vj, also known as arcs, where vi is called arc tail or initial point, and vj is called arc head or end point, that is, arrows from vi to vj, the order cannot be exchanged. As shown in the following figure, the graph on the left has undirected edges and the graph on the right has directed edges.

The left graph can be represented as G1 = (V1, {E1}), where vertex set V1 = {A, B, C, D}, edge set E1 = {(A, B), (B, C), (C, D), (D, A), (A, C)}. The right graph can be represented as G2 = (V2, {E2}), where the vertex set V2 = {A, B, C, D} and the arc set E2 = {,}.

Digraph and undirected graph

A graph is called an undirected graph if the edges between any two vertices in the graph are undirected edges. In an undirected graph, if there are edges between any two vertices, the graph is called an undirected complete graph. An undirected complete graph with n vertices has n (n Mel 1) / 2 edges.

Similarly, if the edge between any two vertices in a graph is a directed edge, the graph is called a directed graph. In a directed graph, if there are two arcs with opposite directions between any two vertices, the graph is called a directed complete graph. A complete digraph with n vertices has n (n Mel 1) edges.

As shown below, the left is an undirected complete graph and the right is a directed complete graph.

Simple graph

In a graph, if there is no edge from the vertex to itself and the same edge does not repeat, such a graph is called a simple graph. The graphs we are going to study are all simple graphs. As shown below, they are not simple diagrams and do not belong to the category of our study.

Sparse graph and dense graph

A graph with few edges or arcs is called a sparse graph and vice versa is called a dense graph. This is a relative concept.

Net

A weighted graph is called a network, and weight refers to the numbers on the edges or arcs of the graph. For example, the following figure is a weighted graph:

Subgraph

Suppose that there are two graphs G = (V, {E}) and G = (V, {E'}). If V '∈ V and E' belong to E, then G'is called a subgraph of G. In short, it is the relationship between the part and the whole.

The relationship between vertices and edges

For an undirected graph G = (V, {E}), if the edge (v, v') ∈ E, then the vertices v and v 'are said to be adjacent to each other, that is, v and v' are adjacent to each other, and the edge (v, v') is attached to vertices v and v, or (v, v') is associated with vertices v and v'. The degree of vertex v is the number of edges associated with v, denoted by TD (v). The relationship between the number of edges and vertex degrees of an undirected graph is as follows:

For a digraph G = (V, {E}), if the arc is associated with vertex v, v'. The number of arcs starting with vertex v is called the entry degree of v, denoted by ID (v), the number of arcs tailed by v is called the exit degree of v, denoted by OD (v), and the degree of vertex v is called TD (v) = ID (v) + OD (v). The relationship between the number of arcs and the degree of exit and entry of a digraph is as follows:

Path

The path from vertex v to v'in undirected graph G = (V, {E}) is a vertex sequence. (vi,j-1,vi,j) ∈ E ≤ m.

If it is a directed graph, then the path is also directed, and the sequence of vertices satisfies ∈ E < 1 ≤ j ≤ m.

The length of the path is the number of edges or arcs on the path.

The same path from the first vertex to the last vertex is called a loop or ring. The path in which the vertices do not repeat in the sequence is called a simple path. Except for the first vertex and the last vertex, the loop in which the other vertices do not repeat is called a simple loop or a simple loop.

Connected graph

In undirected graph G, if there is a path from vertex v to v', then v and v 'are said to be connected. G is said to be a connected graph if vi,vj ∈ VJ vi and vj are connected for any two vertices in the graph. Maximal connected subgraphs in undirected graphs are called connected components. As shown in the following figure, the left is not a connected graph, but it has two connected components:

In a directed graph G, G is called a strongly connected graph if there is a path from vi to vj for every pair of vi,vj ∈ V and vi ≠ vj. The maximal strongly connected subgraph in a digraph is called the strongly connected component of a digraph. As shown in the following figure, although it is not a strongly connected graph, it has two strongly connected components:

Spanning tree and directed tree

The spanning tree of a connected graph is a minimal connected subgraph, which contains all n vertices in the graph, but only 1 edges that are sufficient to form a tree. As shown below, figure 1 is a connected graph, and figures 2 and 3 are its spanning tree:

N vertices and 1 edges are necessary to form a spanning tree, but it is not sufficient, as shown below, it is not a spanning tree:

If a directed graph has exactly one vertex with a degree of 0, and the rest of the vertices have a degree of 1, then it is a directed tree. The spanning forest of a directed graph consists of several directed trees, containing all the vertices in the graph, but only enough to form the arcs of several disjoint directed trees. As shown in the following figure, figure 1 can be split into two directed trees, figure 2 and figure 3.

Storage of graphs

Both linear tables and graphs have a clear cut-in point, but for a graph, each vertex can be used as a starting point, and there may be a logical relationship between each vertex, that is, it is impossible to store a graph simply by using an array or a linked list. Currently, there are five main ways to store graphs:

1. Adjacency matrix

The adjacency matrix (Adjacency Matrix) of a graph is stored in two arrays to represent the graph. An one-dimensional array stores vertex information in the graph, and a two-dimensional array (called adjacency matrix) stores information about edges or arcs in the graph.

Let G have n vertices, then the adjacency matrix is a square matrix of n vertices, defined as:

Next, we demonstrate the storage of adjacency matrix for undirected graph, directed graph and net, respectively.

Undirected graph

Where the value of the main diagonal is 0, indicating that the vertex has no edge to itself. The adjacency matrix of an undirected graph must be symmetric, that is, the upper-right and lower-left symmetry divided by the principal diagonal. We can get the following information from the matrix:

Judge whether there is an edge between two vertices

To get the degree of a vertex, you only need to find the sum of row I or column I.

To get all the critical points of a vertex, you only need to traverse line I.

Directed graph

The representation of a directed graph is similar to that of an undirected graph, as follows:

Net

Because each edge of the network has a weight, the corresponding formula changes slightly, as follows:

Here ∞ represents an impossible value. Examples of adjacency matrix storage for the network are as follows:

two。 Adjacency table

We are already familiar with the advantages and disadvantages of arrays, so the use of adjacency matrix is bound to face the problem of space waste. The more 0 or ∞ in the above example, the less the number of edges in the corresponding graph relative to the number of vertices, the lower the space utilization. The idea of adjacency tables is similar to hash tables, using arrays combined with linked lists to store graphs.

Undirected graph

The adjacency table uses an array to store each vertex, and each bit of the array contains a linked list to store the edges adjacent to that vertex, as shown in the following example:

The values of vertices, edges, and degrees can also be easily obtained from the adjacency table.

Directed graph

The adjacency table of a directed graph is similar to that of an undirected graph, but it is easy to obtain the degree of access, but difficult to obtain the degree of entry, as shown below:

To obtain the output degree of a vertex, you only need to calculate the length of the linked list, but there is no effective way to obtain the input degree, so an inverse adjacency table is usually established as a supplement, as shown below:

Net

Using the adjacency table to store the structure of the network only needs to add a weight field, which is not demonstrated here.

3. Cross linked list

When representing a directed graph, the adjacency table needs the combination of the adjacency table and the inverse adjacency table, which is more tedious. We can combine the adjacency table and the inverse adjacency table into one table, which is the cross list.

Cross-linked lists also use arrays to store vertices, but for each bit of data, in addition to vertices, there are two linked lists that represent edge tables and incoming edge tables, respectively. The structure of the data is as follows:

The structure of the edge table has also changed, as follows:

Where tailvex represents the starting point of the arc in the subscript of the vertex table, headvex indicates that the arc ends in the subscript of the vertex table, headlink is the entry edge table pointer domain, pointing to the next edge with the same end point, and taillink is the outgoing edge table pointer domain, pointing to the next edge with the same starting point.

Next, let's take the following figure as an example to demonstrate the process of establishing a cross list:

First, store all the vertices as follows:

Then, we set up the outedge table of vertex v0, and we can find that this is the only edge, so its outside table is as follows:

In the same way, the outedges of other vertices are as follows:

Now, let's set up the entry table, which has two entry edges for vertex v0, which are and. As you can see, these two edges already exist in the outgoing table, so you can establish a relationship for them directly, as shown below:

In the same way, the incoming table of other vertices is established, and the results are as follows:

It can be seen that in addition to the complex structure, the cross-linked list not only solves the problem that the adjacency table can not obtain the degree of entry and exit at the same time, but also does not increase the required time complexity, so it is very suitable for the storage of directed graph.

4. Adjacency multiple table

The cross list is optimized for the directed graph, while the adjacency table also has some problems in representing the undirected graph. For example, if we want to delete the edge (v2, v0) of the following graph, we need to delete two positions in the adjacency table:

As you can see, this is caused by the repetition of data, so we can construct an adjacent multiple table in the way of a cross-linked list to solve the above problems. To do this, you need to redefine the edge table structure, as follows:

Where ivex and jvex are the subscript of the vertex table of two vertices attached to an edge, ilink represents the next edge attached to vertex ivex, and jlink represents the next edge attached to vertex jvex.

With the experience of cross-linked list, it is very easy to build an adjacent multiple table. Taking the above figure as an example, we first establish vertex nodes and edge table nodes, as follows:

It should be noted here that each node of the edge table appears only once, and then we can connect the relationships between these nodes according to the regulations, as shown below:

5. Edge set array

If we only focus on the operation of edges, we can also use an edge set array, which consists of two one-dimensional arrays, one array to store vertex information and the other array to store edge information. Each element of an array of edges consists of the start subscript, the end subscript, and the weight of an edge. This storage method is mainly used to find the minimum spanning tree algorithm of connected network: Kruskal algorithm.

At this point, I believe you have a deeper understanding of the concept and storage of java diagrams, so you might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.