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

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