Java language description storage structure and adjacency matrix code example

storage structure

To store a graph, we know that the graph has both nodes and edges. For a weighted graph, each edge also has weights. There are two common storage structures for graphs:

Adjacency matrix adjacency table

adjacency matrix

We know that to represent nodes, we can use a one-dimensional array. However, for the relationship between nodes, we can't simply use a one-dimensional array. We can use a two-dimensional array, that is, a matrix representation.

We assume that a is this two-dimensional array, then an element AIJ in a not only reflects the relationship between node VI and node VJ, but also the value of AIJ can represent the weight.

The following is an example of adjacency matrix representation of an undirected graph:

From the above figure, we can see that the adjacency matrix of an undirected graph is a symmetric matrix and must be a symmetric matrix. And the value on the diagonal from the upper left corner to the lower right corner is zero (the diagonal represents the same node)

What is the adjacency matrix of a directed graph?

For weighted graphs, the value of AIJ can be used to represent the weight. The above two graphs are non weighted graphs, so their values are 1.

Adjacency table

We know that the adjacency matrix storage method of a graph uses an n * n matrix. When the matrix is dense (for example, when the graph is a complete graph), of course, the adjacency matrix storage method is selected.

However, if the matrix is sparse, the adjacency table storage structure is a more space-saving storage structure.

The undirected graph in the above can be represented by adjacency table as follows:

The next node after each node is its adjacent node.

Comparison between adjacency matrix and adjacency table

When the number of nodes in the graph is small and there are many edges, the efficiency of using adjacency matrix is higher. When the number of nodes is large and the number of edges is far less than the number of edges of a complete graph with the same node, the adjacency table storage structure is more efficient.

Java implementation of adjacency matrix

Adjacency matrix model class

The class name of adjacency matrix model class is amwgraph Java, can construct a graph represented by adjacency matrix through this class, and provide insertion nodes and insertion edges to obtain the first adjacent node and the next adjacent node of a node.

Test of adjacency matrix model class

Next, set and test the model class according to the following directed graph

TestAMWGraph. The java test program is as follows:

The console output results are shown in the figure below:

summary

The above is all about the code example of Java language description storage structure and adjacency matrix. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message to point out.