هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (مايو 2025)

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

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

في علوم الحاسوب ،يُشير "الترتيب الطوبولوجي" أو "الفرز الطوبولوجي" لمخطط بياني موجه إلى ترتيب خطي لرؤوس بحيث لكل حافة موجهة (u,v) من الرأس u إلى الرأس v ، يأتي u قبل v في الترتيب.

مثال على ذلك، قد تُمثل رؤوس المخطط مهامًا تنفيذها، و تمثل الحواف القيود التي تُفرض تنفيذ مهمة واحدة قبل أخرى؛و في هذا السياق، الترتيب الطوبولوجي هو مجرد تسلسل صالح للمهام. على وجه التحديد، و الفرز الطوبولوجي هو عبارة عن عبور للرسم البياني حيث تَتَم زيارة كل عُقدة v فقط بعد زيارة جميع تبعياتها . يَكُون الترتيب الطوبولوجي ممكنًا إذا تم لم يِكُنْ للرسم البياني أي دورات موجهة ، أي إذا كان رسمًا بيانيًا غير دوري موجه (DAG).و يَحتوي أي DAG على ترتيب طوبولوجي واحد على الأقل، وهناك خوارزميات زمنية خطية لإنشائه. للفرز الطوبولوجي العديد من التطبيقات، وخاصة في مشاكل الترتيب مثل مجموعة قوس التغذية الراجعة . الفرز الطوبولوجي ممكن أيضًا عندما يكون لدى DAG مكونات غير متصلة .

يُعد التطبيق النموذجي للفرز الطوبولوجي هو جدولة سلسلة من الوظائف أو المهام بناءً على علاقات الاعتمادية بينها. تُمثَّّل الوظائف برؤوس(عُقد)، وتكون هناك حافة من x إلى y إذا كان لا بد من إتمام المهمة x قبل أن تبدأ المهمة y (على سبيل المثال، عند غسل الملابس، يجب أن تنتهي الغسالة من عملها قبل وضع الملابس في المجفف).

في هذه الحالة، يوفر الفرز الطوبولوجي ترتيبًا صالحًا لتنفيذ المهام. تمت دراسة تطبيق وثيق الصلة بخوارزميات الفرز الطوبولوجي لأول مرة في أوائل الستينيات في سياق تقنية PERT للجدولة في إدارة المشاريع . ^[1] في هذا التطبيق، تمثل رؤوس الرسم البياني المعالم الرئيسية للمشروع، وتمثل الحواف المهام التي يجب تنفيذها بين معلم رئيسي وآخر. يشكل الفرز الطوبولوجي أساس خوارزميات الوقت الخطي للعثور على المسار الحرج للمشروع، وهو عبارة عن سلسلة من المعالم والمهام التي تتحكم في طول الجدول الزمني الإجمالي للمشروع.

في علم الحاسوب، تَظهر تطبيقات من هذا النوع في مجالات مُتعددة، منها: جدولة التعليمات ، وترتيب تقييم خلايا الصيغ عند إعادة حساب القيم في جدولة البيانات ، وتوليف المنطق الرقمي ، وتحديد ترتيب مهام التجميع التي يجب القيام بها في ملفات Makefiles ، وتسلسل البيانات، وحل تبعيات الرموز في الروابط . ويَتم استخدامه أيضًا لتحديد الترتيب الذي يتم به تحميل الجداول ذات المفاتيح الأجنبية في قواعد البيانات.

تُحقق الخوارزميات الشائعة للفرز الطوبولوجي زمن تنفيذ خطيًا لعدد العقد بالإضافة إلى عدد الحواف، بشكل مقارب، ${\displaystyle O(\left|{V}\right|+\left|{E}\right|).}$

قالب:Data structures and algorithms إحدى هذه الخوارزميات، وقد وُصفت لأول مرة بواسطة كان Kahn (1962) ، تعمل من خلال اختيار الرؤوس بنفس الترتيب الذي سيظهر في الفرز الطوبولوجي النهائي. ^[2] أولاً، ابحث عن قائمة "عقد البداية" التي ليس لها حواف واردة وأدخلها في مجموعة S؛ يجب أن توجد عقدة واحدة على الأقل في رسم بياني غير دوري (منتهي) غير فارغ. ثم:

