האלגוריתם של קרוסקל
מתוך ויקיפדיה, האנציקלופדיה החופשית
האלגוריתם של קרוסקל הוא אלגוריתם חמדן לפתרון בעיית מציאת עץ פורש מינימלי בגרף לא מכוון.
לפי אלגוריתם זה, כדי לבחור את הקשתות שיימצאו בעץ פורש מינימלי, יש למיינן למי משקליהן תחילה. אחר כך יש ליטול לפי הסדר קשת אחר קשת ולהוסיפה לעץ, מהקשת המינימלית עד לקשת הגדולה ביותר במשקלה, כל עוד לא יווצר מעגל בגרף המתקבל.
האלגוריתם הוא חמדן, כיוון שבכל צעד נבחרת הפעולה הנראית אופטימלית באותו שלב - נוטלים את הקשת שמשקלה הקטן ביותר.
סיבוכיות האלגוריתם מושפעת בעיקר מהצורך למיין את הקשתות בתחילת הפעלתו, ועל כן היא חסומה על ידי 
, הסיבוכיות המינימלית למיון מבוסס השוואות של 
מספרים. ( מייצג את מספר הקשתות בגרף.)
