אלגוריתמי חיפוש בגרפים
חקרו אלגוריתמי סריקת גרפים ומסלולים קצרים ביותר
אלגוריתמי חיפוש בגרפים מיושמים בניווט GPS, רשתות חברתיות, ניתוח תלויות ועוד. BFS מוצא את המסלול הקצר ביותר במספר צלעות וטוב לגרפים לא ממושקלים. DFS חוקר לעומק ומשמש לזיהוי מחזורים ומיון טופולוגי. אלגוריתם דייקסטרה מוצא מסלול קצר ביותר בגרף ממושקל עם משקלים חיוביים. A* מוסיף היוריסטיקה לדייקסטרה לחיפוש יעיל יותר כשיש מידע מרחבי.
גרף:
לא ביקרו
נוכחי
חזית
ביקרו
מסלול
התחלה
יעד
🔍 מה קורה עכשיו?
לחצו על הפעל או שלב כדי להתחיל את האלגוריתם.
שלב
1 / 0
פסאודו-קוד
1queue.enqueue(start)
2visited.add(start)
3while queue is not empty:
4 node = queue.dequeue()
5 if node == target: return path
6 for each neighbor of node:
7 if neighbor not visited:
8 visited.add(neighbor)
9 queue.enqueue(neighbor)
חיפוש לרוחב (BFS)
איך זה עובד
חוקר את כל השכנים בעומק הנוכחי לפני שעובר לצמתים בעומק הבא. משתמש במבנה נתונים תור (FIFO).
💡 הרעיון המרכזי
חקרו שכבה אחר שכבה, כמו אדוות המתפשטות מאבן שנזרקה למים.
סיבוכיות
זמן
O(V + E)
מקום
O(V)
מסלול קצר ביותר: true
מתי להשתמש
מציאת מסלול קצר ביותר בגרפים לא ממושקלים, סריקה לפי רמות, בדיקת קישוריות.
🎓 קוויז לימודי - חיפוש לרוחב (BFS)
ציון: 0 / 5שאלה 1 מתוך 5
באיזה מבנה נתונים משתמש BFS לניהול הצמתים שיש לבקר?