L ← قائمة فارغة تحتوي على العناصر المصنفة
S ← مجموعة من جميع العقد بدون حافة واردة

في حين أن S ليست فارغة، افعل
  إزالة عقدة n من S
  أضف n إلى L
  لكل عقدة m ذات حافة e من n إلى m
    إزالة الحافة e من الرسم البياني
    إذا لم يكن لدى m أي حواف واردة أخرى ، فإن
      أدخل m في S

إذا كان الرسم البياني له حواف، إذن
  خطأ العودة (الرسم البياني يحتوي على دورة واحدة على الأقل)
آخر 
  العودة L (ترتيب مرتب طوبولوجيًا)

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

نظرًا لعدم تفرد النوع الناتج، يمكن أن تكون البنية S عبارة عن مجموعة أو طابور أو كومة أو مكدس.

وبحسب ترتيب إزالة العقد من المجموعة S، يتم إنشاء حل مختلف في كل مرة. يشكل أحد أشكال خوارزمية كان الذي يكسر الروابط معجميًا مكونًا رئيسيًا لخوارزمية كوفمان-جراهام للجدولة المتوازية ورسم الرسوم البيانية الطبقية .

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

L ← قائمة فارغة تحتوي على العقد المصنفة
في حين أن هناك عقدًا بدون علامة دائمة ،
  حدد عقدة غير مميزة n
  زيارة( ن )

دالة الزيارة (العقدة n )
  إذا كان n له علامة دائمة، إذن
    يعود
  إذا كان n له علامة مؤقتة ،
    توقف (يحتوي الرسم البياني على دورة واحدة على الأقل)

  ضع علامة n بعلامة مؤقتة

  لِكلُ عقدة m ذات حافة من n إلى m
    زيارة( م )

  علامة n بعلامة دائمة
  أضف n إلى رأس L

كل رأس n يُضاف إلى بداية قائمة الإخراج L فقط بعد النظر في جميع الرؤوس الأخرى التي تعتمد على n (أي جميع أحفاد n في الرسم البياني). بالتحديد، عندما تضيف الخوارزمية الرأس n ، نضمن أن جميع الرؤوس التي تعتمد عليه n موجودة بالفعل في قائمة المخرجات L: إذ أُضيفت إلى L إما بواسطة الاستدعاء visit() المتكرر ،الذي انتهى قبل استدعاء دالة visit n ، أو عن طريق استدعاء دالة visit() الذي بدأ حتى قبل استدعاء دالة visit n .

و بِمَا أنَّ كُلَ حَافة ورَأس يَتِمَ زِيَارَتُهُ مَرة وَاحِدَة، فإن الخوارزمِية تَعمل بِزَمن خَطِي.

هذه الخوارزمية المبنية على البحث بالعمق هي التي وصفها Cormen et al. (2001) ؛ ^[3] ويبدو أنها وُصفت لأول مرة في المطبوعات بِوَاسِطة تارجان في عام 1976. ^[4]

على جهاز وصول عشوائي متوازي ، يُمكن بناء ترتيب طوبولوجي بزمن O ((log n ) ² ) باستخدام عدد كثير من المعالجات متعدد الحدود، مما يَضَعُ المُشكلة ضمن فئة التعقيد NC ^{2. [5]}

إحدى الطرق لتحقيق ذلك هي بتربيع مصفوفة الجوار الخاصة بالرسم البياني بشكل متكرر لعدد لوغاريتمي من المرات، باستخدام ضرب المصفوفات بالحد الأدنى مع التعظيم بدلاً من التصغير. تصف المصفوفة الناتجة أطول مسافات المسار في الرسم البياني. يؤدي فرز الرؤوس حسب أطوال أطول مساراتها الواردة إلى إنتاج ترتيب طوبولوجي. ^[6]

خوارزمية للترتيب الطوبولوجي المتوازي على آلات الذاكرة الموزعة تقوم بتمرير خوارزمية كان لـ DAG ${\displaystyle G=(V,E)}$ . ^[7]

