עבור לתוכן

שאלה בגרפים(2)

Featured Replies

פורסם

לא ברור. לכאורה אם אין קשתות בגרף (הוא כולו קבוצה בלתי-תלויה), אז הפונקציה לא תעשה כלום (כי ייבחר צומת אקראי, ומשום שאין לו שכנים בכלל הוא יוחזר לבדו).

פורסם

הפתרון אכן מניח שהגרף קשיר, מה שלא מצוין בשאלה. אין בעיה להרחיב את האלגוריתם הזה גם לגרפים לא קשירים (פשוט צריך להפעיל אותו שוב ושוב על כל רכיב קשירות של הגרף).

פורסם
  • מחבר

זאת בדיוק הבעיה שלי..כנראה אז טעות.

לא נראה לי שאפשר למצו את הרכיבי קשירות כי מותר להשתמש רק בפעולות שיש שם אז לא נוכל להריץ dfs כדי למצוא את הרכיבי קשירות (כי בשביל זה צריך רשימת קודקודים ואין גישה לזה. אם הייתה אז זה נראה לי היה פשוט: היינו שמים אותם ברשימה, מכניסים את הראשון לL , צובעים את השכנים שלו בשחור וחוזרים על הפרוצדורה עם כל הקודקודים עד שכולם צבועים בשחור)

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים