الرسوم البيانية (Graphs) في كل مكان
في هذا الدرس 11 موضوعات
هذا الدرس متاح حاليًا باللغة الإنجليزية فقط، ولم تُنشر نسخته العربية بعد.
Lesson Overview
You have worked with lists, hash maps, and trees. Each organizes data in a fixed shape: a line, a table of buckets, a hierarchy with one root. Many real problems do not fit those shapes. A metro map has stations joined by tracks in no particular order. A group of friends links to each other in every direction. Software libraries depend on each other in tangled ways. The structure that describes all of these is the graph.
This lesson is about vocabulary and recognition, with no new code. You will learn what a graph is made of (nodes and edges), the difference between undirected and directed edges, what a path and a cycle are, and why a tree is just a special graph. We use a metro map as the running picture for the whole module.
Why this matters: backend systems are full of graphs. Services call other services, build tools order libraries, and networks route packets. Spotting "this is a graph problem" is half of solving it.
This lesson builds on the tree lessons of the previous module (nodes, parents, children, edges) and needs nothing else.
Learning Objectives
By the end of this lesson you will be able to:
- Define a graph as a set of nodes joined by edges.
- Tell undirected edges from directed edges and choose the right one for a relationship.
- Define path, cycle, and neighbor, and find them in a small drawing.
- Explain why a tree is a graph with no cycles and one root.
- Recognize graphs in maps, social networks, web links, software dependencies, and service calls.
- Name the nodes and edges of a real-world situation.
Written Explanation
What a graph is
A graph is a set of nodes (also called vertices) together with a set of edges, where each edge links a pair of nodes. That is the whole definition. Graphs are usually drawn as dots (nodes) joined by lines (edges). This matches the standard mathematical description of a graph as objects where some pairs are linked.
Take the metro picture. Each station is a node. Each stretch of track between two neighboring stations is an edge.
Airport --- Center --- Market
|
StadiumThis graph has four nodes (Airport, Center, Market, Stadium) and three edges (Airport-Center, Center-Market, Center-Stadium). Two nodes joined by an edge are neighbors: Center has three neighbors, Airport has one.
Notice what is missing from the definition: there is no "first" node, no "parent", no "left" or "right". Unlike a tree, a graph has no built-in start. Any node can be where you begin.
Undirected and directed edges
An edge can work in two ways.
- An undirected edge goes both ways. A metro track is usable in both directions, and a friendship on most social networks is mutual. If Airport-Center is an edge, you can ride from Airport to Center and from Center to Airport.
- A directed edge goes one way only. A one-way street is directed. So is "follows" on a platform where following does not have to be returned, and so is "needs" in "library App needs library Web".
We draw a directed edge as an arrow. A graph whose edges are all directed is a directed graph.
App ---> Web ---> CoreHere App needs Web, and Web needs Core. The arrow from App to Web says nothing about whether Web needs App. When you model a situation, ask one question about each relationship: "If A is linked to B, is B automatically linked to A?" If yes, use undirected edges. If not, use directed edges.
Paths and cycles
A path is a sequence of nodes where each consecutive pair is joined by an edge. In the metro graph above, Airport, Center, Market is a path of two edges. The length of a path, in this module, is its number of edges. Airport to Market takes two edges, which a rider would call two stops after the starting station.
In a directed graph a path must follow the arrows. App, Web, Core is a path. Core, Web, App is not, because the edges point the other way.
A cycle is a path that returns to its starting node. Add a track between Market and Stadium to the metro:
Airport --- Center --- Market
| |
+-- Stadium +Now Center, Market, Stadium, Center is a cycle: you can leave Center and come back without reusing the same stretch of track. In a directed graph the arrows must all point along the loop. If library A needs B, B needs C, and C needs A, that is a directed cycle, and you will see in Lesson 5 why it is a problem.
A graph can also fall into separate pieces. If an island has its own tiny metro with two stations and no track to the mainland, there is no path between the mainland and the island. Remember this case: later lessons must handle "unreachable" without crashing.
Where a tree fits
In the previous module you worked with trees. A tree is a graph too: nodes are the tree nodes and edges are the parent-child links. What makes it special is that it has no cycles and one root from which every other node is reached by exactly one path. A graph is the general shape; a tree is the well-behaved special case. Because every non-root node in a tree has exactly one parent, a tree with n nodes has n - 1 edges.
The reverse does not hold. Our four-station metro with the extra Market-Stadium track has a cycle, so it is not a tree. Graphs are what you need whenever data can link back on itself or have several routes between the same two points.
Graphs you already use
| Situation | Nodes | Edges | Directed? |
|---|---|---|---|
| Metro or road map | Stations, junctions | Track or road segments | Usually undirected, except one-way streets |
| Friendship network | People | "is friends with" | Undirected |
| Follower network | Accounts | "follows" | Directed |
| Web links | Pages | A link from one page to another | Directed |
| Software dependencies | Libraries or modules | "needs" | Directed |
| Microservice calls | Services | "calls" | Directed |
The same structure appears in very different places. That is why a handful of graph techniques solve so many problems.
Examples
Example 1: a four-station map (simple)
Stations: Airport, Center, Market, Stadium. Tracks: Airport-Center, Center-Market, Center-Stadium.
- Nodes: 4. Edges: 3. All edges are undirected.
- Neighbors of Center: Airport, Market, Stadium.
- A path from Airport to Stadium: Airport, Center, Stadium (two edges).
- Cycles: none. With four nodes and three edges, all connected, this graph is also a tree if you pick any station as the root.
Example 2: a build-order graph (practical)
Three libraries: App needs Web, App needs Core, Web needs Core.
App ---> Web ---> Core
| ^
+------------------+The nodes are App, Web, and Core; there are three directed edges. The paths from App to Core are App, Core (one edge) and App, Web, Core (two edges). There is no cycle, so a valid build order exists: Core first, then Web, then App. A graph like this one, directed with no cycle, is exactly what a build tool needs. If we added "Core needs App", every library would be waiting for another and nothing could start.
Example 3: services in a shop backend (realistic)
A small online shop has services: Gateway, Orders, Users, Payments, Bank.
- Gateway calls Orders and Users.
- Orders calls Payments and Users.
- Payments calls Bank.
Model it as a directed graph with five nodes and five edges. Questions a graph can answer:
- If Bank is slow, which services are affected? Follow the arrows backward from Bank: Payments, then Orders, then Gateway. Users is not on that path.
- Which service is called most directly? Users has two incoming edges, from Gateway and Orders.
- Is there a cycle? No. If Users called Orders there would be one (Orders calls Users, Users calls Orders), and a request could wait on itself forever.
Engineers draw these service maps for exactly this kind of reasoning.
Backend Insight
Almost every large backend is a graph in disguise. Services call other services. Database tables reference each other through foreign keys. Package managers resolve libraries that need other libraries. Networks route traffic along links between machines. When something fails, the useful question is rarely "which one thing broke" but "what is connected to it".
Two habits will serve you well from here on. First, before writing code, decide what the nodes are and what the edges mean, and whether the edges are directed. A wrong choice here (treating a one-way relationship as two-way) gives wrong answers no matter how good the code is. Second, always ask whether the graph can contain cycles. Cycles are the reason graph code needs extra care, as the next lessons show.
Later in the roadmap, mapping dependencies and service graphs comes back as a professional skill. This module gives you the vocabulary and the core algorithms behind it.
Common Mistakes
Mistake 1: Calling every graph a tree
- Incorrect: "My metro map is a tree, so I can start from the root."
- Correct: "A metro map has loops and no root, so it is a general graph."
A tree has one root and no cycles. If your data has a cycle or several routes between two nodes, use graph thinking.
Mistake 2: Using undirected edges for one-way relationships
"A depends on B" does not mean "B depends on A". Treating it as undirected hides the direction, and you can no longer tell what needs what or detect a bad cycle.
Mistake 3: Mixing up edges and nodes
Stations are nodes, tracks are edges. When you count "how many stops", you count edges on the path (or stations after the start, depending on how you phrase it). Always say which you mean.
Mistake 4: Assuming every two nodes are connected
A graph can have separate pieces. An island with its own metro is a valid part of the graph, but you cannot travel from the mainland to it. Always consider the "no path" case.
Exercises
Try each exercise yourself before opening the solutions.
Level A: Foundation
A1. In your own words, define node, edge, and neighbor.
أظهر الحل A1
A1. A node is one item in the graph (a station, a person, a library). An edge is a link between two nodes. Neighbors are two nodes joined by an edge.
A2. An undirected graph has edges 1-2, 2-3, 3-1, and 3-4. How many nodes and edges does it have? Is there a cycle?
أظهر الحل A2
A2. There are 4 nodes and 4 edges. Yes: 1, 2, 3, 1 is a cycle.
A3. Say whether each relationship is better modeled as directed or undirected: (a) "is married to", (b) "sends money to", (c) "is a coworker of", (d) "must be completed before" (tasks).
أظهر الحل A3
A3. (a) undirected, because it is mutual. (b) directed, because money flows one way. (c) undirected. (d) directed: "A before B" does not mean "B before A".
Level B: Application
B1. Directed edges: Web -> Core, App -> Web, App -> Db, Db -> Core. List every path from App to Core.
أظهر الحل B1
B1. App, Db, Core; and App, Web, Core. Two paths of two edges each. Db does not lead to Web, so there are no other paths.
B2. Which of these edge sets, on nodes P, Q, R, S, form a tree? (i) P-Q, Q-R, R-S. (ii) P-Q, Q-R, R-P, R-S. (iii) P-Q, R-S.
أظهر الحل B2
B2. Only (i). It has four nodes, three edges, is connected, and has no cycle. (ii) has a cycle P, Q, R, P. (iii) is two separate pieces, so it is not one tree.
B3. A school has students and clubs. A student can belong to many clubs and a club has many students. Describe the nodes and the edges, and say whether the edges are directed.
أظهر الحل B3
B3. Nodes: students and clubs. Edge: "student belongs to club". The relationship goes both ways in meaning, so you may draw it undirected. This graph has two kinds of nodes and edges only join a student to a club.
Level C: Challenge
C1. Directed edges: A -> B, B -> C, C -> D, D -> B. Is there a cycle? Name it. Can you reach A from D?
أظهر الحل C1
C1. Yes: B -> C -> D -> B is a directed cycle. No, you cannot reach A from D: the only edge touching A points out of A, and no edge enters it.
C2. A flight map has airports X, Y, Z, W. Flights: X to Y, Y to Z, Z to X, X to W. A traveler at W wants to reach Y. Is there a path? What does this say about modeling flights as directed edges?
أظهر الحل C2
C2. No. The only flight touching W is X to W, which goes into W, so nothing leaves W and there is no path from W to Y. Direction matters. If flights were modeled as undirected, W to X to Y would look possible, and the model would be wrong for one-way routes.
Mini Challenge
Choose a system you know well: your phone's contacts, a game with levels that unlock others, a city bus network, or a school timetable. On paper:
- Say what the nodes are and what the edges mean.
- Say whether the edges are directed, and why.
- Draw at least five nodes and five edges.
- Point to one path of at least three edges, and to a cycle if your graph has one. If it has none, add one edge that would create one.
- Mark one node that cannot be reached from some other node (or explain why every node is reachable).
Check your work: you counted nodes and edges separately, you justified direction, and you found a path and a cycle (or created one).
Summary & Next Lesson
Key takeaways
- A graph is a set of nodes (vertices) joined by edges.
- Edges are undirected (both ways) or directed (one way). Choose by asking whether "A linked to B" implies "B linked to A".
- A path is a sequence of edges between two nodes. A cycle is a path that returns to its start.
- A tree is a graph with no cycles and one root. A graph can have cycles, many routes, and separate pieces.
- Maps, networks, links, dependencies, and service calls are all graphs.
Next lesson
The next lesson, "Representing graphs", shows how to store a graph in Java: the adjacency list and the adjacency matrix, and why the list is the usual choice.
Self-check
- What are the two parts of every graph?
- Is "follows" directed or undirected on a platform where following need not be returned?
- What is a cycle?
- Why is a metro map with a loop not a tree?
- Name two real systems that are graphs.
أظهر الإجابات
- Nodes (vertices) and edges.
- Directed.
- A path that returns to its starting node.
- A tree has no cycles, and a loop is a cycle.
- For example a road network and software library dependencies (also social networks, web links, service calls).
References
- Wikipedia, Graph (discrete mathematics)). Supports the definition of vertices and edges, the undirected versus directed distinction, cycles, and examples such as social networks and road networks. Treat it as a general reference, not a formal textbook.
- The statement that a tree with n nodes has n - 1 edges follows from the previous module's rule that each non-root node has exactly one parent; it was not separately sourced here.
- The metro, shop-services, and library examples are this course's own teaching examples.
التطبيق
طبّق هذا الدرس بمختبر الوحدة وتمارينها واختبارها.
تعليم الدرس كمكتمل اختياري ويمكنك التراجع عنه في أي وقت. يبقى تقدمك محفوظًا في هذا المتصفح.