שאלה + ניסיון פתרון
נתון גרף מכוון (G = (V,E שמיוצג ע"י רשימת שכנות.
תאר אלגוריתם יעיל ככל האפשר, שמחשב את הקבוצה U (שמוכלת ב-V) של הצמתים u in U, בעלי התכונה שלכל v in V קיימת מסילה מכוונת מ-u ל-v.
ניסיון פתרון:
1. נמצא את גרף הרכיבים הקשירים היטב ע"י שתיי הפעלות של dfs.
2. נבצע מיון טופולוגי על גרף הרכיבים הקשירים היטב. נקבל סידור לינארי של קדקדי גרף הרכיבים הקשירים היטב.
3. נבצע bfs עם הקדקד השמאלי ביותר במיון הטופולוגי.
4. אם כל קדקדי גרף הרכיבים הקשירים היטב נסרקו ע"י ה-bfs, אזי יש מסלול מהקדקד השמאלי ביותר במיון, לכל שאר הקדקדים (כלומר לכל שאר הרכיבים הקשירים היטב), ולכן הקדקדים ששייכים לרכיב הקשיר היטב השמאלי ביותר במיון, הוא הקבוצה המבוקשת.
האם האלגוריתם הזה נכון?
תודה מראש.
נתון גרף מכוון (G = (V,E שמיוצג ע"י רשימת שכנות.
תאר אלגוריתם יעיל ככל האפשר, שמחשב את הקבוצה U (שמוכלת ב-V) של הצמתים u in U, בעלי התכונה שלכל v in V קיימת מסילה מכוונת מ-u ל-v.
ניסיון פתרון:
1. נמצא את גרף הרכיבים הקשירים היטב ע"י שתיי הפעלות של dfs.
2. נבצע מיון טופולוגי על גרף הרכיבים הקשירים היטב. נקבל סידור לינארי של קדקדי גרף הרכיבים הקשירים היטב.
3. נבצע bfs עם הקדקד השמאלי ביותר במיון הטופולוגי.
4. אם כל קדקדי גרף הרכיבים הקשירים היטב נסרקו ע"י ה-bfs, אזי יש מסלול מהקדקד השמאלי ביותר במיון, לכל שאר הקדקדים (כלומר לכל שאר הרכיבים הקשירים היטב), ולכן הקדקדים ששייכים לרכיב הקשיר היטב השמאלי ביותר במיון, הוא הקבוצה המבוקשת.
האם האלגוריתם הזה נכון?
תודה מראש.
