首頁 > 文章 > Java > Java中如何使用鄰接矩陣儲存圖？

Java中如何使用鄰接矩陣儲存圖？

PHPz轉載: 2023-04-24 09:55:071350瀏覽

一、點睛

鄰接矩陣通常採用一個一維數組儲存圖中節點的信息，採用一個二維數組儲存圖中節點之間的鄰接關係。

鄰接矩陣可以用來表示無向圖、有向圖和網。

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,其他情況為無窮大。

二、演算法步驟

1 輸入節點數與邊數。

2 依序輸入節點訊息，將其儲存到節點數組 Vex[] 中。

3 初始化鄰接矩陣，如果是圖，則將其初始化為0，如果是網，則將其初始化為無限大。

4 依序輸入每條邊依附的兩個節點，如果是網，則還需要輸入該邊的權值。

如果是無向圖，則輸入a,b，查詢節點a、b在節點數組Vex[] 中的儲存下標i、j，讓Edge[i][ j]=Edge[j][i]=1。
如果是有向圖，則輸入a,b，查詢節點a、b在節點數組Vex[] 的儲存下標i、j，讓Edge[i][ j]=1。
如果是無向網，則輸入a，b，w，查詢節點a、b在節點數組Vex[] 中的儲存下標i、j，讓Edge[i ][j]=Edge[j][i]=w。
如果是有向網，則輸入a，b，w，查詢節點a、b在節點數組Vex[] 中的儲存下標i、j，讓Edge[i ][j]=w。

三、實作

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