Come ridurre la complessità del tempo?
-
29-09-2020 - |
Domanda
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?
Soluzione
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.