كيفية تقليل التعقيد الزمني لهذا الرمز؟
-
29-09-2020 - |
سؤال
لدي رسم بياني 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])
المحلول
للحصول على الزمن التربيعي قم بما يلي:
يترك $M = N( ext{NODE})$ كن جيران NODE في $ج$.
إحصاء - عد $G' = (G - ext{NODE})^3$, ، ال الثاني الرسم البياني للقوة ل $ج$ بدون القمم من NODE.
ثم تقوم بما يلي:لكل رأسين $ش$ و $v$ في $م$, ، لو $uv otin E(G')$, ، يضيف $الأشعة فوق البنفسجية$ ل $ج$.
بهذه الطريقة لن تضطر إلى الحساب shortest_path
أي أكثر من ذلك.
لا تنتمي إلى cs.stackexchange