كيفية تقليل تعقيد الوقت?

Question

لدي رسم بياني G=(V+E) وقائمة القائمة Node حيث تكون كل قائمة فرعية مجموعة فرعية من V.أريد معرفة عقد كل قائمة فرعية لا يمكن الوصول إليها من العقد الأخرى لتلك القائمة الفرعية وإضافة حافة بين تلك العقد.افترض,Node=[[1,2,3,4,5,7,8],[9,10],....] وفي القائمة الفرعية=[1 ، 2 ، 3 ، 4 ، 5 ، 7 ، 8] ، {1 ، 7 ، 3 ، 8} يمكن الوصول إليها من بعضها البعض و {2 ، 4 ، 5} يمكن الوصول إليها من بعضها البعض ، لذا يجب إضافة حافة بين 1/7/3/8 و 2/4/5.لقد استخدمت ما يلي :

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

تعقيد العقدة_مستخرجة_سوبغراف () هو س (الخامس + ه) تعقيد المكونات المتصلة () هو س (م + ن) # م لا.من العقد ون لا.من الحواف في الرسم البياني الفرعي

فكيف للحد من التعقيد الكلي?

Answer 1

أنا ستعمل معالجة سؤالك في جزأين.أولا كيفية ضمان إمكانية الوصول بين العقد في "قائمة فرعية" واحدة مع إضافة الحد الأدنى من الحواف (إذا كان بإمكانك إضافة أكبر عدد ممكن من الحواف كما تريد ، يمكنك الانتقال إلى القائمة وربط عنصر واحد بعنصرين متجاورين-التكلفة O س (ن)$ عمليات إضافة الحافة ، وهي نظريا أسرع طريقة...).إذا أردنا إضافة أقل عدد ممكن من الحواف ، فنحن نريد فقط توصيل "المكونات المتصلة".أفترض الرسم البياني الخاص بك $G$ يتم تخزينها كقائمة المجاورة.

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

الآن هذا ألغو لديه وقت التشغيل من O س (ن + / ه/)) أين $n$ هو طول list.حسنا أن نكون صادقين انها نفس ألغو الخاص بك أريد فقط أن أسلط الضوء على أن استخدام صفائف منطقية أمر مرغوب فيه جدا بشكل عام;كما أنني لا أعرف كيف تعمل طريقة "الرسم البياني الفرعي" - ولكن يجب تجنب إنشاء رسم بياني جديد.

الآن فكرة قد تكون جديدة:يمكنك تقليل عدد القوائم الفرعية عن طريق ربط تلك التي تحتوي على عنصر متداخل.(بالطبع هذا مفيد فقط إذا لم تكن متميزة بالضرورة.) يمكنك استخدام الاتحاد-البحث-هيكل من أجل ذلك:

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)

الآن تحتوي القوائم الجديدة فقط على الكمية الضرورية من القوائم الفرعية (تتم أيضا إزالة جميع القوائم الفرعية بالحجم 1).يأخذ الإجراء O س (ماكس (/الخامس| ، ن\كدوت \ ألفا (|الخامس|)))$ أين N ن = \مجموع ط \ نص {/القوائم الفرعية [أنا]/}$. alpha \ ألفا(|الخامس|) alpha يمكن أساسا أن تعامل على أنها ثابتة ولكن يمكنك أن تقرأ على الاتحاد-البحث-هيكل المادة.إذا كنت تعمل مع العديد من قوائم عقدة متداخلة يجب تنفيذ هذا ألغو أولا.