邻接表和邻接矩阵怎么互相转化

邻接表和邻接矩阵是两种常用的图表示方法，它们可以互相转化。下面是它们之间的转化方法：

1. 邻接表转邻接矩阵：
- 创建一个空的邻接矩阵，大小为图中顶点的个数。
- 遍历邻接表中的每个顶点，对于每个顶点，遍历其对应的邻接链表，将邻接顶点在邻接矩阵中的位置标记为1。
- 如果图是有向图，则只标记出边；如果图是无向图，则标记出边和入边。
- 邻接矩阵中未标记的位置表示两个顶点之间没有边。
- 返回生成的邻接矩阵。

2. 邻接矩阵转邻接表：
- 创建一个空的邻接表，大小为图中顶点的个数。
- 遍历邻接矩阵中的每个顶点，对于每个顶点，遍历其对应的邻接矩阵行，找到值为1的列，将该列对应的顶点添加到邻接表中的对应顶点的邻接链表中。
- 如果图是有向图，则只添加出边；如果图是无向图，则添加出边和入边。
- 返回生成的邻接表。

下面是一个示例代码，演示了邻接表和邻接矩阵的转化过程：

# 邻接表转邻接矩阵
def adjacency_list_to_matrix(adj_list):
    num_vertices = len(adj_list)
    adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
    for i in range(num_vertices):
        for j in adj_list[i]:
            adj_matrix[i][j] = 1
    return adj_matrix

# 邻接矩阵转邻接表
def adjacency_matrix_to_list(adj_matrix):
    num_vertices = len(adj_matrix)
    adj_list = [[] for _ in range(num_vertices)]
    for i in range(num_vertices):
        for j in range(num_vertices):
            if adj_matrix[i][j] == 1:
                adj_list[i].append(j)
    return adj_list

# 示例邻接表
adj_list = [[1, 2], [0, 2], [0, 1, 3], [2]]
# 邻接表转邻接矩阵
adj_matrix = adjacency_list_to_matrix(adj_list)
print(adj_matrix)
# 邻接矩阵转邻接表
adj_list_new = adjacency_matrix_to_list(adj_matrix)
print(adj_list_new)