隣接行列を使用してJavaでグラフを保存するにはどうすればよいですか?-＆＃＆チュートリアル-php.cn

隣接行列を使用してJavaでグラフを保存するにはどうすればよいですか?

PHPz

リリース： 2023-04-24 09:55:07

転載

1366 人が閲覧しました

1. 最後の仕上げ

隣接行列は通常、グラフ内のノードの情報を格納するために 1 次元配列を使用し、グラフ内のノードの情報を格納するために 2 次元配列を使用します。 - グラフ内のノード間の情報を格納する次元配列。

隣接行列は、無向グラフ、有向グラフ、およびネットワークを表すために使用できます。

1. 無向グラフの隣接行列

無向グラフでは、ノード Vi からノード Vj までのエッジがある場合、隣接行列 M[i][j] = M[ j ][i ]= 1、それ以外の場合は M[i][j] = 0。

無向グラフの隣接行列は次のように指定します。

a 無向グラフの隣接行列は対称行列であり、一意です。

b 行 I または列 i の非ゼロの数は、ノード i の次数と正確に一致します。

2. 有向グラフの隣接行列

有向グラフにおいて、ノード Vi からノード Vj までのエッジがある場合、隣接行列 M[i][j]=1、それ以外の場合は、M[i][j]=0。

有向グラフの隣接行列は次のように指定します。

a 有向グラフの隣接行列は必ずしも対称である必要はありません。

b i 番目の行の非ゼロ要素の数は正確に i 番目のノードの出次数であり、i 番目の列の非ゼロ要素の数は正確にi 番目のノードの入次数。

3. ネットワークの隣接行列

ネットワークは重み付きグラフであり、エッジの重みを保存する必要があります。隣接行列は次のように表されます: M[i][ j] = Wij、その他の場合: 巨大。

2. アルゴリズムのステップ

1 ノードとエッジの数を入力します。

2 ノード情報を順に入力し、ノード配列 Vex[]に格納します。

3 隣接行列を初期化します。グラフの場合は 0 に、ネットワークの場合は無限大に初期化します。

4 各エッジに接続されている 2 つのノードを順番に入力します。ネットワークの場合は、エッジの重みも入力する必要があります。

無向グラフの場合、a と b を入力し、ノード配列 Vex[] 内のノード a と b の記憶添字 i と j をクエリし、Edge[i][ とします。 j]=エッジ[j][i]=1。
有向グラフの場合、a と b を入力し、ノード配列 Vex[] 内のノード a と b の記憶添字 i と j をクエリし、Edge[i][ とします。 j]=1。
無向ネットワークの場合、a、b、w を入力し、ノード配列 Vex[] 内のノード a および b のストレージ添字 i および j をクエリし、Edge[i にします][j]=エッジ[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; // 边数
}

ログイン後にコピー