인접 행렬을 사용하여 Java에 그래프를 저장하는 방법은 무엇입니까?-java지도 시간-php.cn

인접 행렬을 사용하여 Java에 그래프를 저장하는 방법은 무엇입니까?

PHPz

풀어 주다： 2023-04-24 09:55:07

앞으로

1351명이 탐색했습니다.

1. 마무리

인접 행렬은 일반적으로 그래프의 노드 정보를 저장하기 위해 1차원 배열을 사용하고, 그래프에서 노드 간의 인접 관계를 저장하기 위해 2차원 배열을 사용합니다. 그래프.

인접 행렬은 무방향 그래프, 유방향 그래프 및 네트워크를 나타내는 데 사용할 수 있습니다.

1. 무방향 그래프의 인접 행렬

무방향 그래프에서 노드 Vi에서 노드 Vj까지 간선이 있으면 인접 행렬 M[i][j] = M[j][i]= 1, 그렇지 않으면 M[i][j] = 0입니다.

무방향 그래프의 인접 행렬은 다음과 같이 지정됩니다.

a 무방향 그래프의 인접 행렬은 대칭 행렬이며 고유합니다.

b i번째 행이나 i번째 열에 있는 0이 아닌 숫자의 개수는 정확히 i번째 노드의 차수입니다.

2. 유향 그래프의 인접 행렬

유향 그래프에서 노드 Vi에서 노드 Vj까지의 간선이 있으면 인접 행렬 M[i][j]=1이고, 그렇지 않으면 M[i][j]입니다. = 0.

유향 그래프의 인접 행렬은 다음과 같이 지정됩니다.

a 유방향 그래프의 인접 행렬이 반드시 대칭일 필요는 없습니다.

b i번째 행에 있는 0이 아닌 요소의 수는 정확히 i번째 노드의 진출 차수이고 i번째 열에 있는 0이 아닌 요소의 수는 정확히 i번째 노드의 내부 차수입니다. i번째 노드.

3. 네트워크의 인접 행렬

네트워크는 가중치 그래프이며 가장자리의 가중치를 저장해야 합니다. 인접 행렬은 M[i][j] = Wij로 표현됩니다. 다른 경우에는 무한합니다.

2. 알고리즘 단계

1 노드와 모서리의 수를 입력합니다.

2 노드 정보를 차례로 입력하고 노드 배열 Vex[]에 저장합니다.

3 인접 행렬을 초기화하고 그래프인 경우 0으로 초기화하고 네트워크인 경우 무한대로 초기화합니다.

4 각 Edge에 연결된 두 개의 노드를 차례로 입력합니다. 네트워크인 경우 Edge의 가중치도 입력해야 합니다.

무방향 그래프인 경우 a와 b를 입력하고 노드 배열 Vex[]에서 노드 a와 b의 저장 첨자 i와 j를 쿼리하고 Edge[i][j]=Edge[j][ 나]=1.
유향 그래프인 경우 a, b를 입력하고 노드 배열 Vex[]에서 노드 a, b의 저장 첨자 i, j를 쿼리하고 Edge[i][j]=1로 둡니다.
무방향 네트워크인 경우 a, b, w를 입력하고 노드 배열 Vex[]에서 노드 a 및 b의 저장 첨자 i 및 j를 쿼리하고 Edge[i][j]=Edge[j ][i]=w.
방향 네트워크인 경우 a, b, w를 입력하고 노드 배열 Vex[]에 있는 노드 a 및 b의 저장 첨자 i 및 j를 쿼리하고 Edge[i][j]=w로 둡니다.

3. 구현

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; // 边数
}

로그인 후 복사