على مستوى عالٍ، تقوم خوارزمية Kahn بإزالة الرؤوس ذات الدرجة الداخلية 0 بشكل متكرر و إضافتها إلى الترتيب الطوبولوجي حسب الترتيب الذي أُزيلت فيه.

وبما أن الحواف الخارجة من الرؤوس المُزالة تُزال أيضًا، فسيكون هناك مجموعة جديدة من الرؤوس من الدرجة الداخلية 0، حيث يتم تكرار الإجراء حتى لا يتبقى أي رؤوس. هذه الخوارزمية تقوم بتنفيذ ${\displaystyle D+1}$ التكرارات، حيث D هو أطول مسار في G يمكن تنفيذ كل تكرار بالتوازي، وهذه هي فكرة الخوارزمية التالية.

فيما يلي، يُفترض أن تقسيم الرسم البياني مخزّن على p من عناصر معالجة (PE)، والموسومة بالأرقام ${\displaystyle 0,\dots ,p-1}$ .

يبدأ كل عنصر معالجة PE i بتهيئة مجموعة من الرؤوس المحلية ${\displaystyle Q_{i}^{1}}$ التي تملك درجة داخلة 0، حيثُ يُمثّل المؤشر العلوي التكرار الحالي. نظرًا لأن جميع الرؤوس في المجموعة المحلية ${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$ لديها درجة داخلة 0، أي أنها غير متجاورة، فإنه يمكن ترتيبها بأي شكل لإنتاج ترتيب طوبولوجي صحيح. لتعيين مؤشر عالمي لكل رأس، يتم حساب مجموع البادئة على أحجام ${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$ . لذا، في كل خطوة، هناك ${\textstyle \sum _{i=0}^{p-1}|Q_{i}|}$ تمت إضافة الرؤوس إلى الفرز الطوبولوجي.

في الخطوة الأولى، يقوم PE j بإسناد الفهارس:${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ إلى الرؤوس المحلية في ${\displaystyle Q_{j}^{1}}$ .

تُزال هذه الرؤوس في ${\displaystyle Q_{j}^{1}}$ مع الحواف الخارجة منها.

لكل حافة خارجية ${\displaystyle (u,v)}$ يكون الطرف v فيها موجودًا في عنصر معالجة آخر PE ${\displaystyle l,j\neq l}$ ، يتم إرسال رسالة تحتوي على ${\displaystyle (u,v)}$ إلى PE l .

بعد إزالة جميع الرؤوس في ${\displaystyle Q_{j}^{1}}$،تُرسل الرسائل المجمعة إلى عناصر المعالجة المعينة.

كل رسالة ${\displaystyle (u,v)}$ يتم استلامها تُحدث درجة الدخول للرأس المحلي v . إذا انخفضت الدرجة الداخلية إلى الصفر، تتم إضافة v إلى ${\displaystyle Q_{j}^{2}}$ . ثم تبدأ التكرار التالي.

في الخطوة (k) ، يقوم PE j بِتَعيين المُؤشِرات ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ ، أين ${\displaystyle a_{k-1}}$ هُو العَدَد الإجمَالي للرؤوس المُعَالَجة بَعدَ ${\displaystyle k-1}$ تُتَكرر هَذِهِ العَملية حتى لا يَتبقى أي رؤوس لمُعَالجَتها، وبالتالي ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$ . وهذه نظرة عامة على الكود الزائف لبرنامج واحد عالي المستوى وبيانات متعددة لهذه الخوارزمية.

لاحظ أن مجموع البادئة للإزاحات المحلية ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ يمكن حسابها بكفاءة بالتوازي.

عناصر معالجة p ذات معرفات من 0 إلى p -1
المدخلات: G = (V, E) DAG، موزعة على PEs، مؤشر PE j = 0، ... ، ص - 1
الإخراج: الفرز الطوبولوجي لـ G

دالة traverseDAGDistributed
  δ الدرجة الواردة للرؤوس المحلية V
  Q = {v ∈ V | δ[v] = 0} // جميع الرؤوس ذات الدرجة الداخلية 0
  عدد الرؤوس المعالجة = 0

  يفعل
    مجموع بادئة البناء العالمية على حجم Q // الحصول على الإزاحات والعدد الإجمالي للرؤوس في هذه الخطوة
    offset = nrOfVerticesProcessed + sum(Q i, i = 0 to j - 1) // j هو مؤشر المعالج
    لكل u في Q
      localOrder[u] = index++;
      foreach (u,v) في E قم بنشر الرسالة ( u, v ) إلى PE صاحب الرأس v
    nrOfVerticesProcessed += sum(|Q i |, i = 0 إلى p - 1)
    توصيل جميع الرسائل إلى جيران الرؤوس في Q
    استقبال الرسائل للرؤوس المحلية V
    إزالة جميع الرؤوس في Q
    لكل رسالة ( u, v ) مستلمة:
      إذا --δ[v] = 0
        أضف v إلى Q
  في حين أن الحجم العالمي لـ Q > 0

  إرجاع الطلب المحلي

تعتمد تكلفة الاتصال بشكل كبير على قسم الرسم البياني المُعطى. أما بالنسبة لوقت التشغيل، ففي نموذج CRCW-PRAM الذي يَسمح بالجلب والتناقص في وقتٍ ثابت، تَعمل هذه الخوارزمية في الزمن${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$ حيث إن : D هو مرة أطول مسار في G و Δ الدرجة العُظمى لأي رأس في G. ^[7]

يُمكن استخدام الترتيب الطوبولوجي أيضًا لحساب المسارات الأقصر بسرعة في رسم بياني موجه لا دوري مرجح . لنفترض أن V هي قائمة الرؤوس في مثل هذا الرسم البياني، مرتبة ترتيبًا طوبولوجيًا. عندئذٍ يمكن أن يُستخدم الخوارزم التالية بحساب أقصر مسار من بعض رؤوس المصدر s إلى جميع الرؤوس الأخرى: ^[3]

في الرسم البياني المكون من n رأسًا و m حافة، تأخذ هذه الخوارزمية Θ(n + m) ، أي زمنًا خطيًا . ^[3]

إذا كان للفرز الطوبولوجي خاصية أن جميع أزواج الرؤوس المتتالية في الترتيب المفرز متصلة بواسطة حواف، فإن هذه الحواف تُشكل مسار هاميلتونيًا موجهًا في الرسم البياني المُوجه اللادوري DAG . إذا كَان مَسار هاميلتوني مَوجُودًا، فإن تَرتيب الفَرز الطوبولوجي يَكُون فريدًا؛ فلا يوجد ترتيب آخر يَحتَرِم حَوَاف المَسار. وَعلى العكس مِنْ ذَلك، إذا لم يُشكّل التَرتِيب الطوبولوجي مَسَارًا هاميلتونيًا، فسيكون لدى DAG ترتيبان طوبولوجيان صالحان أو أكثر، لأنه في هذه الحالة يمكن دائمًا إنشاء ترتيب صالح آخر عن طريق تبديل رأسين متتاليين غير متصلين بحافة بينهما. لذلك، من الممكن اختبار ما إذا كان الترتيب الفريد موجودًا، وما إذا كان مسار هاملتوني موجودًا في الوقت الخطي، على الرغم من صعوبة NP لمشكلة مسار هاملتوني للرسوم البيانية الموجهة الأكثر عمومية (أي الرسوم البيانية الموجهة الدورية). ^[8]

الترتيبات الطوبولوجية ترتبط ارتباطًا وثيقًا بمفهوم الامتداد الخطي للترتيب الجزئي في الرياضيات.

المجموعة المرتبة جزئيًا هي ببساطة مجموعة من العناصر تعريف لعلاقة عدم المساواة "≤"، مما يُلبي مسلمات الانعكاسية ( x ≤ x )، التناظر المضاد (إذا x ≤ ي و ي ≤ x ثم x = y ) والتعدية (إذا x ≤ ي و ي ≤ z ، ثم x ≤ ز ).

أما الترتيبات الكلية هو ترتيب جزئي حيث لكل كائنين x و y في المجموعة، إما x أو y ≤ ي أو ي ≤ x . تعتبر الطلبات الإجمالية مألوفة في علوم الحاسوب باعتبارها مشغلي المقارنة اللازمين لأداء خوارزميات فرز المقارنة . بالنسبة للمجموعات المنتهية، يمكن تمثيل الترتيب الكلي بتسلسل خطي من العناصر، حيثُ تَكُون العَلاقة "≤" صحيحة كلما سَبَقَ العنصر الأول العنصر الثاني في الترتيب؛ ويمكن استخدام خوارزمية فرز المقارنة لتحويل الترتيب الكلي إلى تسلسل بهذه الطريقة.

أما الامتداد الخطي للترتيب الجزئي، هو ترتيب كلي يتوافق معه، بمعنى أنه إذا كان x ≤ y في الترتيب الجزئي، فإنه يجب أن يكون x ≤ y أيضًا في الترتيب الكلي.

يمكن تعريف ترتيب جزئي انطلاقًا من أي مخطط بياني موجه لا دوريًا (DAG )، وذلك باعتبار مجموعة العناصر هي رؤوس DAG، وتحديد x ≤ يكون y بأنها صحيحًا لأي رأسين x و y ، كلما وُجد مسار مُوجَّه من x إلى y ؛ أي كلما أمكن الوصول إلى y من x . بهذه التعريفات، يكون الترتيب الطوبولوجي لـ DAG هو نفسه الامتداد الخطي لهذا الترتيب الجزئي. و بالعكس، يمكن تعريف أي ترتيب جزئي باعتباره علاقة الوصول في مخطط DAG.

هناك طريقتان لبناء هذا النوع من المخططات:

إنشاء مخطط يحتوي على رأس لكل عنصر في مجموعة الترتيب الجزئي ، ورسم حافة xy لكل زوج من الكائنات التي يكون x لها ≤ ي .

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

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

• tsort ، برنامج يونكس للفرز الطوبولوجي
• مجموعة قوس التغذية الراجعة ، وهي مجموعة من الحواف التي يسمح إزالتها بفرز الرسم البياني الفرعي المتبقي طوبولوجيًا
• خوارزمية المكونات المتصلة بقوة لتارجان ، وهي خوارزمية تعطي قائمة مرتبة طوبولوجيًا للمكونات المتصلة بقوة في رسم بياني
• الترتيب ما قبل الطوبولوجي

• دي كنوث ، فن برمجة الكمبيوتر ، المجلد 1، القسم 2.2.3، الذي يقدم خوارزمية للفرز الطوبولوجي للترتيب الجزئي، وتاريخًا موجزًا.
• برتراند ماير ، لمسة من الطبقة: تعلم البرمجة بشكل جيد مع الكائنات والعقود ، سبرينغر ، 2009، الفصل 15، ابتكار وهندسة خوارزمية: الفرز الطوبولوجي ، باستخدام لغة برمجة حديثة، لتقديم تربوي مفصل للفرز الطوبولوجي (باستخدام أحد متغيرات خوارزمية كان) مع مراعاة تصميم بنية البيانات، وتصميم واجهة برمجة التطبيقات، ومخاوف هندسة البرمجيات.

• قاموس NIST للخوارزميات وهياكل البيانات: الترتيب الطوبولوجي

  ميّز عن الخوارزمية المجرية.

1. ^ اكتب عنوان المرجع بين علامتي الفتح <ref> والإغلاق </ref> للمرجع Jarnagin
2. ^ اكتب عنوان المرجع بين علامتي الفتح <ref> والإغلاق </ref> للمرجع Kahn
3. ^ ^{ا ب ج} اكتب عنوان المرجع بين علامتي الفتح <ref> والإغلاق </ref> للمرجع CLRS
4. ^ اكتب عنوان المرجع بين علامتي الفتح <ref> والإغلاق </ref> للمرجع Tarjan
5. ^ اكتب عنوان المرجع بين علامتي الفتح <ref> والإغلاق </ref> للمرجع Cook
6. ^ اكتب عنوان المرجع بين علامتي الفتح <ref> والإغلاق </ref> للمرجع DNS
7. ^ ^{ا ب} اكتب عنوان المرجع بين علامتي الفتح <ref> والإغلاق </ref> للمرجع SMDD
8. ^ اكتب عنوان المرجع بين علامتي الفتح <ref> والإغلاق </ref> للمرجع VM