无向图中通过顶点查找对应边的实现方法 [C++ BGL]

你当前使用的全边遍历方案时间复杂度为O(E)（E为总边数），在边数较多的场景下效率确实偏低，可根据你的业务场景选择以下更优的实现方案：

方案1：邻接表哈希映射（最通用） #

• 核心思路：为每个顶点维护一个哈希字典，键为相邻顶点，值为对应的边对象/边ID，无向图加边时两个方向的邻接字典都要写入对应关系
• 复杂度：存储复杂度O(E)，查询时取两个顶点中度数更小的顶点查其邻接字典，平均时间复杂度为O(1)
• 参考实现（Python）：

from collections import defaultdict

# 邻接表初始化
adj = defaultdict(dict)

# 新增边
def add_edge(u, v, edge):
    adj[u][v] = edge
    adj[v][u] = edge

# 查询边
def get_edge(u, v):
    # 优先查度数更小的顶点的邻接表，降低哈希冲突概率（可选优化）
    if len(adj[u]) > len(adj[v]):
        u, v = v, u
    return adj[u].get(v, None)

• 适用场景：图结构增删频繁、查询次数多，同时需要做邻接遍历的通用场景

方案2：排序顶点对全局哈希映射 #

• 核心思路：对任意两个顶点u、v，先排序生成固定格式的键(min(u,v), max(u,v))，用全局哈希表存储键和边的对应关系
• 复杂度：存储复杂度O(E)，查询平均时间复杂度O(1)，空间占用比邻接表方案少一半
• 参考实现（Python）：

edge_map = {}

# 新增边
def add_edge(u, v, edge):
    key = tuple(sorted((u, v)))
    edge_map[key] = edge

# 查询边
def get_edge(u, v):
    key = tuple(sorted((u, v)))
    return edge_map.get(key, None)

• 适用场景：顶点ID为可排序类型（整数、字符串等），仅需要查询两点间边、不需要做邻接遍历的场景

方案3：邻接矩阵（仅适用于小顶点稠密图） #

• 核心思路：用二维数组存储边，matrix[u][v]直接对应u、v之间的边
• 复杂度：查询时间复杂度O(1)，但空间复杂度为O(V²)（V为顶点数），顶点数超过1000时空间占用会急剧升高
• 适用场景：顶点数量少（通常小于1000）、边密度高的图，比如小型完全图

如果使用的顶点是不可哈希的复杂对象，可以先为每个顶点分配唯一的整数ID，再套用上述方案即可。

内容的提问来源于stack exchange，提问作者eddy