خوارزمية كروسكال
Sign in to saveminimum spanning forest algorithm that greedily adds edges
Key facts
- Class
- Minimum spanning tree algorithm
- Data structure
- Graph
- Worst case performance
- O ( | E | log | V | ) {\displaystyle O(|E|\log |V|)}
via Wikipedia infobox
Wikidata facts
- Named after
- Joseph Kruskal
- Image
- MST kruskal en.gif
Show 6 more facts
- Commons category
- Kruskal's algorithm
- Stack Exchange tag
- stackoverflow.com/tags/kruskals-algorithm
- publication date
- 1956-00-00
- discoverer or inventor
- Joseph Kruskal
- computes solution to
- minimum spanning tree
Sources (2)
via Wikidata · CC0
Article · العربية
خوارزمية كروسكال (بالإنجليزية: Kruskal Algorithm) هي خوارزمية لإيجاد الطريق ذي الوزن الأقل أو الأقل كلفة، وهي خوارزمية شرهة في نظرية المخططات حيث تجد الطريق الأقل وزن لمخطط متصل موزون، بإضافة الكلفة في كل مرحلة، وهذا يعني أنها توجد المجموعات الجزئية التي تحتوي على الخط الواصل بين عقدتين الذي يكون الشجرة التي تحتوي على جميع العقد، حيث يتم تقليل المجموع الكلي لأوزان الخطوط الواصلة بين العقد في هذه الشجرة لأقل ما يمكن. إذا كان المخطط غير متصل سيقوم بإيجاد الشجرة التي تحتوي على اقل كلفة لكل شجرة في الغابة. ظهرت هذه الخوارزمية لأول مرة في وقائع المجتمع الأمريكي للرياضيين عام 1956 وكتبها .
Abstract from DBpedia / Wikipedia · CC BY-SA