图解邻接矩阵：概念、实现与应用

图解邻接矩阵：概念、实现与应用

引用

CSDN

1.

https://blog.csdn.net/zsx0728/article/details/114633962

邻接矩阵是图论中一种重要的表示方法，它将图的顶点和边关系以矩阵形式展现出来。本文将详细介绍邻接矩阵的概念、表示方法、优缺点，并通过C语言代码示例帮助读者更好地理解其应用。

邻接矩阵表示法

邻接矩阵是将图G={V，E}表示为布尔矩阵的一种方法。矩阵的大小是 VxV，其中 V 是图的顶点数，根据顶点 i 到顶点 j 是否有边，条目 Aij 的值为1或0。

邻接矩阵示例

下图显示了一个图形及其等效的邻接矩阵。

对于无向图，由于每一条边（i，j）的存在，矩阵关于对角线对称，因此也有一条边（j，i）。

邻接矩阵的优点

• 添加边、删除边以及检查从顶点 i 到顶点 j 是否有边等基本操作都是非常省时的常规操作。
• 如果图是密集的，且边的数目较大，则邻接矩阵是首选。即使图和邻接矩阵是稀疏的，我们也可以用稀疏矩阵的数据结构来表示它。
• 图的最大的优势来自于矩阵的使用。硬件的最新发展使我们能够在GPU上执行代价很大的矩阵运算。
• 通过对邻接矩阵进行运算，我们可以深入了解图的性质及其顶点之间的关系。

邻接矩阵的缺点

• 邻接矩阵的 VxV 空间要求使它占用很多内存。自然的图通常没有太多连接，这就是为什么邻接列表是大多数任务的更好选择的主要原因。
• 虽然基本操作很简单，但在使用邻接矩阵表示时，像增加边和删除边这样的操作代价很大。

C语言示例

如果您知道如何创建二维数组，那么您也知道如何创建邻接矩阵。

// Adjacency Matrix representation in C
#include <stdio.h>
#define V 4
// Initialize the matrix to zero
void init(int arr[][V]) {
  int i, j;
  for (i = 0; i < V; i++)
    for (j = 0; j < V; j++)
      arr[i][j] = 0;
}
// Add edges
void addEdge(int arr[][V], int i, int j) {
  arr[i][j] = 1;
  arr[j][i] = 1;
}
// Print the matrix
void printAdjMatrix(int arr[][V]) {
  int i, j;
  for (i = 0; i < V; i++) {
    printf("%d: ", i);
    for (j = 0; j < V; j++) {
      printf("%d ", arr[i][j]);
    }
    printf("\n");
  }
}
int main() {
  int adjMatrix[V][V];
  init(adjMatrix);
  addEdge(adjMatrix, 0, 1);
  addEdge(adjMatrix, 0, 2);
  addEdge(adjMatrix, 1, 2);
  addEdge(adjMatrix, 2, 0);
  addEdge(adjMatrix, 2, 3);
  printAdjMatrix(adjMatrix);
  return 0;
}

邻接矩阵应用

• 在网络中创建路由表
• 导航任务