خوارزمية الفرز الطوبولوجي: Python, C++ مثال

ما هي خوارزمية الفرز الطوبولوجي؟

يُعرف الفرز الطوبولوجي أيضًا باسم خوارزمية خان وهي خوارزمية فرز شائعة. باستخدام رسم بياني موجه كمدخل، يقوم الفرز الطوبولوجي بفرز العقد بحيث تظهر كل منها قبل العقدة التي تشير إليها.

تُطبَّق هذه الخوارزمية على الرسم البياني الموجه غير الدوري (DAG) بحيث يظهر كل عقدة في المصفوفة المرتبة قبل جميع العقد الأخرى التي تشير إليها. وتتبع هذه الخوارزمية قواعد محددة بشكل متكرر حتى يكتمل الفرز.

لتبسيط الأمر، انظر إلى المثال التالي:

مخطط موجه

هنا، نلاحظ أن العقدة "أ" ليس لها درجة داخلية. الدرجة الداخلية تعني الحافة التي تشير إلى عقدة. العقدتان "ب" و"ج" مرتبطتان مسبقًا بالعقدة "أ"، بينما العقدة "هـ" مرتبطة مسبقًا بالعقدتين "د" و"و". بعض العقد تعتمد على عقد أخرى.

إليكم تمثيل آخر للرسم البياني أعلاه:

تبعية كل عقدة (الترتيب الخطي)

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

إليك الخطوات للقيام بذلك:

الخطوة 1) ابحث عن العقدة ذات الحواف الواردة صفر، والعقدة ذات الدرجة صفر.

الخطوة 2) قم بتخزين عقدة الدرجة الداخلة الصفرية في قائمة انتظار أو مكدس، ثم قم بإزالة العقدة من الرسم البياني.

الخطوة 3) ثم احذف الحافة الخارجة من تلك العقدة. سيؤدي هذا إلى تقليل عدد الحواف الداخلة للعقدة التالية.

يتطلب الترتيب الطوبولوجي ألا تحتوي بنية بيانات الرسم البياني على أي دورة. يُعتبر الرسم البياني رسمًا بيانيًا موجهًا غير دوري (DAG) إذا استوفى هذه المتطلبات:

• عقدة واحدة أو أكثر بقيمة داخلية تساوي صفرًا.
• لا يحتوي الرسم البياني على أي دورة.

طالما أن هناك عقدًا في الرسم البياني، وكان الرسم البياني لا يزال رسمًا بيانيًا موجهًا غير دوري (DAG)، فسننفذ الخطوات الثلاث المذكورة أعلاه. وإلا، ستقع الخوارزمية في التبعية الدورية، ولن تتمكن خوارزمية كان من إيجاد عقدة ذات درجة دخول صفرية.

كيف يعمل الفرز الطوبولوجي

سنستخدم هنا "خوارزمية كان" للترتيب الطوبولوجي. لنفترض أن لدينا الرسم البياني التالي:

فيما يلي خطوات خوارزمية كان:

الخطوة 1) احسب الحافة الداخلية أو الحافة الواردة لجميع العقد في الرسم البياني.

ملاحظة:

• تعني الدرجة الداخلية الحواف الموجهة التي تشير إلى العقدة.
• الدرجة الخارجية تعني الحواف الموجهة التي تأتي من العقدة.

فيما يلي درجة الدخول ودرجة الخروج للرسم البياني أعلاه:

الخطوة 2) ابحث عن العقدة ذات الدرجة الداخلية الصفرية أو ذات الحواف الواردة الصفرية. العقدة ذات الدرجة الداخلية الصفرية تعني عدم وجود حواف متجهة نحوها. العقدة "أ" لها درجة داخلية صفرية، أي لا توجد حافة تشير إليها. لذا، سنقوم بالإجراءات التالية:

• قم بإزالة هذه العقدة وحوافها الخارجية (الحواف الخارجة).
• ضع العقدة في قائمة الانتظار للطلب.
• قم بتحديث عدد درجات الدخول للعقدة المجاورة لـ "A".

