¿Cómo reducir la complejidad del tiempo?

Question

tengo un grafico G=(V+E) y lista de lista Node donde cada sublista es un subconjunto de V.Quiero encontrar los nodos de cada sublista a los que no se puede acceder desde otros nodos de esa sublista y agregar una ventaja entre esos nodos.Suponer,Node=[[1,2,3,4,5,7,8],[9,10],....] y en sublista=[1,2,3,4,5,7,8], { 1,7,3,8} accesibles entre sí y {2,4,5} accesibles entre sí, por lo que es necesario agregar un borde entre 1/7/3/8 y 2/4/5.He usado lo siguiente:

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

la complejidad de node_induced_subgraph() es O(V+E) complejidad de connected_components() es O(m+n) # m es no.de nodos y n es no.de aristas en el subgrafo

Entonces, ¿cómo reducir la complejidad general?

Answer 1

Voy a abordar tu pregunta en dos partes.Primero, cómo garantizar la accesibilidad entre nodos en una "sublista" agregando una cantidad mínima de bordes (si puede agregar tantos bordes como desee, puede revisar la lista y conectar un elemento con sus dos elementos vecinos: costear $O(n)$ operaciones de suma de bordes, que en teoría es el método más rápido...).Si queremos agregar la menor cantidad de bordes posible, solo queremos conectar los "componentes conectados".Supongo que tu grafica $g$ se almacena como una lista de adyacencia.

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

Ahora este algo tiene un tiempo de ejecución de $O(n+|E|)$ dónde $n$ es la longitud de list.Bueno, para ser honesto, es lo mismo que tu algoritmo. Solo quiero resaltar que el uso de matrices bool es muy deseable en general;Además, no sé cómo funciona su método de "subgrafo inducido", pero debe evitar crear un nuevo gráfico.

Ahora una idea que podría ser nueva:Puedes reducir el número de sublistas conectando aquellas que tengan un elemento superpuesto.(Por supuesto, esto solo es útil si no son necesariamente distintos). Puede utilizar un unión-encontrar-estructura para eso:

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)

Ahora 'new_sublists' solo contiene la cantidad necesaria de sublistas (también se eliminan todas las sublistas de tamaño 1).El procedimiento toma $O(max(|V|,N\cdot\alpha (|V|)))$ dónde $N=\sum_i ext{|sublistas[i]|}$. $\alfa(|V|)$ Básicamente se puede tratar como una constante, pero puedes leer sobre el unión-encontrar-estructura artículo.Si está trabajando con muchas listas de nodos superpuestas, este algoritmo debe ejecutarse primero.