Come ridurre la complessità del tempo?

Question

Ho un grafico G=(V+E) ed elenco di elenco Node in cui ogni subblist è sottoinsieme di V.Voglio scoprire i nodi di ogni sublista che non sono raggiungibili da altri nodi di quel subblist e aggiungono un bordo tra quei nodi.Supponiamo, Node= [[1,2,3,4,5,7,8], [9,10], ....] e in sublist= [1,2,3,4,5,7,8], {1,7,3,8} raggiungibile l'uno dall'altro e {2,4,5} raggiungibili l'uno dall'altro, quindi un vantaggio deve essere aggiunto tra il 1/7/3/8 e il 2/4/5.Ho usato quanto segue:

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

.

Complessità di nodo_induced_subgraph () è o (V + E) La complessità del collegamento_components () è o (m + n) # m è no.dei nodi e n è no.di bordi nel sotto-grafico

Quindi come ridurre la complessità complessiva?

Answer 1

Avredo la tua domanda in due parti. Prima come garantire la raggiungibilità tra i nodi in un unico "sublista" con l'aggiunta di una quantità minima di bordi (se è possibile aggiungere quanti bordi come si desiderate potrai passare attraverso l'elenco e connettere un elemento ai suoi due elementi vicini - costare la classe $ o (n) $ Operazioni di aggiunta del bordo, che è teoricamente il metodo più veloce ...). Se vogliamo aggiungere il maggior numero possibile di bordi, vogliamo solo collegare i "componenti collegati". Suppongo il tuo grafico $ G $ è memorizzato come elenco di adiacenza.

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

.

Ora questo algo ha un runtime di $ o (n + | e |) $ dove $ N $ è la lunghezza del list. Bene ad essere onesti è lo stesso del tuo algo voglio solo sottolineare che l'utilizzo degli array di bool è molto desiderabile in generale; Inoltre non so come funziona il metodo "sottografo indicito" - ma dovresti evitare di costruire un nuovo grafico.

Ora un'idea che potrebbe essere nuova: È possibile ridurre il numero di sublisti collegando quelli che hanno un elemento sovrapposto. (Ovviamente questo è utile solo se non sono necessariamente distinti.) Puoi usare un Struttura sindacale-find per questo:

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)

.

Now'new_sublists 'solo contiene la quantità necessaria dei sublisti (anche tutti i sublisti delle dimensioni 1 vengono rimossi). La procedura prende $ o (max (max (| v |, n \ cdot \ alfa (| v |)))) $ dove $ N=sum_i \ testo {| neblists [i] |} $ . $ \ alfa (| v |) $ può fondamentalmente essere trattati come costante ma è possibile leggere su Struttura sindacale-trinciale Articolo. Se stai lavorando con molti elenchi di nodi sovrapposti, questo algo dovrebbe essere eseguito prima.