الفرق بين المراجعتين لصفحة: «Algorithms/Graph Algorithms»
لا ملخص تعديل |
|||
| (3 مراجعات متوسطة بواسطة نفس المستخدم غير معروضة) | |||
| سطر 7: | سطر 7: | ||
== خوارزميات إيجاد الشجرة الممتدة الصغرى == | == خوارزميات إيجاد الشجرة الممتدة الصغرى == | ||
الشجرة الممتدة Spanning Tree لرسم بياني متّصل connected وغير موجّه undirected، هي رسم بياني فرعي subgraph يكون على هيئة [[Algorithms/binary trees|شجرة بيانات]] تتصل كل الرؤوس فيها ببعضها البعض، ويمكن للرسم البياني الواحد أن يمتلك عددًا من الأشجار الممتدة المختلفة. | |||
=== [[Algorithms/Kruskal MST|خوارزمية كروسكال | الشجرة الممتدة الصغرى Minimum Spannig Tree (وتعرف اختصارًا MST) أو الشجرة الممتدة ذات الوزن الأدنى Minimum weight spanning tree لرسم بياني متصل وموزون وغير موجّه هي شجرة ممتدة ذات وزن أقل من وزن أي شجرة ممتدة أخرى أو يساويه. ويعرف وزن الشجرة الممتدة بأنه مجموع أوزان جميع الأضلاع في الشجرة الممتدة. | ||
تمتلك الشجرة الممتدة الصغرى <code>(V - 1)</code> من الأضلاع وتمثّل <code>V</code> عدد الرؤوس في الرسم البياني المعطى. | |||
=== [[Algorithms/Kruskal MST|خوارزمية كروسكال]] === | |||
تعثر خوارزمية كروسكال Kruskal على الشجرة الممتدة الصغرى في الرسم البياني المعطى، بترتيب الأضلاع تصاعديًا ثم اختيار الضلع الأصغر. | تعثر خوارزمية كروسكال Kruskal على الشجرة الممتدة الصغرى في الرسم البياني المعطى، بترتيب الأضلاع تصاعديًا ثم اختيار الضلع الأصغر. | ||
=== [[Algorithms/Prim MST|خوارزمية برم | === [[Algorithms/Prim MST|خوارزمية برم]] === | ||
تعثر خوارزمية Prim على الشجرة الممتدة الصغرى في الرسم البياني المعطى، وتبدأ بشجرة ممتدة فارغة وتعتمد في عملها على مجموعتين من الرؤوس. | تعثر خوارزمية Prim على الشجرة الممتدة الصغرى في الرسم البياني المعطى، وتبدأ بشجرة ممتدة فارغة وتعتمد في عملها على مجموعتين من الرؤوس. | ||
=== [[Algorithms/Boruvka MST|خوارزمية بوروفكا]] === | |||
تعدّ خوارزمية بوروفكا أقدم خوارزمية لإيجاد الشجرة الممتدة الصغرى وقد وضعها بوروفكا سنة 1926م، قبل اختراع الحواسيب بفترة طويلة، وقد نشرت هذه الخوارزمية كطريقة لبناء شبكة فعّالة من التمديدات الكهربائية. | |||
== خوارزميات إيجاد المسار الأقصر == | == خوارزميات إيجاد المسار الأقصر == | ||
| سطر 29: | سطر 36: | ||
الترتيب الطوبولوجي Topological Sorting للرسوم البيانية الموجّهة غير الدائرية، هو ترتيب خطي للرؤوس يأتي فيه الرأس <code>u</code> قبل الرأس <code>v</code> في الترتيب لكل ضلع <code>u-v</code> موجّه. | الترتيب الطوبولوجي Topological Sorting للرسوم البيانية الموجّهة غير الدائرية، هو ترتيب خطي للرؤوس يأتي فيه الرأس <code>u</code> قبل الرأس <code>v</code> في الترتيب لكل ضلع <code>u-v</code> موجّه. | ||
=== [[Algorithms/Kahn|خوارزمية كان للترتيب الطوبولوجي]] === | |||
تجري خوارزمية كان عملية الترتيب الطوبولوجي باستخدام [[Algorithms/queues|رتل]]. | |||
[[تصنيف:الخوارزميات]] | |||
[[تصنيف:خوارزميات الرسوم البيانية]] | |||
المراجعة الحالية بتاريخ 17:41، 24 ديسمبر 2019
الرسم البياني هو من بنى المعطيات غير الخطية والتي تتضمّن عقدًا nodes وأضلاع edges. تُسمّى العقد في بعض الأحيان بالرؤوس vertices والأضلاع بالخطوط lines أو الأقواس arcs التي تربط بين عقدتين في الرسم البياني.
الكشف عن وجود دورة في الرسم البياني
الهدف من هذه الخوارزمية هو الكشف عن وجود دورة في الرسم البياني الموجّه.
خوارزميات إيجاد الشجرة الممتدة الصغرى
الشجرة الممتدة Spanning Tree لرسم بياني متّصل connected وغير موجّه undirected، هي رسم بياني فرعي subgraph يكون على هيئة شجرة بيانات تتصل كل الرؤوس فيها ببعضها البعض، ويمكن للرسم البياني الواحد أن يمتلك عددًا من الأشجار الممتدة المختلفة.
الشجرة الممتدة الصغرى Minimum Spannig Tree (وتعرف اختصارًا MST) أو الشجرة الممتدة ذات الوزن الأدنى Minimum weight spanning tree لرسم بياني متصل وموزون وغير موجّه هي شجرة ممتدة ذات وزن أقل من وزن أي شجرة ممتدة أخرى أو يساويه. ويعرف وزن الشجرة الممتدة بأنه مجموع أوزان جميع الأضلاع في الشجرة الممتدة.
تمتلك الشجرة الممتدة الصغرى (V - 1) من الأضلاع وتمثّل V عدد الرؤوس في الرسم البياني المعطى.
خوارزمية كروسكال
تعثر خوارزمية كروسكال Kruskal على الشجرة الممتدة الصغرى في الرسم البياني المعطى، بترتيب الأضلاع تصاعديًا ثم اختيار الضلع الأصغر.
خوارزمية برم
تعثر خوارزمية Prim على الشجرة الممتدة الصغرى في الرسم البياني المعطى، وتبدأ بشجرة ممتدة فارغة وتعتمد في عملها على مجموعتين من الرؤوس.
خوارزمية بوروفكا
تعدّ خوارزمية بوروفكا أقدم خوارزمية لإيجاد الشجرة الممتدة الصغرى وقد وضعها بوروفكا سنة 1926م، قبل اختراع الحواسيب بفترة طويلة، وقد نشرت هذه الخوارزمية كطريقة لبناء شبكة فعّالة من التمديدات الكهربائية.
خوارزميات إيجاد المسار الأقصر
خوارزمية بِلمان - فورد
تمتاز هذه الخوارزمية بقدرتها على إيجاد المسار الأقصر في الرسوم البيانية التي تكون فيها أوزان الأضلاع ذات قيم سالبة.
خوارزمية ديكسترا
تنتج خورازمية ديكسترا Dijkstra شجرة المسار الأقصر بدءًا من المصدر المعطى كجذر لهذه الشجرة.
خوارزمية فلويد وارشال
تقدّم خوارزمية فلويد-وارشال Floyd-Warshall حلًّا لمشكلة المسار الأقصر لجميع الأزواج.
الترتيب الطوبولوجي
الترتيب الطوبولوجي Topological Sorting للرسوم البيانية الموجّهة غير الدائرية، هو ترتيب خطي للرؤوس يأتي فيه الرأس u قبل الرأس v في الترتيب لكل ضلع u-v موجّه.
خوارزمية كان للترتيب الطوبولوجي
تجري خوارزمية كان عملية الترتيب الطوبولوجي باستخدام رتل.