אני מתקשה מאוד עם שאלה 2:
נתון גרף ממושקל G=(V,E) שבו משקל כל קשת הוא 1 או 2. הציעו אלגוריתם המוצא עפ"מ בזמן O(V+E).
אין לי ממש כיוון.
חשבתי על BFS או DFS, אבל אני לא חושבת שזה יעזור לי איכשהו, כי גם אם אני אשנה את האלגוריתם איכשהו אני אצטרך להוכיח שהעץ שקיבלתי הוא מינימום, וזה נראה לי בכלל בכלל לא טריויאלי, כמו שההוכחה של DFS ו-BFS לא טריויאלית.
להשתמש בקרוסקל או פרים - אני חושבת שזה בעייתי מבחינת הסיבוכיות (אגב, מה יותר גדול? E+V או ElogV? אני מניחה מהשאלה ש-ElogV, אחרת אפשר לפתור את זה עם קרוסקל/פרים, אבל לא ממש ברור לי למה...)
בקיצור, אין לי ממש כיוון, אז אשמח לעזרה, כי ההגשה למחר בלילה....
תודה!
