חידה תכנותית: סידור של תלוית

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

לדוגמה, נתונה רשימה של שני מערכים המתארים תלויות:

[[1,0],[2,1]]

• [1,0] - משמעו ש-1 תלוי ב-0
• [2,1] - משמעו ש-2 תלוי ב-1

הדרך היחידה לסידור התלויות היא: 0 -> 1 -> 2

דוגמה נוספת. נתונה רשימה של 8 מערכים המתארים תלויות של נושאי לימוד:

[
['graph','arrays'],
['graph','dictionary'],
['bfs','graph'],
['arrays','variables'],
['dictionary','variables'],
['queue','arrays'],
['bfs','queue'],
['topological sorting','bfs']
]

הדרך לסדר את נושאי הלימוד באופן שלומדים נושא רק לאחר שקודם לומדים את הנושאים הדרושים ללימודו היא אם כן:

Variables -> Arrays -> Dictionary -> Queue -> Graph -> Bfs -> Topological sorting

וזו גם רשימת הנושאים מסודרים לפי סדר שצריך ללמוד כדי לפתור את הבעיה:

1. משתנים וערכים

2. רשימות (מערכים) של פייתון

3. מילונים בשפת פייתון

4. תורים Queue - הבנה ויישום

5. יישום תורת הגרפים בפייתון ובפרט רשימת סמיכויות

6. אלגוריתם חיפוש לרוחב BFS

7. מיון טופולוגי באמצעות אלגוריתם Kahn

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

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

להלן פתרון האתגר המבוסס על מיון טופולוגי:

def schedule(dependencies):
    """
    Computes a topological order for the given dependencies using Kahn's algorithm.

    Args:
        dependencies: A list of dependency pairs, where each pair is a list of [item, prerequisite].

    Returns:
        A list of items in topological order, or an empty list if there is a circular dependency.
    """

    # Initialize data structures
    sorted_items = []  # List to store items in topological order
    items = []  # List of all items
    in_degrees = {}  # Dictionary to store in-degree of each item
    adj_list = {}  # Adjacency list representation of dependencies

    # Process dependencies
    for item, pre in dependencies:
        if item not in items:
            items.append(item)
        if pre not in items:
            items.append(pre)

        if item in in_degrees:
            in_degrees[item] += 1
        else:
            in_degrees[item] = 1

        if pre in adj_list:
            adj_list[pre].append(item)
        else:
            adj_list[pre] = [item]

    # Identify items with no dependencies (start of topological order)
    q = []  # Queue for BFS traversal

    # Add items with no dependencies to queue and sorted list
    for item in items:
        if item not in in_degrees:
            q.append(item)
            sorted_items.append(item)  

    # Perform BFS to order items in topological order
    while q:
        # Remove the first item from the queue as it has no dependencies
        current = q.pop(0)  

        if current in adj_list:
            # Iterate through items dependent on current item
            for item in adj_list[current]:  
                if item in in_degrees and item not in sorted_items:
                    # Reduce in-degree of dependent items
                    in_degrees[item] -= 1  
                    
                    # Add items with no dependencies to queue and sorted list
                    if in_degrees[item] == 0:
                        q.append(item) 
                        sorted_items.append(item)

    # If items have circular dependency return empty list since can't be resolved
    if len(items) != len(sorted_items):
        return []

    # Return topological order
    return sorted_items

נבחן את הפונקציה schedule עם רשימות תלויות שחלקם כוללות הפניות מעגליות:

# Test cases
print(schedule([[1,0],[2,0],[3,1],[3,2]]))

print(schedule([['graph','arrays'],['graph','dictionary'],['bfs','graph'],['arrays','variables'],['dictionary','variables'],['queue','arrays'],['bfs','queue'],['topological sorting','bfs']]))

print(schedule([[1,0],[3,2],[4,3]]))  #   Disconnected graph

print(schedule([[1,0],[2,0],[3,1],[3,2],[0,1]]))   # Circular dependency

print(schedule([[1,0],[2,0],[3,1],[3,2],[0,0]]))   # Circular dependency

נסביר:

1. מתחילים ביצירת מבני נתונים שיאפשרו את סידור התלויות בסדר טופולוגי:

   • sorted_items: רשימה ריקה לצורך אחסון תלויות ע"פ סדר טופולוגי.
   • items: רשימת כל התלויות.
   • in_degrees: מילון לאחסון in degree של כל תלות.
   • adj_list: מילון לאחסון רשימת הסמיכות של יחסי התלות.

   # Initialize data structures
   sorted_items = []  # List to store items in topological order
   items = []  # List of all items
   in_degrees = {}  # Dictionary to store in-degree of each item
   adj_list = {}  # Adjacency list representation of dependencies

   מבני נתונים אלה משמשים לייצוג התלויות, היחסים ביניהם ומבנה הגרף הכללי.

