如何快速查找二分图中子集的关联节点？求高效操作的数据结构

问题背景 #

给定二分图（由左节点集、右节点集及边构成），需支持从左节点子集快速查询与之相连的所有右节点子集。现有稀疏图的邻接表实现（如下方代码），但在中等连通性场景下，connected_endpoints的实际复杂度接近O(len(input) * len(result))——当多个左节点共享大量右节点时，会重复遍历这些共享节点。我们需要一种数据结构，能高效支持：

• 增边：均摊O(1)
• 删边：均摊O(1)
• 关联节点查询：O(len(start) + len(返回值))（允许带多对数因子）

现有实现分析 #

以下是原稀疏图邻接表实现：

from typing import *
from collections import defaultdict

A = TypeVar('A')
B = TypeVar('B')

class Graph(Generic[A, B]):
    def __init__(self):
        self.edges = defaultdict(set)
    
    def set_edge(self, start: A, end: B):
        """期望：均摊O(1)"""
        self.edges[start].add(end)
    
    def unset_edge(self, start: A, end: B):
        """期望：均摊O(1)"""
        s = self.edges[start]
        s.discard(end)
        if not s:
            self.edges.pop(start, None)

    def connected_endpoints(self, start: Set[A]) -> Set[B]:
        """期望：均摊O(len(start) + len(<返回值>))"""
        empty = set()
        if not start:
            return empty
        return set.union(*(self.edges.get(node, empty) for node in start))

该实现的问题在于：set.union会遍历每个左节点的全部邻接右节点，即使这些右节点已经被其他左节点包含。例如，若1000个左节点都连接到同一个右节点，该右节点会被遍历1000次，导致查询复杂度冗余。

优化方案：双向邻接表+标记追踪 #

通过维护双向邻接表，结合一次性标记机制，可以将查询复杂度优化到O(len(start) + len(返回值))，同时保持增删边的均摊O(1)复杂度。

实现思路 #

1. 维护两个邻接表：
   • left_to_right：左节点到右节点的映射（与原实现一致）
   • right_to_left：右节点到左节点的映射（支持反向追踪）
2. 新增标记组件：
   • marker：递增整数，每次查询使用唯一标识，避免重复标记
   • node_markers：记录每个右节点最近被标记的查询标识

代码实现 #

from typing import *
from collections import defaultdict

A = TypeVar('A')
B = TypeVar('B')

class OptimizedGraph(Generic[A, B]):
    def __init__(self):
        self.left_to_right = defaultdict(set)
        self.right_to_left = defaultdict(set)
        self.marker = 0
        self.node_markers = dict()  # 右节点到标记值的映射
    
    def set_edge(self, start: A, end: B):
        """增边：均摊O(1)"""
        self.left_to_right[start].add(end)
        self.right_to_left[end].add(start)
    
    def unset_edge(self, start: A, end: B):
        """删边：均摊O(1)"""
        # 更新左到右映射
        left_neighbors = self.left_to_right[start]
        left_neighbors.discard(end)
        if not left_neighbors:
            self.left_to_right.pop(start, None)
        
        # 更新右到左映射
        right_neighbors = self.right_to_left[end]
        right_neighbors.discard(start)
        if not right_neighbors:
            self.right_to_left.pop(end, None)
    
    def connected_endpoints(self, start: Set[A]) -> Set[B]:
        """查询：均摊O(len(start) + len(返回值))"""
        if not start:
            return set()
        
        self.marker += 1
        result = set()
        
        for node in start:
            for neighbor in self.left_to_right.get(node, set()):
                # 仅当该右节点未被当前查询标记时，加入结果并更新标记
                if self.node_markers.get(neighbor, -1) != self.marker:
                    self.node_markers[neighbor] = self.marker
                    result.add(neighbor)
        
        return result

复杂度分析 #

• 增边/删边：仅涉及两个哈希集合的增删操作，均摊复杂度为O(1)
• 查询：遍历输入的左节点（O(len(start))），每个右节点仅会被加入结果集一次（O(len(返回值))），即使被多个左节点关联也只会处理一次。总复杂度为O(len(start) + len(返回值))，完全符合需求。

额外说明 #

• 标记机制使用递增整数而非清空字典，避免了每次查询后清理标记的开销，进一步保证了效率
• 双向邻接表同时支持反向查询（从右节点子集查询左节点子集），只需稍作修改即可实现
• 若节点是可哈希的任意类型（如字符串、自定义对象），该实现均能正常工作

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