الفرق بين المراجعتين لصفحة: «Algorithms/Graph Algorithms»
لا ملخص تعديل |
لا ملخص تعديل |
||
| سطر 2: | سطر 2: | ||
الرسم البياني هو من بنى المعطيات غير الخطية والتي تتضمّن عقدًا nodes وأضلاع edges. تُسمّى العقد في بعض الأحيان بالرؤوس vertices والأضلاع بالخطوط lines أو الأقواس arcs التي تربط بين عقدتين في الرسم البياني. | الرسم البياني هو من بنى المعطيات غير الخطية والتي تتضمّن عقدًا nodes وأضلاع edges. تُسمّى العقد في بعض الأحيان بالرؤوس vertices والأضلاع بالخطوط lines أو الأقواس arcs التي تربط بين عقدتين في الرسم البياني. | ||
== الكشف عن وجود دورة في الرسم البياني == | == [[Algorithms/detect cycle|الكشف عن وجود دورة في الرسم البياني]] == | ||
الهدف من هذه الخوارزمية هو الكشف عن وجود دورة في الرسم البياني الموجّه. | الهدف من هذه الخوارزمية هو الكشف عن وجود دورة في الرسم البياني الموجّه. | ||
== خوارزمية كروسكال لإيجاد الشجرة الممتدة الصغرى == | == [[Algorithms/Kruskal MST|خوارزمية كروسكال لإيجاد الشجرة الممتدة الصغرى]] == | ||
تعثر هذه الخوارزمية على الشجرة الممتدة الصغرى في الرسم البياني المعطى، بترتيب الأضلاع تصاعديًا ثم اختيار الضلع الأصغر. | تعثر هذه الخوارزمية على الشجرة الممتدة الصغرى في الرسم البياني المعطى، بترتيب الأضلاع تصاعديًا ثم اختيار الضلع الأصغر. | ||
== خوارزمية برم لإيجاد الشجرة الممتدة الصغرى == | == [[Algorithms/Prim MST|خوارزمية برم لإيجاد الشجرة الممتدة الصغرى]] == | ||
تعثر هذه الخوارزمية على الشجرة الممتدة الصغرى في الرسم البياني المعطى، وتبدأ بشجرة ممتدة فارغة وتعتمد في عملها على مجموعتين من الرؤوس. | تعثر هذه الخوارزمية على الشجرة الممتدة الصغرى في الرسم البياني المعطى، وتبدأ بشجرة ممتدة فارغة وتعتمد في عملها على مجموعتين من الرؤوس. | ||
== خوارزميات إيجاد المسار الأقصر == | == خوارزميات إيجاد المسار الأقصر == | ||
=== [[Algorithms/Bellman Ford|خوارزمية بِلمان - فورد]] === | |||
=== خوارزمية بِلمان - فورد === | |||
تمتاز هذه الخوارزمية بقدرتها على إيجاد المسار الأقصر في الرسوم البيانية التي تكون فيها أوزان الأضلاع ذات قيم سالبة. | تمتاز هذه الخوارزمية بقدرتها على إيجاد المسار الأقصر في الرسوم البيانية التي تكون فيها أوزان الأضلاع ذات قيم سالبة. | ||
=== خوارزمية ديكسترا === | === [[Algorithms/Dijkstra|خوارزمية ديكسترا]] === | ||
تنتج خورازمية ديكسترا Dijkstra شجرة المسار الأقصر بدءًا من المصدر المعطى كجذر لهذه الشجرة. | تنتج خورازمية ديكسترا Dijkstra شجرة المسار الأقصر بدءًا من المصدر المعطى كجذر لهذه الشجرة. | ||
=== خوارزمية فلويد وارشال === | === [[Algorithms/Floyd Warshall|خوارزمية فلويد وارشال]] === | ||
تقدّم خوارزمية فلويد-وارشال Floyd-Warshall حلًّا لمشكلة المسار الأقصر لجميع الأزواج. | تقدّم خوارزمية فلويد-وارشال Floyd-Warshall حلًّا لمشكلة المسار الأقصر لجميع الأزواج. | ||
== الترتيب الطوبولوجي == | == [[Algorithms/Topological Sorting|الترتيب الطوبولوجي]] == | ||
الترتيب الطوبولوجي Topological Sorting للرسوم البيانية الموجّهة غير الدائرية، هو ترتيب خطي للرؤوس يأتي فيه الرأس | الترتيب الطوبولوجي Topological Sorting للرسوم البيانية الموجّهة غير الدائرية، هو ترتيب خطي للرؤوس يأتي فيه الرأس <code>u</code> قبل الرأس <code>v</code> في الترتيب لكل ضلع <code>u-v</code> موجّه. | ||
مراجعة 17:36، 19 أكتوبر 2019
الرسم البياني هو من بنى المعطيات غير الخطية والتي تتضمّن عقدًا nodes وأضلاع edges. تُسمّى العقد في بعض الأحيان بالرؤوس vertices والأضلاع بالخطوط lines أو الأقواس arcs التي تربط بين عقدتين في الرسم البياني.
الكشف عن وجود دورة في الرسم البياني
الهدف من هذه الخوارزمية هو الكشف عن وجود دورة في الرسم البياني الموجّه.
خوارزمية كروسكال لإيجاد الشجرة الممتدة الصغرى
تعثر هذه الخوارزمية على الشجرة الممتدة الصغرى في الرسم البياني المعطى، بترتيب الأضلاع تصاعديًا ثم اختيار الضلع الأصغر.
خوارزمية برم لإيجاد الشجرة الممتدة الصغرى
تعثر هذه الخوارزمية على الشجرة الممتدة الصغرى في الرسم البياني المعطى، وتبدأ بشجرة ممتدة فارغة وتعتمد في عملها على مجموعتين من الرؤوس.
خوارزميات إيجاد المسار الأقصر
خوارزمية بِلمان - فورد
تمتاز هذه الخوارزمية بقدرتها على إيجاد المسار الأقصر في الرسوم البيانية التي تكون فيها أوزان الأضلاع ذات قيم سالبة.
خوارزمية ديكسترا
تنتج خورازمية ديكسترا Dijkstra شجرة المسار الأقصر بدءًا من المصدر المعطى كجذر لهذه الشجرة.
خوارزمية فلويد وارشال
تقدّم خوارزمية فلويد-وارشال Floyd-Warshall حلًّا لمشكلة المسار الأقصر لجميع الأزواج.
الترتيب الطوبولوجي
الترتيب الطوبولوجي Topological Sorting للرسوم البيانية الموجّهة غير الدائرية، هو ترتيب خطي للرؤوس يأتي فيه الرأس u قبل الرأس v في الترتيب لكل ضلع u-v موجّه.