Graphs · גרפים
Graphs
- A graph is a set of nodes (also called vertices) joined by edges (connections).
- Graphs model networks: friends, roads between cities, links between web pages.
- A tree is really a special graph; a general graph can have cycles and many links per node.
גרפים
- גרף הוא קבוצת צמתים (נקראים גם קודקודים) המחוברים על ידי קשרים (חיבורים).
- גרפים מדמים רשתות: חברים, כבישים בין ערים, לינקים בין דפי אינטרנט.
- עץ הוא למעשה גרף מיוחד; גרף כללי יכול להכיל מחזוריות וריבים רבים לכל צומת.
Representing a graph: adjacency list
- One common way is an adjacency list: a dictionary mapping each node to its list of neighbours.
graph["A"]is the list of nodes directly connected toA.- This is compact when each node has only a few connections.
ייצוג גרף: רשימת סמוכים
- אחת הדרכים הנפוצות היא רשימת סמוכים: מפתח שמייצגת כל צומת לרשימת הסמוכים שלו.
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']
Adding an edge
- In an undirected graph, an edge
A—Bgoes both ways. - So adding it means appending
BtoA's list andAtoB's list. - If a node is new, start it with an empty list first.
הוספת קשר
- בגרף לא מכוון, קשר
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']}
Walking the neighbours
- To explore from a node, you read its neighbour list and visit each one.
- A node that is not in the graph has no neighbours — return an empty list, not an error.
- This neighbour lookup is the first step of bigger jobs like searching the whole graph.
סיור בסמוכים
- כדי לסרוק מהצומת, קרא את רשימת הסמוכים שלו ובקר בכל אחד מהם.
- לצומת שאינו קיים בגרף אין אין סמוכים — החזר רשימה ריקה, לא שגיאה.
- חיפוש זה בסמוכים הוא השלב הראשון בעבודות גדולות יותר כמו סריקה של כל הגרף.
Directed vs undirected
- In an undirected graph an edge works both ways (a friendship).
- In a directed graph an edge points one way only (a one-way street, a "follows" link).
- For directed edges you would append in one direction only.
מכוון מול לא מכוון
- בגרף לא מכוון קצה פועל בשני הכיוונים (כמו חברות).
- בגרף מכוון קצה מצביע בכיוון אחד בלבד (כמו רחוב חד-כיווני, או קישור "עוקב אחר").
- עבור קצוות מכוונים תוסיף רק בכיוון אחד.
Common mistakes
- A graph is nodes joined by edges; an edge can be one-way or two-way.
- A tree is a graph with no cycles — do not confuse the two.
טעויות נפוצות
- גרף הוא נקודות מחוברות על ידי קצוות; קצה יכול להיות חד-כיווני או דו-כיווני.
- עץ הוא גרף ללא מחזוריות — אל תבלבל בין השניים.
Now you try
- Build the adjacency-list operations:
add_edge,neighbours, andcount_edges. - Each task checks your function on a small graph.
- Press Check answer to test it.
כעת תנסו בעצמכם
- בנה את פעולות רשימת הסמיכות:
add_edge,neighboursוcount_edges. - כל משימה בודקת את הפונקציה שלך בגרף קטן.
- לחץ על בדיקת תשובה כדי לבדוק אותה.
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b to graph[a] and a to graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place. · כתוב add_edge(graph, a, b) לגרף ללא כיוון מאוחסן כמילון של רשימות שכנים. הוסף b לgraph[a] והוסף a לgraph[b]. אם צומת אינו בגרף עוד, תן לו רשימה ריקה [] קודם. שנה את המילון במקום.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
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). · כתוב neighbours(graph, node) שמחזיר את רשימת הצמתים המקושרים ישירות ל-node. אם node אינו בגרף, החזר רשימה ריקה [] (אל תגרום לשגיאה).
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
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. · כתוב count_edges(graph) לגרף ללא כיוון: ספור כמה קשרים יש בו. סכום את אורכי כל רשימת השכנים, ואז חלק ב-2 (כל קשר מאוחסן ברשימות של שני הצמתים). דוגמה: משולש A–B–C יש לו 3 קשרים.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.