规范化邻接列表_从邻接列表创建邻接矩阵_如何反转邻接列表？ - 腾讯云开发者社区

规范化邻接列表

基础概念

规范化邻接列表（Normalized Adjacency List）是一种用于表示图数据结构的方法。在这种表示法中，每个节点都有一个与之关联的列表，该列表包含了所有与该节点直接相连的其他节点以及相应的边权重（如果有的话）。规范化邻接列表通常用于图的存储和遍历操作。

类型

规范化邻接列表通常有两种形式：

无向图的规范化邻接列表：每个节点的邻接列表包含与其相连的所有节点，且边是双向的。
有向图的规范化邻接列表：每个节点的邻接列表包含指向它的所有节点（入边）和它指向的所有节点（出边）。

应用场景

规范化邻接列表广泛应用于各种需要表示图结构的场景，如社交网络分析、路由算法、推荐系统等。

遇到的问题及解决方法

问题：如何构建规范化邻接列表？

解决方法：

对于无向图，可以按照以下步骤构建规范化邻接列表：

初始化一个空的字典（或其他适当的数据结构）来存储节点及其邻接列表。
遍历图中的每一条边，将边的两个端点添加到对方的邻接列表中。

示例代码（Python）：

def build_normalized_adjacency_list(edges):
    adjacency_list = {}
    for u, v in edges:
        if u not in adjacency_list:
            adjacency_list[u] = []
        if v not in adjacency_list:
            adjacency_list[v] = []
        adjacency_list[u].append(v)
        adjacency_list[v].append(u)
    return adjacency_list

# 示例边集合
edges = [(1, 2), (2, 3), (3, 4), (4, 1)]
adj_list = build_normalized_adjacency_list(edges)
print(adj_list)

输出：

{1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [3, 1]}

对于有向图，只需稍作修改，将边的方向考虑在内：

def build_normalized_adjacency_list_directed(edges):
    adjacency_list = {}
    for u, v in edges:
        if u not in adjacency_list:
            adjacency_list[u] = {'out': [], 'in': []}
        if v not in adjacency_list:
            adjacency_list[v] = {'out': [], 'in': []}
        adjacency_list[u]['out'].append(v)
        adjacency_list[v]['in'].append(u)
    return adjacency_list

# 示例边集合
edges = [(1, 2), (2, 3), (3, 4), (4, 1)]
adj_list_directed = build_normalized_adjacency_list_directed(edges)
print(adj_list_directed)

输出：

{1: {'out': [2], 'in': [4]}, 2: {'out': [3], 'in': [1]}, 3: {'out': [4], 'in': [2]}, 4: {'out': [1], 'in': [3]}}

参考链接

页面内容是否对你有帮助？

有帮助

没帮助

规范化邻接列表

基础概念

相关优势

类型

应用场景

遇到的问题及解决方法

问题：如何构建规范化邻接列表？

参考链接

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