如何降低时间复杂度？

Question

我有一个图表 G=(V+E) 及名单一览表 Node 其中每个子列表是 V.我想找出每个子列表的节点，这些节点无法从该子列表的其他节点访问，并在这些节点之间添加边缘。假设,Node=[[1,2,3,4,5,7,8],[9,10],.... 在sublist=[1,2,3,4,5,7,8]中，{1,7,3,8}彼此可达，{2,4,5}彼此可达，因此需要在1/7/3/8和2/4/5之间添加边。我已经使用了以下内容 :

for each sublist in Node
 SG=node_induced_subgraph(sublist) of G
 C=connected_components(SG) 
 for each component c_i in C
  add edge between c_i and c_{i+1}
 end
end

node_induced_subgraph()的复杂度为O(V+E) connected_components()的复杂度为O(m+n)#m为否。节点和n是否。子图中的边

那么如何降低整体复杂度呢？

Answer 1

我将把你的问题分为两部分。首先，如何通过添加最少量的边来确保一个"子列表"中的节点之间的可达性（如果您可以根据需要添加尽可能多的边，则可以通过列表并将一个元素连接 缧O(n)缧 边相加运算，这在理论上是最快的方法。..).如果我们想添加尽可能少的边，我们只想连接"连接的组件"。我想你的图表 $G$ 被存储为邻接列表。

//reused arrays
visited := bool array of size |V| initialized to false
active  := bool array of size |V| initialized to false
//simple dfs
def dfs(node):
  if visited[node] or not active[node]: return
  visited[node] = true
  for child in neighbors(node):
    dfs(child)
//algo
def connect_node_list(list):
  for node in list: active[node] = true
  last := null
  for node in list:
    if not visited[node]: 
      dfs(node)
      if last != null: add_edge(last,node)
      last = node
  for node in list: 
    active[node]  = false
    visited[node] = false

现在这个算法有一个运行时 ＜O(n+|E/)＞ 哪里 $n$ 是长度的 list.好吧，说实话它和你的algo一样我只是想强调一下，bool数组的用法在一般情况下是非常可取的;另外我也不知道你的"indcued subgraph"方法是如何工作的-但是你应该避免构建一个新的图形。

现在一个可能是新的想法:您可以通过连接具有重叠元素的子列表来减少子列表的数量。（当然，这只有在它们不一定不同的情况下才有用。) 您可以使用一个 联合查找结构 为了那个:

uf := union find structure with |V| elements
for list in sublists:
  first = list[0]
  for node in list:
    uf.unify(first, node)
index := array of length |V|
counter := 0
for element in uf:
  index[element]  = -1
  if uf.parent(element) = element and uf.size(element) > 1:
      index[element] = counter
      counter++
new_sublists = list of <counter> many lists
for element in uf:
  set = uf.find(element)
  if index[set] != -1:
    new_sublists[index[set]].add(element)

现在new_sublists只包含必要数量的子列表（也删除所有大小为1的子列表）。该程序需要 $O(max(/V/,N\cdot\alpha(/V/)))$ 哪里 $N=\sum_i ext{/sublists[i]/}$. $\alpha(/V/|$ 基本上可以被视为一个常数，但你可以阅读 联合查找结构 文章。如果您正在处理许多重叠的节点列表，则应首先执行此算法。