邻接矩阵和领接表的区别

邻接矩阵和邻接表是两种常用的图的表示方法，它们有以下区别：

1. 存储方式：
- 邻接矩阵：使用二维数组来表示图的连接关系，其中数组的行和列分别代表图中的顶点，数组元素的值表示两个顶点之间的边的关系。
- 邻接表：使用链表或数组的方式来表示图的连接关系，其中每个顶点都对应一个链表或数组，链表或数组中存储了与该顶点相邻的顶点。

2. 空间复杂度：
- 邻接矩阵：需要使用二维数组来表示图的连接关系，因此空间复杂度为O(V^2)，其中V为顶点的数量。
- 邻接表：只需要存储与每个顶点相邻的顶点，因此空间复杂度为O(V+E)，其中E为边的数量。

3. 访问效率：
- 邻接矩阵：可以通过索引直接访问到两个顶点之间的边的关系，因此查找边的关系的时间复杂度为O(1)。
- 邻接表：需要遍历链表或数组来查找与某个顶点相邻的顶点，因此查找边的关系的时间复杂度为O(degree)，其中degree为顶点的度数。

4. 适用场景：
- 邻接矩阵：适用于稠密图，即边的数量接近于顶点数量的平方。
- 邻接表：适用于稀疏图，即边的数量远小于顶点数量的平方。

相关问题

python 实现将带权图图的领接矩阵转换成邻接表，和将邻接表转换成邻接矩阵

将带权图的领接矩阵转换成邻接表可以按照如下步骤进行：

1. 遍历领接矩阵，找到每个非零元素；
2. 对于每个非零元素，将其所在的行表示的节点与列表示的节点之间添加一条边；
3. 如果图是有向图，则只需将该边添加到起点的邻接表中；
4. 如果图是无向图，则需要将该边同时添加到起点和终点的邻接表中。

Python 代码实现如下：

def matrix_to_list(matrix):
    n = len(matrix)
    graph = {}
    for i in range(n):
        for j in range(n):
            if matrix[i][j] != 0:
                if i not in graph:
                    graph[i] = []
                graph[i].append((j, matrix[i][j]))
    return graph

将邻接表转换成邻接矩阵可以按照如下步骤进行：

1. 遍历邻接表，找到每个节点以及其邻居节点；
2. 对于每个节点及其邻居节点，将其在邻接矩阵中对应位置的值置为其边权值；
3. 注意区分有向图和无向图，无向图需要将对称的两个位置的值都置为边权值。

Python 代码实现如下：

def list_to_matrix(graph, directed=False):
    n = len(graph)
    matrix = [[0] * n for _ in range(n)]
    for node in graph:
        for neighbor, weight in graph[node]:
            matrix[node][neighbor] = weight
            if not directed:
                matrix[neighbor][node] = weight
    return matrix

注意，这里的邻接表使用字典来存储，字典的键表示节点，值为一个列表，其中每个元素是一个二元组，表示该节点与其邻居节点之间的边权值。

python 实现将图的领接矩阵转换成邻接表，和将邻接表转换成邻接矩阵 及测试用例

将图的邻接矩阵转换为邻接表可以使用以下 Python 代码实现：

def matrix_to_list(adj_matrix):
    adj_list = {}
    n = len(adj_matrix)
    for i in range(n):
        adj_list[i] = []
        for j in range(n):
            if adj_matrix[i][j] == 1:
                adj_list[i].append(j)
    return adj_list

# 示例测试用例
adj_matrix = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 1],
    [0, 1, 1, 0]
]
adj_list = matrix_to_list(adj_matrix)
print(adj_list)

将邻接表转换为邻接矩阵可以使用以下 Python 代码实现：

def list_to_matrix(adj_list):
    n = len(adj_list)
    adj_matrix = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in adj_list[i]:
            adj_matrix[i][j] = 1
    return adj_matrix

# 示例测试用例
adj_list = {
    0: [1],
    1: [0, 2, 3],
    2: [1, 3],
    3: [1, 2]
}
adj_matrix = list_to_matrix(adj_list)
print(adj_matrix)

测试用例的输出结果如下：

# matrix_to_list 的测试用例结果
{0: [1], 1: [0, 2, 3], 2: [1, 3], 3: [1, 2]}

# list_to_matrix 的测试用例结果
[[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]]