الخطوة 3) نحتاج إلى إيجاد عقدة ذات درجة داخلية تساوي صفرًا. في هذا المثال، العقدتان "ب" و"ج" لهما درجة داخلية تساوي صفرًا. يمكننا هنا اختيار أيٍّ منهما. لنأخذ "ب" ونحذفها من الرسم البياني. ثم نُحدِّث قيم الدرجة الداخلية للعقد الأخرى. بعد تنفيذ هذه العمليات، سيبدو الرسم البياني وقائمة الانتظار كما يلي:

الخطوة 4) لا يوجد ضلع وارد للعقدة "C". لذا، سنزيل العقدة "C" من الرسم البياني ونضيفها إلى قائمة الانتظار. يمكننا أيضًا حذف الضلع الصادر من "C". الآن، سيبدو الرسم البياني كما يلي:

الخطوة 5) نلاحظ أن العقدتين "D" و"F" لهما درجة داخلية تساوي صفرًا. سنأخذ عقدة ونضعها في قائمة الانتظار. لنأخذ "D" أولًا. عندها ستصبح درجة العقدة "E" تساوي 1. الآن، لن تكون هناك عقدة من D إلى E. علينا أن نفعل الشيء نفسه مع العقدة "F"، وستكون النتيجة كما يلي:

الخطوة 6) أصبحت درجة الدخول (الحواف الداخلة) ودرجة الخروج (الحواف الخارجة) للعقدة "E" صفرًا. وبذلك، نكون قد استوفينا جميع الشروط المسبقة للعقدة "E". سنضع "E" في نهاية قائمة الانتظار. وبذلك، لم يتبق لدينا أي عقد، وتنتهي الخوارزمية هنا.

كنية Code للفرز الطوبولوجي

إليكم الشفرة الزائفة للفرز الطوبولوجي باستخدام خوارزمية كان.

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  while node with 0 indegree present:
    topological_list.append(node)
    G.remove(node)
    // Update indegree of present nodes
  return topological_list

يمكن أيضًا تنفيذ الفرز الطوبولوجي باستخدام DFS (عمق البحث الأول) طريقة. ومع ذلك، فإن هذا النهج هو الأسلوب العودي. تعتبر خوارزمية خان أكثر كفاءة من منهج DFS.

C++ تنفيذ الفرز الطوبولوجي

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

الناتج

0       1       2       3       5       4

Python تنفيذ الفرز الطوبولوجي

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list)
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

الناتج

[0, 1, 2, 3, 5, 4]

الرسوم البيانية الدورية لخوارزمية الفرز الطوبولوجي

لا يمكن ترتيب الرسم البياني الذي يحتوي على دورة ترتيبًا طوبولوجيًا، لأن الرسم البياني الدوري يعتمد على دورة. على سبيل المثال، انظر إلى هذا الرسم البياني:

هذا الرسم البياني ليس رسمًا بيانيًا موجهًا غير دوري (DAG) لأن النقاط A وB وC تُشكل دورة. لاحظ أنه لا توجد عقدة ذات درجة دخول صفرية. وفقًا لخوارزمية كان، إذا حللنا الرسم البياني أعلاه:

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

يمكننا اكتشاف الدورات باستخدام الترتيب الطوبولوجي بالخطوات التالية:

الخطوة 1) إجراء الفرز الطوبولوجي.

الخطوة 2) احسب العدد الإجمالي للعناصر في القائمة المصنفة طوبولوجيًا.

الخطوة 3) إذا كان عدد العناصر يساوي العدد الإجمالي للرؤوس، فلا توجد دورة.

الخطوة 4) إذا لم يكن مساوياً لعدد الرؤوس، فهناك دورة واحدة على الأقل في بنية بيانات الرسم البياني المعطاة.

تحليل تعقيد الترتيب الطوبولوجي

يوجد نوعان من التعقيد في الخوارزميات. وهما:

1. تعقيد الوقت
2. تعقيد الفضاء

يتم تمثيل هذه التعقيدات باستخدام دالة توفر تعقيدًا عامًا.

