儲存圖（鄰接矩陣）

要儲存圖形，有兩種常見方法：

• 鄰接矩陣
• 鄰接名單

鄰接矩陣是用於表示一個有限圖的正方形矩陣。矩陣的元素指示圖中的頂點對是否相鄰。

相鄰意味著’毗鄰或毗鄰其他東西’或旁邊的東西。例如，你的鄰居與你相鄰。在圖論中，如果我們可以從節點 A 轉到節點 B ，我們可以說節點 B 與節點 A 相鄰。現在我們將瞭解如何通過 Adjacency Matrix 儲存哪個節點與哪個節點相鄰。這意味著，我們將表示哪些節點在它們之間共享邊緣。這裡矩陣表示 2D 陣列。 **** **** ****

https://i.stack.imgur.com/Oh7b1.jpg

在這裡你可以看到圖表旁邊的表格，這是我們的鄰接矩陣。這裡 Matrix [i] [j] = 1 表示在 i 和 j 之間存在邊緣。如果沒有邊緣，我們只需將 Matrix [i] [j] = 0 。

這些邊可以加權，就像它可以代表兩個城市之間的距離。然後我們將值放在 **Matrix [i] [j]中，**而不是放 1。

上面描述的圖是雙向的或無向的，這意味著，如果我們可以從節點 2 轉到節點 1 ，我們也可以從節點 1 轉到節點 2 。如果圖表是定向的，那麼圖表的一側會有箭頭符號。即便如此，我們也可以使用鄰接矩陣來表示它。 **** **** **** **

https://i.stack.imgur.com/MBM3s.jpg

我們表示不通過無窮大共享邊緣的節點。需要注意的一點是，如果圖是無向的，則矩陣變得對稱。

用於建立矩陣的虛擬碼：

Procedure AdjacencyMatrix(N):    //N represents the number of nodes
Matrix[N][N]
for i from 1 to N
    for j from 1 to N
        Take input -> Matrix[i][j]
    endfor
endfor

我們也可以使用這種常見方式填充 Matrix：

Procedure AdjacencyMatrix(N, E):    // N -> number of nodes
Matrix[N][E]                        // E -> number of edges
for i from 1 to E
    input -> n1, n2, cost
    Matrix[n1][n2] = cost
    Matrix[n2][n1] = cost
endfor

對於有向圖，我們可以刪除 Matrix [n2] [n1] =成本線。

使用 Adjacency Matrix 的缺點：

記憶是一個巨大的問題。無論有多少邊，我們總是需要 N * N 大小的矩陣，其中 N 是節點的數量。如果有 10000 個節點，則矩陣大小將為 4 * 10000 * 10000，大約為 381 兆位元組。如果我們考慮具有一些邊緣的圖形，則這是對記憶體的巨大浪費。

假設我們想知道我們可以從節點 u 到哪個節點。我們將需要檢查的整排 U ，花費了大量的時間。

唯一的好處是，我們可以使用 Adjacency Matrix 輕鬆找到 uv 節點之間的連線及其成本。

使用上面的虛擬碼實現的 Java 程式碼：

import java.util.Scanner;
 
public class Represent_Graph_Adjacency_Matrix 
{
    private final int vertices;
    private int[][] adjacency_matrix;
 
    public Represent_Graph_Adjacency_Matrix(int v) 
    {
        vertices = v;
        adjacency_matrix = new int[vertices + 1][vertices + 1];
    }
 
    public void makeEdge(int to, int from, int edge) 
    {
        try 
        {
            adjacency_matrix[to][from] = edge;
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
    }
 
    public int getEdge(int to, int from) 
    {
        try 
        {
            return adjacency_matrix[to][from];
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
        return -1;
    }
 
    public static void main(String args[]) 
    {
        int v, e, count = 1, to = 0, from = 0;
        Scanner sc = new Scanner(System.in);
        Represent_Graph_Adjacency_Matrix graph;
        try 
        {
            System.out.println("Enter the number of vertices: ");
            v = sc.nextInt();
            System.out.println("Enter the number of edges: ");
            e = sc.nextInt();
 
            graph = new Represent_Graph_Adjacency_Matrix(v);
 
            System.out.println("Enter the edges: <to> <from>");
            while (count <= e) 
            {
                to = sc.nextInt();
                from = sc.nextInt();
 
                graph.makeEdge(to, from, 1);
                count++;
            }
 
            System.out.println("The adjacency matrix for the given graph is: ");
            System.out.print("  ");
            for (int i = 1; i <= v; i++)
                System.out.print(i + " ");
            System.out.println();
 
            for (int i = 1; i <= v; i++) 
            {
                System.out.print(i + " ");
                for (int j = 1; j <= v; j++) 
                    System.out.print(graph.getEdge(i, j) + " ");
                System.out.println();
            }
 
        }
        catch (Exception E) 
        {
            System.out.println("Somthing went wrong");
        }
 
        sc.close();
    }
}

執行程式碼：儲存檔案並使用 javac Represent_Graph_Adjacency_Matrix.java 進行編譯

例：

$ java Represent_Graph_Adjacency_Matrix
Enter the number of vertices:
4
Enter the number of edges:
6
Enter the edges: <to> <from>
1 1
3 4
2 3
1 4
2 4
1 2
The adjacency matrix for the given graph is:
  1 2 3 4
1 1 1 0 1
2 0 0 1 1
3 0 0 0 1
4 0 0 0 0