如何快速找到连接到二部图子集的所有节点？

Question

给定一组左节点和右节点，以及它们之间的边（二分图），我需要支持从左节点集到连接到左侧任何内容的右节点子集的快速查找。

如果图形非常稀疏或密集，这很容易。下面是一个示例邻接表实现，它将支持connected_endpoints()稀疏图上的快速调用。O(len(input) * len(result))然而，对于中等数量的连接，尽管涉及的数据大小表明可能存在解决方案，但中间计算看起来像是这样O(len(input) + len(result))。

是否存在一种数据结构可以相对快速地支持这 3 个操作（或类似的操作）——添加/删除可能为 O(1)，连接边搜索为 O(in+out)，给出或采用多对数因子？

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):
        """Desired: Amortized O(1)"""
        self.edges[start].add(end)
    
    def unset_edge(self, start: A, end: B):
        """Desired: Amortized 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]:
        """Desired: Amortized O(len(start) + len(<return>))"""
        empty = set()
        if not start:
            return empty
        return set.union(*(self.edges.get(node, empty) for node in start))

Answer 1

正如评论中正确指出的那样，与一组大小相关的边缘对象的len(input)潜在大小len(input) * len(B)意味着仅读取输入会导致最坏情况的复杂性len(input) * len(B)。

因此，没有可能的算法可以保证len(input) + len(result)复杂性。

然而，有多种方法可以通过将二分图表示为 2D 布尔矩阵来获得更快的算法，其中：

• 每行代表 A 中的一个节点
• 每列代表 B 中的一个节点
• 每个单元代表 A 节点和 B 节点之间的连接。

通过这种表示，您可以将行编码为位向量，使用这样的向量，您可以使用单个指令执行多个按位布尔或。（例如，在 64 位架构上，单个按位 OR 将导致 64 个子操作）。

您可以在这里找到更多问题解决方案：

https://cs.stackexchange.com/a/146616