تعقيد الوقت: جميع حالات التعقيد الزمني لخوارزمية الفرز الطوبولوجي متساوية. توجد ثلاث حالات للتعقيد الزمني: أسوأها، ومتوسطها، وأفضلها. التعقيد الزمني لخوارزمية الفرز الطوبولوجي هو O(E + V)، حيث E يمثل عدد الحواف في الرسم البياني، وV يمثل عدد الرؤوس فيه.

دعونا نتجاوز هذا التعقيد:

الخطوة 1) في البداية، سوف نقوم بحساب جميع الدرجات. للقيام بذلك، نحتاج إلى المرور عبر جميع الحواف، وفي البداية، سنعين جميع درجات قمة الرأس V إلى الصفر. لذا فإن الخطوات الإضافية التي نكملها ستكون يا (ف + ه).

الخطوة 2) سوف نجد العقدة بقيمة صفر درجة. نحن بحاجة إلى البحث من الرقم V للرأس. وبذلك تكون الخطوات قد اكتملت يا (الخامس).

الخطوة 3) بالنسبة لكل عقدة ذات درجات داخلية صفرية، سنزيل تلك العقدة ونخفض الدرجة الداخلية. سيؤدي تنفيذ هذه العملية لجميع العقد إلى يا (ه).

الخطوة 4) وأخيرا، سوف نتحقق مما إذا كان هناك أي دورة أم لا. سوف نتحقق مما إذا كان إجمالي عدد العناصر في المصفوفة التي تم فرزها يساوي إجمالي عدد العقد. ستستغرق يا (1).

إذن، هذه هي التعقيدات الزمنية الفردية لكل خطوة من خطوات الفرز الطوبولوجي أو الترتيب الطوبولوجي. يمكننا القول أن التعقيد الزمني من الحساب أعلاه سيكون O(V + E)؛ حيث O تعني دالة التعقيد.

تعقيد الفضاء: احتجنا إلى مساحة O(V) لتشغيل خوارزمية الفرز الطوبولوجي. فيما يلي الخطوات التي احتجنا فيها إلى مساحة للبرنامج:

• كان علينا حساب جميع درجات العقد الموجودة في الرسم البياني. نظرًا لأن الرسم البياني يحتوي على إجمالي العقد V، فنحن بحاجة إلى إنشاء مصفوفة بالحجم V. لذا، كانت المساحة المطلوبة يا (الخامس).
• تم استخدام بنية بيانات قائمة الانتظار لتخزين العقدة بدرجة صفر. قمنا بإزالة العقد ذات الدرجة الصفرية من الرسم البياني الأصلي ووضعناها في قائمة الانتظار. ولهذا كانت المساحة المطلوبة يا (الخامس).
• يُطلق على المصفوفة اسم "order"، والتي تخزن العقد بترتيب طوبولوجي. وقد تطلب ذلك أيضًا يا (الخامس) المسافات.

هذه هي تعقيدات المساحة الفردية. لذا، نحتاج إلى زيادة هذه المساحات إلى أقصى حد ممكن خلال وقت التشغيل. يُرمز لتعقيد المساحة بـ O(V)، حيث V يُمثل عدد الرؤوس في الرسم البياني.

تطبيق الفرز الطوبولوجي

تُستخدم عملية الفرز الطوبولوجي على نطاق واسع. إليك بعضًا منها:

• يتم استخدامه عندما Operaنظام تينغ يحتاج إلى تنفيذ تخصيص الموارد.
• إيجاد دورة في الرسم البياني. يمكننا التحقق مما إذا كان الرسم البياني عبارة عن رسم بياني موجه غير دوري (DAG) أم لا باستخدام الفرز الطوبولوجي.
• ترتيب الجمل في تطبيقات الإكمال التلقائي.
• يُستخدم للكشف عن جمود.
• تستخدم أنواع مختلفة من الجدولة أو جدولة الدورات التدريبية الفرز الطوبولوجي.
• حل التبعيات. على سبيل المثال، إذا حاولت تثبيت حزمة، فقد تحتاج هذه الحزمة أيضًا إلى حزم أخرى. يكتشف الترتيب الطوبولوجي جميع الحزم اللازمة لتثبيت الحزمة الحالية.
• لينكس يستخدم الفرز الطوبولوجي في "apt" للتحقق من تبعية الحزم.

الأسئلة الشائعة