Wie kann die Zeitkomplexität reduziert werden?

Question

Ich habe eine Grafik G=(V+E) und Liste der Liste Node wobei jede Unterliste eine Teilmenge von ist V.Ich möchte Knoten jeder Unterliste herausfinden, die von anderen Knoten dieser Unterliste aus nicht erreichbar sind, und eine Kante zwischen diesen Knoten hinzufügen.Vermuten,Node=[[1,2,3,4,5,7,8],[9,10],....] und in sublist=[1,2,3,4,5,7,8], { 1,7,3,8} voneinander erreichbar und {2,4,5} voneinander erreichbar, daher muss zwischen 1/7/3/8 und 2/4/5 eine Kante hinzugefügt werden.Ich habe Folgendes verwendet:

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

Die Komplexität von node_induced_subgraph () ist o (v+e) Komplexität von Connected_Components () ist o (m+n) # m ist Nr.von Knoten und n ist nein.der Kanten im Untergraphen

Wie lässt sich also die Gesamtkomplexität reduzieren?

Answer 1

Ich werde Ihre Frage in zwei Teilen beantworten.Erstens, wie man die Erreichbarkeit zwischen Knoten in einer „Unterliste“ durch Hinzufügen einer minimalen Anzahl von Kanten sicherstellt (wenn Sie so viele Kanten hinzufügen können, wie Sie möchten, können Sie die Liste durchgehen und ein Element mit seinen beiden benachbarten Elementen verbinden – Kostenberechnung). $O(n)$ Kantenadditionsoperationen, was theoretisch die schnellste Methode ist...).Wenn wir so wenige Kanten wie möglich hinzufügen möchten, möchten wir nur die „verbundenen Komponenten“ verbinden.Ich nehme deine Grafik an $G$ wird als Adjazenzliste gespeichert.

//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

Jetzt hat dieser Algorithmus eine Laufzeit von $O(n+|E|)$ Wo $n$ ist die Länge von list.Um ehrlich zu sein, ist es dasselbe wie Ihr Algorithmus. Ich möchte nur hervorheben, dass die Verwendung von Bool-Arrays im Allgemeinen sehr wünschenswert ist.Ich weiß auch nicht, wie Ihre Methode „Indcued Subgraph“ funktioniert – aber Sie sollten es vermeiden, einen neuen Graphen zu erstellen.

Nun eine Idee, die vielleicht neu ist:Sie können die Anzahl der Unterlisten reduzieren, indem Sie diejenigen verbinden, die ein überlappendes Element haben.(Natürlich ist dies nur nützlich, wenn sie nicht unbedingt unterschiedlich sind.) Sie können a verwenden Union-Find-Struktur dafür:

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)

Jetzt enthält „new_sublists“ nur noch die erforderliche Anzahl an Unterlisten (auch alle Unterlisten der Größe 1 werden entfernt).Das Verfahren dauert $O(max(|V|,N\cdot\alpha (|V|)))$ Wo $N=\sum_i ext{|sublists[i]|}$. $\alpha(|V|)$ kann grundsätzlich als Konstante behandelt werden, aber Sie können sich darüber informieren Union-Find-Struktur Artikel.Wenn Sie mit vielen überlappenden Knotenlisten arbeiten, sollte dieser Algorithmus zuerst ausgeführt werden.