邻接矩阵和邻接表的画法

邻接矩阵和邻接表是图论中常用的两种表示图的数据结构。

1. **邻接矩阵**：它是一个二维数组，其中行代表起点，列表示终点。如果两个顶点之间有边相连，对应的矩阵元素值通常是1（无向图）或0/1（带权重）。对于每个顶点i，它的列索引就是连接到的其他所有顶点，使得A[i][j]=1。例如，如果A[i][j] = 1，表示顶点i与j直接相连。

- 矩阵形式直观易懂，查找两点间是否有边的时间复杂度为O(1)。
- 但空间效率不高，当图非常稀疏（即边数远小于顶点数的平方）时，会浪费大量存储空间。

2. **邻接表**：它是一个链表的集合，每个顶点对应一个链表，链表中的节点包含了与该顶点相邻的所有其他顶点。这种数据结构通常包含一个额外的哈希表或数组来快速查找特定顶点的邻接顶点。

- 当图是稠密的（边数接近于顶点数的平方），邻接表更节省空间。
- 查找任意两点间的边需要遍历链表，时间复杂度为O(deg(v))，deg(v)是目标顶点的度数。

相关问题

图的邻接矩阵和邻接表

图是一种非线性数据结构，邻接矩阵和邻接表是两种表示图的方式。

邻接矩阵是用一个二维数组来表示图的。对于无向图而言，邻接矩阵是对称的，而对于有向图而言则不一定对称。如果图中有n个节点，那么邻接矩阵就是一个n * n的矩阵。如果节点i到节点j之间有边，则邻接矩阵中第i行第j列的元素为1，否则为0。对于带权图而言，邻接矩阵中的元素可以表示边的权值。

邻接表则是由一组链表来表示图的。对于图中的每个节点，邻接表中都有一个对应的链表，链表中存储该节点所连的所有边的信息。对于无向图而言，邻接表中的每条边都会在两个节点对应的链表中出现。因为邻接表只存储实际存在的边，所以它通常比邻接矩阵更省空间。

邻接矩阵和邻接表问题

邻接矩阵和邻接表是两种表示图的方式。

邻接矩阵是一个二维数组，用于表示图中节点之间的关系。具体来说，如果节点i和节点j之间有一条边，则邻接矩阵中第i行第j列的值为1，否则为0。如果是有权图，邻接矩阵中存储的是边的权值。

邻接表则是一种更加节省空间的表示方式，它使用链表存储每个节点的邻居节点。对于每个节点i，邻接表中存储的是与节点i相连的所有节点。如果是有权图，邻接表中存储的是边的权值。

邻接矩阵的优点是可以快速地判断任意两个节点之间是否有边相连，时间复杂度为O(1)。但是如果图比较稀疏（即节点之间的边比较少），那么邻接矩阵会浪费很多空间。

邻接表的优点是可以节省空间，因为它只存储与每个节点相连的节点，而不存储不存在的边。但是如果要判断任意两个节点之间是否有边相连，需要遍历链表，时间复杂度为O(k)，其中k是与节点i相连的节点数。所以在稠密图中，邻接矩阵比邻接表更加高效；在稀疏图中，邻接表比邻接矩阵更加高效。