How to use adjacency matrix to store graph in Java?

1. The finishing touch

The adjacency matrix usually uses a one-dimensional array to store the information of the nodes in the graph, and a two-dimensional array to store the information between the nodes in the graph. adjacency relationship.

The adjacency matrix can be used to represent undirected graphs, directed graphs and networks.

1. Adjacency matrix of undirected graph

In the undirected graph, if there is an edge from node Vi to node Vj, then the adjacency matrix M[i][j] = M[j ][i ]= 1, otherwise M[i][j] = 0.

The adjacency matrix of an undirected graph is specified as follows.

a The adjacency matrix of an undirected graph is a symmetric matrix and is unique.

b The number of non-zeros in row I or column i is exactly the degree of node i.

2. Adjacency matrix of directed graph

In the directed graph, if there is an edge from node Vi to node Vj, then the adjacency matrix M[i][j]=1, otherwise M[i][j]=0.

The adjacency matrix of a directed graph is specified as follows.

a The adjacency matrix of a directed graph is not necessarily symmetric.

b The number of non-zero elements in the i-th row is exactly the out-degree of the i-th node, and the number of non-zero elements in the i-th column is exactly the in-degree of the i-th node.

3. The adjacency matrix of the network

The network is a weighted graph and needs to store the weights of the edges. The adjacency matrix is ​​expressed as: M[i][j] = Wij, in other cases: gigantic.

2. Algorithm steps

1 Enter the number of nodes and edges.

2 Enter the node information in sequence and store it in the node array Vex[].

3 Initialize the adjacency matrix. If it is a graph, initialize it to 0. If it is a network, initialize it to infinity.

4 Enter the two nodes attached to each edge in turn. If it is a network, you also need to enter the weight of the edge.

• If it is an undirected graph, enter a and b, query the storage subscripts i and j of nodes a and b in the node array Vex[], let Edge[i][ j]=Edge[j][i]=1.

• If it is a directed graph, enter a and b, query the storage subscripts i and j of nodes a and b in the node array Vex[], let Edge[i][ j]=1.

• If it is an undirected network, enter a, b, w, query the storage subscripts i and j of nodes a and b in the node array Vex[], let Edge[i ][j]=Edge[j][i]=w.

• If it is a directed network, enter a, b, w, query the storage subscripts i and j of nodes a and b in the node array Vex[], let Edge[i ][j]=w.

3. Implementation

package graph;
 
import java.util.Scanner;
 
public class CreateAMGraph {
    static final int MaxVnum = 100;  // 顶点数最大值
 
    static int locatevex(AMGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标
            if (x == G.Vex[i])
                return i;
        return -1; // 没找到
    }
 
    static void CreateAMGraph(AMGraph G) {
        Scanner scanner = new Scanner(System.in);
        int i, j;
        char u, v;
        System.out.println("请输入顶点数：");
        G.vexnum = scanner.nextInt();
        System.out.println("请输入边数:");
        G.edgenum = scanner.nextInt();
        System.out.println("请输入顶点信息:");
 
        // 输入顶点信息，存入顶点信息数组
        for (int k = 0; k < G.vexnum; k++) {
            G.Vex[k] = scanner.next().charAt(0);
        }
        //初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大
        for (int m = 0; m < G.vexnum; m++)
            for (int n = 0; n < G.vexnum; n++)
                G.Edge[m][n] = 0;
 
        System.out.println("请输入每条边依附的两个顶点：");
        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);
 
            i = locatevex(G, u);// 查找顶点 u 的存储下标
            j = locatevex(G, v);// 查找顶点 v 的存储下标
            if (i != -1 && j != -1)
                G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1
            else {
                System.out.println("输入顶点信息错！请重新输入！");
                G.edgenum++; // 本次输入不算
            }
        }
    }
 
    static void print(AMGraph G) { // 输出邻接矩阵
        System.out.println("图的邻接矩阵为：");
        for (int i = 0; i < G.vexnum; i++) {
            for (int j = 0; j < G.vexnum; j++)
                System.out.print(G.Edge[i][j] + "\t");
            System.out.println();
        }
    }
 
    public static void main(String[] args) {
        AMGraph G = new AMGraph();
        CreateAMGraph(G);
        print(G);
    }
}
 
class AMGraph {
    char Vex[] = new char[CreateAMGraph.MaxVnum];
    int Edge[][] = new int[CreateAMGraph.MaxVnum][CreateAMGraph.MaxVnum];
    int vexnum; // 顶点数
    int edgenum; // 边数
}

4. Test

Green is input and white is output.

The above is the detailed content of How to use adjacency matrix to store graph in Java?. For more information, please follow other related articles on the PHP Chinese website!