2. מילוי מבני הנתונים לפני שמתחילים במעבר שיטתי באמצעות אלגוריתם סריקה BFS. במסגרת זו:

   • עוברים על רשימת יחסי התלות dependencies.
   • מוסיפים תלויות ל-items.
   • מעדכנים את in_degrees ו-adj_list עבור כל אחד מיחסי התלויות.

   # Process dependencies
   for item, pre in dependencies:
       if item not in items:
           items.append(item)
       if pre not in items:
           items.append(pre)
   
       if item in in_degrees:
           in_degrees[item] += 1
       else:
           in_degrees[item] = 1
   
       if pre in adj_list:
           adj_list[pre].append(item)
       else:
           adj_list[pre] = [item]

   בסה"כ שלב זה בונה את ייצוג הגרף ואת יתר מבני הנתונים המייצגים את התלויות באופן שניתן לפתור באמצעות אלגוריתם Kahn.

3. בשלב זה, עוברים בצורה שיטתית על הרשימה items לצורך מציאת פריטים ללא דרישות מוקדמות אותם מוסיפים לרשימה הממוינת sorted_items ולמבנה נתונים queue בשביל סריקה סדרתית בגישה של חיפוש לרוחב BFS.

   # Identify items with no dependencies (start of topological order)
   q = []  # Queue for BFS traversal
   
   # Add items with no dependencies to queue and sorted list
   for item in items:
       if item not in in_degrees:
           q.append(item)
           sorted_items.append(item) 

4. החלק העיקרי של קוד הפונקציה מבצע סריקה סדרתית בגישה של חיפוש לרוחב BFS לצורך מציאת הסדר הטופולוגי של רשימת התלויות. בשלב זה הפונקציה עושה חיפוש לרוחב (BFS), כשהיא מתחילה מפריטים ללא יחסי תלות. בכל פעם שעוברים על פריט ה-in_degree שלו פוחת, כאשר פריט ללא תלויות (in_degree שווה 0) שנותר מתווסף לתור q ולרשימת הסדר הטופולוגי sorted_items.

   # Perform BFS to order items in topological order
   while q:
       # Remove the first item from the queue as it has no dependencies
       current = q.pop(0)  
   
       if current in adj_list:
           # Iterate through items dependent on current item
           for item in adj_list[current]:  
               if item in in_degrees and item not in sorted_items:
                   # Reduce in-degree of dependent items
                   in_degrees[item] -= 1  
                       
                   # Add items with no dependencies to queue and sorted list
                   if in_degrees[item] == 0:
                       q.append(item) 
                       sorted_items.append(item)

   • מסירים את התלות הנוכחית current מראש התור q.
   • עוברים על רשימת התלויות של התלות הנוכחית adj_list[current]. בכל מעבר מפחיתים את ה-in_degree של כל תלות שעוברים עליה. במידה וin_degree הופך לאפס מוסיפים את הפריט ל-q ולרשימת הפריטים הממויינים sorted_items.

5. במידה, ובסיום הסריקה השיטתית באמצעות אלגוריתם BFS מספר הפריטים הממויינים שונה ממספר הפריטים שהוזנו לפונקציה, יש תלות מעגלית, ולכן לא ניתן למיין את הפריטים באמצעות מיון טופולוגי. במקרה זה, הפונקציה תחזיר רשימה ריקה.

6. לאחר סיום סריקת הגרף וטיפול ביחסי תלות מעגליים, הפונקציה מחזירה רשימה sorted_items בה הפריטים ממויינים בסדר טופולוגי כפלט סופי.

בסך הכל, הקוד מיישם באופן יעיל את האלגוריתם של קאהן למציאת הסדר הטופולוגי של פריטים בהתבסס על יחסי התלות שלהם. הוא מטפל כראוי במקרים ללא יחסי תלות, יחסי תלות מרובים ויחסי תלות מעגליים.

הערכת ביצועים

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

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

• in_degrees: O(V)
• adj_list: O(E)
• q: O(V)
• sorted_items: O(V)
• items: O(V)

לכן, סיבוכיות המקום הכוללת היא:

O(in_degrees) + O(adj_list) + O(q) + O(sorted_items) + O(items) = O(V + E)

סיבוכיות המקום היא לפיכך:

O(V + E)

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

יישום תורת הגרפים בפייתון ובפרט רשימת סמיכויות

אלגוריתם חיפוש לרוחב BFS

מיון טופולוגי באמצעות אלגוריתם Kahn

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים