Wie kann die zeitliche Komplexität dieses Codes reduziert werden?

Question

Ich habe eine Grafik G=(V,E).Eine Liste von Knoten NODE Teilmenge von V.Ich möchte alle Nachbarknoten jedes Knotens herausfinden NODE und Kante hinzufügen, wenn diese Nachbarn einen Abstand von mehr als 2 haben.Kann mir hier bitte jemand helfen, die zeitliche Komplexität dieses Codes auf quadratische Zeit oder weniger zu reduzieren?

import networkx as nx
import random

G = nx.erdos_renyi_graph(30, 0.05)

node=[]
for j in range(5): 
        node.append(random.randint(1,30))

for i in node:
    lst=list(G.neighbors(i))
    if(len(lst)>1):
         for j in range(len(lst)):
             for k in range(j+1,len(lst)):
                 if(len(nx.shortest_path(G,lst[j],lst[k]))>2):
                     G.add_edge(lst[j],lst[k])

Answer 1

Um die quadratische Zeit zu erhalten, gehen Sie wie folgt vor:

Lassen $M = N( ext{NODE})$ Seien Sie die Nachbarn von NODE in $G$.

Berechnen $G' = (G - ext{NODE})^3$, Die 2 Leistungsdiagramm von $G$ ohne die Eckpunkte von NODE.

Dann machen Sie Folgendes:Für jeweils zwei Eckpunkte $u$ Und $v$ In $M$, Wenn $uv otin E(G')$, hinzufügen $uv$ Zu $G$.

Auf diese Weise müssen Sie nicht rechnen shortest_path mehr.