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.
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;
public class AMWGraph {
private ArrayList vertexList;
//The link table of storage points
private int[][] edges;
//Address matrix, used to store edges
private int numOfEdges;
//Number of edges
public AMWGraph(int n) {
//Initialize the matrix, one-dimensional array, and the 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 and v2
public int getWeight(int v1,int v2) {
return edges[v1][v2];
}
//Insert 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 subscript 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;
}
//Get the next adjacency node based on 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;
}
}Let’s take a look at the code that implements the adjacency matrix to represent dense graphs:
package com.dataStructure.graph;
///// Dense graph - Use adjacency matrix to represent
//public class DenseGraph {
//
// private int n; // number of nodes
// private int m; // edge number
// private boolean directed; // Is it a directed graph
// private boolean[][] g; // Specific data of the picture
//
// // Constructor
// public DenseGraph(int n, boolean directed) {
// assert n >= 0;
// this.n = n;
// this.m = 0; // Initialization has no edges
// this.directed = directed;
// // g is initialized to a boolean matrix of n*n. Each g[i][j] is false, indicating that there are no any and edges.
// // false is the default value of boolean type variable
// g = new boolean[n][n];
// }
//
// public int V() {
// return n;
// } // Return the number of nodes
//
// public int E() {
// return m;
// } // Return the number of edges
//
// // Add an edge to the graph
// public void addEdge(int v, int w) {
//
// assert v >= 0 && v < n;
// assert w >= 0 && w < n;
//
// if (hasEdge(v, w))
// return;
//
// // Connect v and w
// g[v][w] = true;
// if (!directed)
// g[w][v] = true;
//
// // Number of edges++
// m++;
// }
//
// // Verify whether there are edges from v to w in the graph
// boolean hasEdge(int v, int w) {
// assert v >= 0 && v < n;
// assert w >= 0 && w < n;
// return g[v][w];
// }
//
// // Return all neighbors of a vertex in the graph
// // Since Java uses a reference mechanism, returning a Vector will not bring any additional overhead.
// public Iterable<Integer> adj(int v) {
// assert v >= 0 && v < n;
// Vector<Integer> adjV = new Vector<Integer>();
// for(int i = 0 ; i < n ; i ++ )
// if( g[v][i] )
// adjV.add(i);
// return adjV;
// }
//}
import java.util.ArrayList;
import java.util.List;
// Use adjacency matrix to represent dense graphs
public class DenseGraph{
private int n;
// Number of nodes in the figure
private int m;
// Number of edges in the picture
private Boolean[][] g;
// Adjacent matrix g
private Boolean directed;
// Is it a directed graph
public DenseGraph(int n, Boolean directed){
this.n = n;
// The number of nodes in the initialization graph
this.m = 0;
// The number of edges in the figure is initialized to 0
this.directed = directed;
g = new Boolean[n][n];
// The adjacency matrix g is initialized into a two-dimensional matrix of n*n
// The index represents the node in the graph, and the value stored in g is whether the node has edges
}
// Return the number of edges in the graph
public int E(){
return m;
}
// Return the number of nodes in the graph
public int V(){
return n;
}
// Add edges between the two nodes specified in the figure
public void addEdge(int v, int w){
if (!hasEdge(v, w)){
// Connect [v][w]
g[v][w] = true;
// Undirected graph
if (!directed)
g[w][v] = true;
// The number of sides in the picture +1
m++;
}
}
// Determine whether there are edges between the two nodes
private Boolean hasEdge(int v, int w){
return g[v][w];
}
// Returns the adjacency nodes of all nodes v
public Iterable<Integer> adjacentNode(int v){
// adjacentL is used to store the adjacent node of v
List<Integer> adjacentL = new ArrayList<>();
// Find all nodes adjacent to v and add them to adjacentL
for (int i = 0; i < n;i++){
if (g[v][i])
adjacentL.add(i);
}
return adjacentL;
}
}
Summarize
The above is all the content of this article about Java programming to implement the code example of dense graph representation of adjacency matrix, and I hope it will be helpful to everyone. Interested friends can continue to refer to this site:
Analysis of basic concepts and code examples of java data structure tree
Java common data structure interview questions (with answers)
Multimode string matching algorithm principle and Java implementation code
If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!