인접 행렬 애니메이션 시연 애니메이션으로 코드를 시각화하세요
邻接矩阵 是 N x N 大小的方阵，其中 N 是图中的节点数，用于表示图的边之间的连接。
无向图到邻接矩阵的图表示
邻接矩阵的特点是：
- 矩阵的大小由图中的顶点数决定。
- 图中的节点数量决定了矩阵的大小。
- 简单计算图中的边数。
- 如果图的边很少，则矩阵将是稀疏的。
如何构建邻接矩阵：
为图构建邻接矩阵非常容易和简单，您需要遵循下面给出的某些步骤：
- 创建一个 nxn 矩阵，其中 n 是图中的顶点数。
- 将所有元素初始化为 0。
- 对于图中的每条边 (u, v)，如果图是无向的，则将 a[u][v] 和 a[v][u] 标记为 1，如果边从 u 指向 v ， 则将 a [ u][v] 为 1。（如果图形已加权，则单元格将填充边权重）
邻接矩阵的应用：
- 图算法： 许多图算法（例如 Dijkstra 算法 、 Floyd-Warshall 算法 和 Kruskal 算法） 都使用邻接矩阵来表示图。
- 图像处理 ： 图像处理中使用邻接矩阵来表示图像中像素之间的邻接关系。
- 寻找两个节点之间的最短路径： 通过对邻接矩阵进行矩阵乘法，可以找到图中任意两个节点之间的最短路径。
使用邻接矩阵的优点：
- 邻接矩阵简单且易于理解。
- 在图表中添加或删除边既快速又简单。
- 它允许恒定时间访问图中的任何边。
使用邻接矩阵的缺点：
- 对于稀疏图来说，它的空间利用率很低，因为它占用了 O(N 2 ) 空间。
- 计算一个顶点的所有邻居需要 O(N) 时间。
你还能读什么？
- Kruskal 算法（邻接矩阵的简单实现）
- 将邻接矩阵转换为图的邻接列表表示
- 将邻接列表转换为图的邻接矩阵表示
- 图的邻接表与邻接矩阵表示的比较