Storage structure
To store a graph, we know that the graph has both nodes and edges. For a powered graph, each edge also has a weight value. There are two main types of commonly used graph storage structures:
Adjacent Matrix Adjacent Table
Adjacent Matrix
We know that to represent nodes, we can represent them with a one-dimensional array. However, for the relationship between nodes, we cannot simply represent them with a one-dimensional array. We can represent them with a two-dimensional array, that is, a matrix-forming representation method.
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 size of the weight.
Here is an example of an adjacency matrix representation of an undirected graph:
From the above figure we can see that the adjacency matrix of the 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 indicates 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 size of the weight. The above two graphs are graphs without weights, so their values are both 1.
Adjacent table
We know that the adjacency matrix storage method of the graph uses an n*n matrix. When this matrix is a dense matrix (for example, when the graph is a complete graph), then of course, the adjacency matrix storage method is chosen.
But if this matrix is a sparse matrix, the adjacent table storage structure is a more space-saving storage structure.
For the undirected graph above, we can use an adjacency table to represent it as follows:
The node connected to 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 sides, the efficiency of using an adjacency matrix is higher.
When the number of nodes is very large and the number of edges is much smaller than the number of edges of the complete graph of the same node, it is more efficient to adopt an adjacency table storage structure.
Java implementation of adjacency matrix
Adjacent Matrix Model Class
The class name of the adjacency matrix model class is AMWGraph.java. It can construct a graph represented by an adjacency matrix through this class, and provide insertion nodes, insert edges, and obtain the first adjacency node and the next adjacency node of a certain node.
import java.util.ArrayList;import java.util.LinkedList;/** * @description Adjacent matrix model class* @author beanlam * @time 2015.4.17 */public class AMWGraph { private ArrayList vertexList;//Storage points private int[][] edges;//Adjacent matrix, used to store edges private int numOfEdges;//Number of edges public AMWGraph(int n) { //Initialize matrix, one-dimensional array, and number of edges edges=new int[n][n]; vertexList=new ArrayList(n); numOfEdges=0; } //Get the number of nodes public int getNumOfVertex() { return vertexList.size(); } //Get the number of edges public int getNumOfEdges() { return numOfEdges; } //Return the data of node i public Object getValueByIndex(int i) { return vertexList.get(i); } //Return the weight of v1,v2 public int getWeight(int v1,int v2) { return edges[v1][v2]; } //Insert the node public void insertVertex(Object vertex) { vertexList.add(vertexList.size(),vertex); } //Insert node public void insertEdge(int v1,int v2,int weight) { edges[v1][v2]=weight; numOfEdges++; } //Delete node public void deleteEdge(int v1,int v2) { edges[v1][v2]=0; numOfEdges--; } //Get the index of the first adjacent node public int getFirstNeighbor(int index) { for(int j=0;j<vertexList.size();j++) { if (edges[index][j]>0) { return j; } } return -1; } //Fetch the next adjacency node according to the subscript of the previous adjacency node public int getNextNeighbor(int v1,int v2) { for (int j=v2+1;j<vertexList.size();j++) { if (edges[v1][j]>0) { return j; } } return -1; }}Testing of adjacency matrix model class
Next, set up the test model class based on the following directed graph
The TestAMWGraph.java test program is as follows:
/** * @description Test class of AMWGraph class* @author beanlam * @time 2015.4.17 */public class TestAMWGraph { public static void main(String args[]) { int n=4,e=4;//Represents the number of nodes and the number of edges respectively String labels[]={"V1","V1","V3","V4"};//Node identification AMWGraph graph=new AMWGraph(n); for(String label:labels) { graph.insertVertex(label);//Insert node} //Insert four edges graph.insertEdge(0, 1, 2); graph.insertEdge(0, 2, 5); graph.insertEdge(2, 3, 8); graph.insertEdge(3, 0, 7); System.out.println("The number of nodes is: "+graph.getNumOfVertex()); System.out.println("The number of edges is: "+graph.getNumOfEdges()); graph.deleteEdge(0, 1);//Delete <V1,V2> edge System.out.println("After deletion <V1,V2> edge..."); System.out.println("The number of nodes is: "+graph.getNumOfVertex()); System.out.println("The number of edges is: "+graph.getNumOfEdges()); }}The output results of the console are shown in the figure below:
Summarize
The above is all the content of this article about the Java language description of the storage structure and adjacency matrix code examples. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out.