גרפים
גרפים
- גרף הוא קבוצת צמתים (נקראים גם קודקודים) המחוברים על ידי קשרים (חיבורים).
- גרפים מדמים רשתות: חברים, כבישים בין ערים, לינקים בין דפי אינטרנט.
- עץ הוא למעשה גרף מיוחד; גרף כללי יכול להכיל מחזוריות וריבים רבים לכל צומת.
ייצוג גרף: רשימת סמוכים
- אחת הדרכים הנפוצות היא רשימת סמוכים: מפתח שמייצגת כל צומת לרשימת הסמוכים שלו.
graph["A"]היא הרשימה של הצמתים המחוברים ישירות לA.- זהו ייצוג מצומצם כאשר לכל צומת יש רק מעט חיבורים.
# A graph as a dict: each node maps to its list of neighbours
graph = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A"],
}
print(graph["A"]) # ['B', 'C'] -- A connects to B and C
print(graph["B"]) # ['A']
הוספת קשר
- בגרף לא מכוון, קשר
A—Bהולך בשני הכיוונים. - לכן, הוספתו אומרת להוסיף
BלרשימתAוגםAלרשימתB. - אם צומת חדש נמצא, התחל אותו ברשימה ריקה תחילה.
def add_edge(graph, a, b):
if a not in graph:
graph[a] = []
if b not in graph:
graph[b] = []
graph[a].append(b)
graph[b].append(a)
graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "A", "C")
print(graph) # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
סיור בסמוכים
- כדי לסרוק מהצומת, קרא את רשימת הסמוכים שלו ובקר בכל אחד מהם.
- לצומת שאינו קיים בגרף אין אין סמוכים — החזר רשימה ריקה, לא שגיאה.
- חיפוש זה בסמוכים הוא השלב הראשון בעבודות גדולות יותר כמו סריקה של כל הגרף.
מכוון מול לא מכוון
- בגרף לא מכוון קצה פועל בשני הכיוונים (כמו חברות).
- בגרף מכוון קצה מצביע בכיוון אחד בלבד (כמו רחוב חד-כיווני, או קישור "עוקב אחר").
- עבור קצוות מכוונים תוסיף רק בכיוון אחד.
טעויות נפוצות
- גרף הוא נקודות מחוברות על ידי קצוות; קצה יכול להיות חד-כיווני או דו-כיווני.
- עץ הוא גרף ללא מחזוריות — אל תבלבל בין השניים.
כעת תנסו בעצמכם
- בנה את פעולות רשימת הסמיכות:
add_edge,neighboursוcount_edges. - כל משימה בודקת את הפונקציה שלך בגרף קטן.
- לחץ על בדיקת תשובה כדי לבדוק אותה.
רמת קושי 5/5 · 400 מטבעות + בונוס קטן בהשלמה הראשונה היום
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b אל graph[a] וגם a אל graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 5/5 · 400 מטבעות + בונוס קטן בהשלמה הראשונה היום
Write neighbours(graph, node) that returns the list of nodes directly connected to node. If node is not in the graph, return an empty list [] (do not raise an error).
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 5/5 · 400 מטבעות + בונוס קטן בהשלמה הראשונה היום
Write count_edges(graph) for an undirected graph: count how many edges it has. Add up the lengths of every neighbour list, then divide by 2 (each edge is stored in both nodes' lists). Example: a triangle A–B–C has 3 edges.
לחץ על הרץ כדי לראות את התוצא כאן.