كيفية تقليل التعقيد الزمني لهذا الرمز؟

Question

لدي رسم بياني G=(V,E).قائمة العقد NODE فرعية V.أريد معرفة جميع العقد المجاورة لكل عقدة فيها NODE وأضف الحافة إذا كانت مسافة هؤلاء الجيران أكبر من 2.هل يمكن لأي شخص هنا أن يساعدني في تقليل التعقيد الزمني لهذا الرمز إلى وقت تربيعي أو أقل.

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

للحصول على الزمن التربيعي قم بما يلي:

يترك $M = N( ext{NODE})$ كن جيران NODE في $ج$.

إحصاء - عد $G' = (G - ext{NODE})^3$, ، ال الثاني الرسم البياني للقوة ل $ج$ بدون القمم من NODE.

ثم تقوم بما يلي:لكل رأسين $ش$ و $v$ في $م$, ، لو $uv otin E(G')$, ، يضيف $الأشعة فوق البنفسجية$ ل $ج$.

بهذه الطريقة لن تضطر إلى الحساب shortest_path أي أكثر من ذلك.