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