建立交集图的线性时间复杂度算法

Question

如果您能帮助确定线性时间复杂度算法以构建有限元素集 U 的一组子集的交集图，我们将不胜感激。

例如，令 U = {a,b,c,d,e,f,g,h}。考虑 U 的集合 S = {{{a,b}, {c,d}, {a,e,h}, {e,f,g} }。我们需要在线性中构建 S 的交集图 G时间，如果可能的话。 S中的每个元素都是G的一个节点。G中的两个节点N1和N2之间有一条边当且仅当N1和N2至少有一个共同元素。

例如上面S的交集图G有四个节点，即{a,b}, {c,d}, {a,e,h}, {e,f,g} . G 将具有 G 的 2 条边，即 {a,b}-{a,e,h} 和 {a,e,h}-{e,f,g}。

是否有一种线性算法可以根据有限元素集的一组子集构建相交图？

Answer 1

我可以在 O(E * M) 中完成，其中 E 是结果图中的边数，M 是具有共同的元素。

当然可以。首先，我将为 S 的元素指定一个任意顺序，并按该顺序按索引为 S 的元素命名。我还对 U 的元素进行了任意排序，并按该顺序按其索引命名每个元素。

这完全是一种奇特的说法 "I can now say I want the 4rd element in U and the 2nd element in S"，而且这样做的时间复杂度为 O(1)。

我创建了以下数据结构：

table: 1...|U| -> list of numbers in range 1...|S|

现在我遍历 S 中的所有元素 N，因此 N 我遍历 N 中的所有 u，然后我看table[u] 中的节点列表，并在 N 和 table[u] 中的所有节点之间添加一条图边。最后将当前的N添加到table[u]

伪代码：

for N1 in S:
  for u in N1:
    for N2 in table[u]:
      Create edge N1-N2
    add N1 to table[u]

建立交集图的线性时间复杂度算法

Linear time complexity algorithm for building the intersection graph

algorithm

data-structures

set

intersection