Bagaimana untuk menggunakan matriks bersebelahan untuk menyimpan graf di Jawa?

1 Sentuhan penamat

Matriks bersebelahan biasanya menggunakan tatasusunan satu dimensi untuk menyimpan maklumat nod dalam graf, dan dua. tatasusunan -dimensi untuk menyimpan maklumat antara nod dalam graf.

Matriks bersebelahan boleh digunakan untuk mewakili graf tidak terarah, graf terarah dan rangkaian.

1. Matriks bersebelahan graf tidak berarah

Dalam graf tidak berarah, jika terdapat tepi dari nod Vi ke nod Vj, maka matriks bersebelahan M[i][j] = M[ j ][i ]= 1, jika tidak M[i][j] = 0.

Matriks bersebelahan graf tidak berarah dinyatakan seperti berikut.

a Matriks bersebelahan graf tidak terarah ialah matriks simetri dan unik.

b Bilangan bukan sifar dalam baris I atau lajur i adalah betul-betul darjah nod i.

2. Matriks bersebelahan graf berarah

Dalam graf berarah, jika terdapat tepi dari nod Vi ke nod Vj, maka matriks bersebelahan M[i][j]=1, sebaliknya M[i][j]=0.

Matriks bersebelahan graf terarah ditentukan seperti berikut.

a Matriks bersebelahan graf berarah tidak semestinya simetri.

b Bilangan elemen bukan sifar dalam baris ke-i adalah betul-betul darjah keluar nod ke-i dan bilangan elemen bukan sifar dalam lajur ke-i adalah betul-betul dalam darjah nod ke-i.

3. Matriks bersebelahan rangkaian

Rangkaian ialah graf berwajaran dan perlu menyimpan pemberat tepi Matriks bersebelahan dinyatakan sebagai: M[i][ j] = Wij, dalam kes lain: Infiniti.

2. Langkah-langkah algoritma

1 Masukkan bilangan nod dan tepi.

2 Masukkan maklumat nod dalam urutan dan simpannya dalam tatasusunan nod Vex[].

3 Mulakan matriks bersebelahan, jika ia adalah graf, mulakan ia kepada 0, jika ia rangkaian, mulakan ia kepada infiniti.

4 Masukkan dua nod yang dipasang pada setiap tepi secara bergilir-gilir Jika ia adalah rangkaian, anda juga perlu memasukkan berat tepi.

• Jika ia adalah graf tidak berarah, masukkan a, b, tanya subskrip storan i, j nod a, b dalam tatasusunan nod Vex[], biarkan Edge[i][ j]=Tepi[j][i]=1.

• Jika ia adalah graf terarah, masukkan a, b, tanya subskrip storan i, j nod a, b dalam tatasusunan nod Vex[], biarkan Edge[i][ j]=1.

• Jika ia adalah rangkaian tidak terarah, masukkan a, b, w, tanya subskrip storan i dan j nod a dan b dalam tatasusunan nod Vex[], biarkan Edge[i ][j]=Tepi[j][i]=w.

• Jika ia adalah rangkaian terarah, masukkan a, b, w, tanya subskrip storan i dan j nod a dan b dalam tatasusunan nod Vex[], biarkan Edge[i ][j]=w.

3. Pelaksanaan

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. Ujian

Hijau ialah input dan putih ialah output.

Atas ialah kandungan terperinci Bagaimana untuk menggunakan matriks bersebelahan untuk menyimpan graf di Jawa?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!