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