בעיה

[revision]

בעיה

אני צריך לפתור את הבעיה הבאה: יש גרף מכוון(G(V,E בצורה רשימת סמיכויות עם קשתות מקבילות ולולאות עצמיות.אני צריך למצוא אלגוריתם בזמן(O(V+E שיצור גרף לא מכוון ללא קשתות מקבילות ולולאות עצמיות בצורת רשימת סמיכויות. אם הרשימות ממויונות אפשר לעשות את זה ע"י מעבר יחיד על כול קשת. העיניין הוא שלא ברור לי איך אני יכול למיין את רשימות הקשתות בלי לפגוע בדרישות הסיבוכיות כי המיון של כול רשימה צריך להיות לינארי באורך הרשימה.

 

[vinney]

תזכיר לי מה זה בדיוק

אם אני לא טועה, רשימת סיכויות זה רשימה לכל קודקוד מה הקודקודים הסמוכים אליו נכון? כי אם כך אתה עושה את זה במעבר אחד בו אתה עובר על כל הרשומות, על כל אחת מהן, יעני בדיוק E+V. במעבר על הקודקודים הסמוכים, אתה יכול מיד לחסל את הקשתות העצמיות (קודקודים שמופיעים ברשימות של עצמם - נמחקים בהינף יד), ואילו בשביל קשתות מקבילות תצטרך להחזיק מערך עזר בגודל V*V. זה בשלוף, בטח אפשר לשפר את זה... תקן אותי אם אני טועה

 

[revision]

אתה לא טועה

אבל הפיתרון שהצעת לא מתאים.תודה בכול מקרה. מערך עזר בגודל שהצעת כבר הורס את הסיבוכיות. מה שעושים זה להעתיק את כול הרשומות למערך שכול כניסה במערך מכילה קודקוד יעד שהוא קודקוד מרשימה ואת הקודקוד המקור שלו שהוא הקודקוד אליו הרשימה היתה מחוברת. ואז ממינים את המערך בCOUNTING SORT לפי קודקודי היעד ואת המערך שמתקבל ממינים לפי קודקודי המקור. המיון יציב כך שמקבלים את כול הקשתות ממויונות כמו שצריך ועל זה אפשר כבר לעבור.

 

[vinney]

הסבר קצר

מה זה counting sort? ואת ההצעה שלי אפשר ליעל כך שבמקום מערך V*V תשתמש בוקטור בגודל V, וזה לא הורס לך את הסיבוכיות.

 

[revision]

הסבר

COUNTING SORT זה מיון על מערך בגודל N שבהינתן שהמפתח הגדול ביותר במערך הוא K (והמפתחות הם מספרים שלמים) הוא מבצע את המיון בסיבוכיות של (o(N+K כך אם מעתיקים את הקשתות למערך הגודל E אפשר לבצע עליו מיון ב-(o(E+V מבלי לפגוע בסיבוכיות.המיון הזה הוא גם יציב כלומר הוא שומר על הסדר בין איברים זהים.אם נמיין את קודקודי המקור נקבל מערך.אם נמיין את המערך הזה לפי קודקודי היעד נקבל מערך נוסף. מערך זה מכיל בדיוק את קודקודי המקור ממיונים אחד יחסית לשני וגם בינם לבין עצמם לפי קודקודי היעד שלהם. על ידי מעבר על 2 המערכים ניתן לקבל את הגרף המבוקש. וקטור באורך V לא יעזור לזכור אילו צמתים כבר קושרו בגרף בכול שלב - בגרף היעד צריכה להיות לכול היותר קשת אחת בין 2 צמתים.

 

[vinney]

אוקיי

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