לדלג לתוכן

אלגוריתם חיפוש לרוחב – הבדלי גרסאות

אין תקציר עריכה
מ (←‏top: הגהה, replaced: צמתי ← צומתי באמצעות AWB)
אין תקציר עריכה
פלט האלגוריתם, המכונה עץ החיפוש לרוחב (BFS), מקיים את התכונה שהמסלול משורש העץ לכל אחד מהצמתים הוא המסלול בעל מספר הצלעות הנמוך ביותר בגרף המקורי, ובגרף שאינו [[גרף ממושקל]] הוא גם המסלול הקצר ביותר.
 
[[סיבוכיות]] [[סיבוכיות זמן|הזמן]] [[סיבוכיות מקום|והמקום]] של האלגוריתם בגרף קשיר כמעט לחלוטין היא <math>\ O(|V|+|E|)</math>, כאשר <math>V</math> מייצג את מספרקבוצת הצמתים בגרף ו-<math>E</math> מייצג את מספרקבוצת הקשתות בגרף.
 
==תיאור אינטואיטיבי==
משתמש אלמוני