時間の複雑さを軽減するにはどうすればよいでしょうか?

Question

グラフがあります G=(V+E) そしてリストのリスト Node ここで、各サブリストは次のサブセットです V. 。各サブリストの他のノードから到達できないノードを見つけて、それらのノード間にエッジを追加したいと考えています。仮定する、Node=[[1,2,3,4,5,7,8],[9,10],....] およびサブリスト内 =[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_して誘導_subgraph（）の複雑さはo（v+e）connected_components（）の複雑さですo（m+n）＃mはno。ノードの数であり、n はいいえです。サブグラフのエッジの数

では、全体の複雑さを軽減するにはどうすればよいでしょうか?

Answer 1

あなたの質問に 2 つの部分に分けてお答えします。まず、最小限のエッジを追加して 1 つの「サブリスト」内のノード間の到達可能性を確保する方法 (必要な数のエッジを追加できる場合は、リストを調べて 1 つの要素をその 2 つの隣接する要素に接続できます - コスト計算) $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。正直に言うと、それはあなたのアルゴリズムと同じです。一般にブール配列の使用が非常に望ましいことを強調したいだけです。また、「誘導サブグラフ」メソッドがどのように機能するかわかりませんが、新しいグラフの構築は避けるべきです。

さて、新しいかもしれないアイデア:重複する要素を持つサブリストを接続することで、サブリストの数を減らすことができます。(もちろん、これは必ずしも別個ではない場合にのみ役立ちます。 あなたは、 共用体検索構造 そのために:

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{|サブリスト[i]|}$. $\アルファ(|V|)$ 基本的には定数として扱うことができますが、 共用体検索構造 記事。多くの重複するノード リストを操作している場合は、このアルゴを最初に実行する必要があります。