存储图（邻接矩阵）

要存储图形，有两种常见方法：

• 邻接矩阵
• 邻接名单

邻接矩阵是用于表示一个有限图的正方形矩阵。矩阵的元素指示图中的顶点对是否相邻。

相邻意味着’毗邻或毗邻其他东西’或旁边的东西。例如，你的邻居与你相邻。在图论中，如果我们可以从节点 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