邻接矩阵和邻接表的画法

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

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

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

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

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

相关问题

邻接矩阵转化为邻接表

将邻接矩阵转化为邻接表可以通过遍历邻接矩阵中每个元素来实现。

具体步骤如下：

1. 创建一个空的邻接表。
2. 遍历邻接矩阵中的每个元素，如果该元素的值为1，则表示有一条边，根据该边的起点和终点，在邻接表中添加相应的边和节点。
3. 对于无向图，需要在邻接表中同时添加起点和终点的边，因为邻接矩阵是对称的。
4. 完成所有元素的遍历后，邻接表就构建完成了。

下面是一个示例代码，将邻接矩阵转化为邻接表：

def adjacency_matrix_to_list(adj_matrix):
    adj_list = {}
    for i in range(len(adj_matrix)):
        adj_list[i] = []
        for j in range(len(adj_matrix[i])):
            if adj_matrix[i][j] == 1:
                adj_list[i].append(j)
                adj_list[j].append(i)   # 无向图需要同时添加起点和终点的边
    return adj_list

其中，adj_matrix 是邻接矩阵，adj_list 是转化后的邻接表，返回值即为 adj_list。

邻接矩阵和邻接表详细介绍

邻接矩阵和邻接表是两种常见的图的存储方式。它们之间的转化可以通过以下步骤实现：

1. 邻接矩阵转邻接表：对于邻接矩阵中的每个非零元素，将其对应的行和列分别作为起点和终点，构建一个边的链表。如果邻接矩阵中的元素为0，则不需要构建边。

2. 邻接表转邻接矩阵：首先需要确定图的节点数n，然后创建一个n*n的矩阵，并将所有元素初始化为0。对于每个节点i，遍历其邻接表中的所有边，将对应的矩阵元素设为1。

通过以上步骤，就可以实现邻接矩阵和邻接表的相互转化。