שאלה למי שיודע

[ohanonbar]

אשמח לתשובות על השאלות:
1.מהו זמן הריצה של BFS כשאר גרף הקלט הוא מיוצג עי מטריצה והאלגוריתם מותאם לגרף כזה?
2.כתוב אלגוריתם יעיל הקובע האם גרף בילתי מכוון הוא דו צדדי.
תודה רבה

[TA_Yoni]

1. כשמדברים על BFS אנו מניחים כי הייצוג הוא ברשימת שכנויות ולכן זמן הריצה יהיה (O(E+V . על מטריצה לא דברנו אך הזמן ריצה יכול להיות V^2.
 2. יש לבצע סריקת BFS על הגרף. אם נגלה קשת מקודקוד u לקודקוד v כך ש [d[v] = d[u, אז הגרף הוא לא דו צדדי. אחרת הגרף הוא דו צדדי והחלוקה המתאימה תתקבל לפי הזוגיות של הרמות (= שדה ה d )
קודקודים ברמה זוגית יהיו בקבוצה הראשונה וקודקודים ברמה אי זוגית יהיו בקבוצה השניה.

למה זה נכון?
מכיוון שהגרף קשיר , ניתן להגיע מכל קודקוד לכל קודקוד. כדי לקבל גרף דו חלקי צריך לחלק את הקודקודים לשתי קבוצות V ו U כך שהצלעות של הגרף הן מקודקודים u שב U לקודקודים v שב V. לכן אם סורקים את הגרף לפי שכבות מקודקוד מסויים s ונניח כי s ב U , כל הקודקודים בשכבה הראשונה חייבים להיות ב V , לאחר מכן כל הקודקודים בשכבה השנייה חייבים להיות ב V , לאחר מכן כל הקודקודים בשכבה השלישית חייבים להיות ב U וכן הלאה.... אם יש צלע בין קודקודים באותה שכבה ברור כי הגרף אינו דו-צדדי.

[TA_Yoni]

טעות\תיקון:
1. התייחסנו לגרף כאל רשימת שכנויות וכך אם לא מצוין אחרת מדובר ברשימת שכנויות. אנחנו בד"כ לא מתעסקים בייצוגים אחרים ולכן שאלת הייצוג אינה חשובה
2. התייחסתי לגרף כקשיר וזה לא מה ששאלת.
אם הגרף לא קשיר הבדיקה תעשה רק עבור כל זוג קדקדים שבאותו רכיב קשירות.

[ohanonbar]

תודה יוני