comment réduire la complexité du temps?

Question

J'ai un graphique G=(V+E) et de liste de liste Node où chaque sous-liste est sous-ensemble de V.Je veux trouver les nœuds de chaque sous-liste qui ne sont pas accessibles à partir d'autres nœuds de cette sous-liste et ajouter de bord entre ces nœuds.Supposons que,Node=[[1,2,3,4,5,7,8],[9,10],....] et dans la sous-liste=[1,2,3,4,5,7,8], {1,7,3,8} accessibles les uns des autres et {2,4,5} accessibles les uns des autres de sorte qu'un bord doit être ajouté entre les 1/7/3/8 et 2/4/5.J'ai utilisé les suivants :

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 complexité de node_induced_subgraph() est O(V+E) la complexité de connected_components() est O(m+n) # m est non.de nœuds et n est pas.d'arêtes dans la Sous-graphe

Alors, comment réduire la complexité globale?

Answer 1

Je vais répondre à votre question en deux parties.D'abord comment s'assurer de l'accessibilité entre les nœuds dans un "sous-liste" avec l'ajout d'un montant minimal d'arêtes (si vous pouvez ajouter autant de bords comme vous le vouliez, vous pourriez aller par le biais de la liste et connect un élément à ses deux éléments voisins - le prix de revient $O(n)$ edge outre les opérations, ce qui est théoriquement la méthode la plus rapide...).Si nous voulons ajouter quelques bords que possible, nous voulons seulement de connecter les "composantes connexes".Je suppose que votre graphique $G$ est stockée sous forme de liste d'adjacence.

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

Maintenant, cet algo a un temps d'exécution de $O(n+|E|)$ où $n$ est la longueur de list.Eh bien, pour être honnête, c'est la même chose que ton algo, je veux juste mettre en évidence que l'utilisation de bool tableaux est très souhaitable en général;aussi, je ne sais pas comment votre "indcued sous-graphe de la" méthode fonctionne - mais vous devriez éviter de construire un nouveau graphe.

Maintenant, une idée qui pourrait être nouveau:vous pouvez réduire le nombre de sous-listes en reliant ceux qui ont un chevauchement de l'élément.(Bien sûr, ce n'est utile que si ils ne sont pas nécessairement distincts.) Vous pouvez utiliser un union-find-structure pour qui:

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)

Maintenant new_sublists contient uniquement la quantité nécessaire de sous-listes (aussi tous les sous-listes de taille 1 sont supprimés).La procédure prend $O(max(|V|,N\cdot\alpha (|V|)))$ où $N=\sum_i ext{|sous-listes[i]|}$. $\alpha(|V|)$ peut généralement être traitée comme une constante, mais vous pouvez lire sur le union-find-structure l'article.Si vous travaillez avec de nombreux chevauchements nœud listes cette algo doit être exécuté en premier.