وقت تشغيل الحد الأدنى من الشجرة الممتدة؟(الطريقة الأولية)

Question

لقد كتبت رمزًا يحل مشكلة MST باستخدام طريقة Prim.قرأت أن هذا النوع من التنفيذ (باستخدام قائمة انتظار الأولوية) يجب أن يحتوي على O(E + VlogV) = O(VlogV) حيث E هو عدد الحواف وعدد V من الحواف ولكن عندما أنظر إلى الكود الخاص بي فإنه ببساطة لا يبدو بهذه الطريقة، سأكون ممتنًا لو تمكن شخص ما من توضيح هذا الأمر لي.

بالنسبة لي يبدو أن وقت التشغيل هو هذا:

تستغرق حلقة while أوقات O (E) (حتى نمر عبر جميع الحواف) داخل هذه الحلقة نستخرج عنصرا من Q يستغرق وقت O (logE).وتستغرق الحلقة الداخلية الثانية وقت O (V) (على الرغم من أننا لا نقوم بتشغيل هذه الحلقة في كل مرة من الواضح أنه سيتم تشغيله V مرات حيث يتعين علينا إضافة جميع الرؤوس )

استنتاجي هو أن وقت التشغيل هو:O( E(logE+V) ) = O( E*V ).

هذا هو الكود الخاص بي:

#define p_int pair < int, int >

int N, M; //N - nmb of vertices, M - nmb of edges
int graph[100][100] = { 0 }; //adj. matrix
bool in_tree[100] = { false }; //if a node if in the mst
priority_queue< p_int, vector < p_int >, greater < p_int > > Q; 
/*
keeps track of what is the smallest edge connecting a node in the mst tree and
a node outside the tree. First part of pair is the weight of the edge and the 
second is the node. We dont remember the parent node beaceuse we dont need it :-)
*/

int mst_prim()
{
 Q.push( make_pair( 0, 0 ) );

 int nconnected = 0;
 int mst_cost = 0;
 while( nconnected < N )
 {
      p_int node = Q.top(); Q.pop();

      if( in_tree[ node.second ] == false )
      {
           mst_cost += node.first;
           in_tree[ node.second ] = true;

           for( int i = 0; i < N; ++i )
                if( graph[ node.second ][i] > 0 && in_tree[i]== false )
                     Q.push( make_pair( graph[ node.second ][i], i ) );

           nconnected++;
      }
 }

 return mst_cost;
}

Answer 1

يمكنك استخدام قوائم المجاورة لتسريع الحل الخاص بك (ولكن ليس للرسوم البيانية الكثيفة)، ولكن حتى ذلك الحين، لن تحصل على O(V log V) بدون كومة فيبوناتشي.

ربما خوارزمية كروسكال سيكون من الأسهل عليك أن تفهم.لا يحتوي على قائمة انتظار ذات أولوية، ما عليك سوى فرز مجموعة من الحواف مرة واحدة.وغني عن هذا في الأساس:

• أدخل جميع الحواف في مصفوفة وقم بفرزها حسب الوزن
• قم بالتكرار على الحواف التي تم فرزها، ولكل عقدة ربط i وj لكل حافة، تحقق مما إذا كان i وj متصلين.إذا كانت كذلك، فتخطى الحافة، وإلا أضف الحافة إلى MST.

المشكلة الوحيدة هي أن تكون قادرًا بسرعة على تحديد ما إذا كانت العقدتان متصلتين أم لا.لهذا، يمكنك استخدام بنية بيانات Union-Find، والتي تبدو كالتالي:

int T[MAX_#_OF_NODES]

int getParent(int a)
{
  if (T[a]==-1)return a;
  return T[a]=getParent(T[a]);
}
void Unite(int a,int b)
{
  if (rand()&1)
     T[a]=b;
  else
     T[b]=a;
}

في البداية، ما عليك سوى تهيئة T إلى الكل -1، ثم في كل مرة تريد معرفة ما إذا كانت العقدتين A وB متصلتين، ما عليك سوى مقارنة العقدتين الأصليتين - إذا كانتا متماثلتين، فإنهما متصلتان (مثل هذا getParent(A)==getParent(B)).عندما تقوم بإدراج الحافة إلى MST، تأكد من تحديث Union-Find باستخدام Unite(getParent(A),getParent(B)).

التحليل بسيط، حيث تقوم بفرز الحواف والتكرار باستخدام UF الذي يأخذ O(1).لذلك فإن O(E logE + E ) يساوي O(E log E).

هذا هو ؛-)

Answer 2

لم أضطر للتعامل مع الخوارزمية من قبل، ولكن ما قمت بتنفيذه لا يتطابق مع الخوارزمية كما هو موضح أدناه ويكيبيديا.الخوارزمية هناك تعمل على النحو التالي.

1. ولكن كل القمم في قائمة الانتظار.يا (الخامس)
2. بينما قائمة الانتظار ليست فارغة ...يا (الخامس)
   1. خذ الحافة بأقل وزن من قائمة الانتظار.يا (سجل (V))
   2. تحديث أوزان القمم المجاورة.O(E / V)، هذا هو متوسط ​​عدد القمم المجاورة.
   3. إعادة إنشاء بنية قائمة الانتظار.يا (سجل (V))

هذا يعطي

        O(V) + O(V) * (O(log(V)) + O(V/E))
      = O(V) + O(V) * O(log(V)) + O(V) * O(E / V)
      = O(V) + O(V * log(V)) + O(E)
      = O(V * log(V)) + O(E)

بالضبط ما يتوقعه المرء.