🗺️ धडा 10 — Graphs: कॉरिडॉरचा नकाशा

📍 तुम्ही इथे आहात: 12 पैकी धडा 10 · पुढे: lesson-11-dp-greedy

📦 या ब्रँचमध्ये काय आहे

धडे 01–10. खोल्या आणि कॉरिडॉर, दोन मूलभूत चाली, अंतर मोजणारी चाल, आणि cycle ओळखणे.

dsa/structures.py — adjacency list म्हणून Graph, weighted, directed किंवा नाही
dsa/algorithms.py — bfs, dfs, dijkstra, has_cycle
dsa/demo.py — graphs: सहा खोल्या, तीन प्रश्न

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

शाळा म्हणजे कॉरिडॉरनी जोडलेल्या खोल्या — हाच graph. कार्यालयापासून शोध घेण्याच्या तीन पद्धती: BFS पसरत जातो — एका कॉरिडॉर अंतरावरच्या सगळ्या खोल्या, मग दोन, मग तीन (भेट द्यायच्या खोल्यांची जेवणासारखी रांग) — म्हणून एखाद्या खोलीत पहिल्यांदा पोहोचता तेव्हा ते सर्वात कमी कॉरिडॉरमधून असते. DFS एक कॉरिडॉर अगदी शेवटपर्यंत धरतो, मग मागे येऊन पुढचा करून पाहतो (पर्यायांची चळत). Dijkstra मोजतो — कॉरिडॉरना लांबी असते, म्हणून आतापर्यंत माहीत असलेली सर्वात लहान चाल नेहमी पुढे वाढवा (चालींचे व्यासपीठ). आधी पाहिलेल्या खोलीकडे परत नेणारा कॉरिडॉर म्हणजे cycle.

🗺️ आकृती

flowchart LR
  O["office"] ---|20| H["hall"]
  H ---|30| L["lab"] ; H ---|10| B["library"]
  B ---|60| G["gym"] ; L ---|15| G
  G ---|40| F["field"]

❓ काय

मांडणी: adjacency list {room: [(neighbour, weight)]} — O(V + E) memory; दाट graphs साठी adjacency matrix.
BFS: queue; O(V + E); hops मध्ये सर्वात लहान path; level order.
DFS: recursion किंवा stack; O(V + E); reachability, cycles, topological order, backtracking.
Dijkstra: (distance, room) चा min-heap; O(E log V); weight नुसार सर्वात लहान path; negative कॉरिडॉर चालत नाहीत (ते Bellman-Ford हाताळतो).
Cycle (undirected): आधीच पाहिलेला असा शेजारी जो parent नाही. Topological sort: प्रत्येक कॉरिडॉर पुढेच दाखवेल अशा क्रमाने tasks लावणे (build systems, dependency resolvers).
नेहमी visited खूण करा — नाहीतर कायम चालत राहाल.

🤔 का

नकाशे, dependencies, social networks, state machines, Networking school चे routes आणि Kubernetes school चे pods — सगळे graphs आहेत. BFS आणि DFS ही तुम्ही सर्वात आधी हाती घेणारी दोन साधने; अंतर महत्त्वाचे असेल तेव्हा Dijkstra.

🔧 कसे (या repo मध्ये)

bfs deque वापरतो; dfs seen set सह recursive आहे; dijkstra heapq वापरतो आणि शिळ्या (stale) entries सोडून देतो; has_cycle parent खाली पाठवतो. demo.py graphs सहा खोल्यांचा नकाशा बनवतो आणि hops, क्रम आणि मीटर विचारतो.

🧪 करून पाहा

python3 dsa/demo.py graphs
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from structures import Graph; from algorithms import bfs, dijkstra, has_cycle
g = Graph(directed=True)
for a, b in (("wake", "wash"), ("wash", "dress"), ("wake", "eat"), ("dress", "leave"), ("eat", "leave")): g.add_edge(a, b)
print("hops from wake:", bfs(g, "wake"))
# topological order: DFS post-order, reversed
seen, order = set(), []
def go(r):
    seen.add(r); [go(n) for n in g.neighbours(r) if n not in seen]; order.append(r)
go("wake"); print("do things in this order:", order[::-1])
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

BFS hops {office: 0, hall: 1, lab: 2, library: 2, gym: 3, field: 4}, office पासून सुरू होणारा DFS क्रम, Dijkstra मीटर {…, gym: 65, field: 105} (library मार्गे नाही, lab मार्गे), आणि cycle? True. तुमचा सकाळचा graph wake पहिला आणि leave शेवटी असलेला योग्य क्रम print करतो.

🏁 तुम्ही आत्ताच काय सिद्ध केले

तुम्ही graph मांडला, त्यातून तीन प्रकारे चाललात, सर्वोत्तम मार्गावर hops आणि मीटर एकमत होत नाहीत हे पाहिले, आणि DFS वरून tasks चा क्रम काढला.

⚠️ नेहमीच्या चुका

visited विसरणे — कोणत्याही cycle वर अनंत loops.
सर्वात लहान path साठी DFS (तो एखादा path शोधतो).
negative edge सह Dijkstra; किंवा शिळ्या heap entries पुन्हा process करणे.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: package managers, build systems, CI pipelines (DAGs), routing tables, recommendation graphs, आणि "या outage चा कोणत्या services वर परिणाम होतो?" — सगळ्या graph चाली.

⏭️ पुढे

धडा 11 — dynamic programming आणि greedy: फळ्यावरची उत्तरे, आणि सरळ दिसणारी पायरी कधी पुरेशी असते.

🗺️ Lesson 10 — Graphs: the corridor map

📍 You are here: Lesson 10 of 12 · Next: lesson-11-dp-greedy

📦 What's in this branch

Lessons 01–10. Rooms and corridors, the two fundamental walks, the one that measures, and cycle detection.

dsa/structures.py — Graph as an adjacency list, weighted, directed or not
dsa/algorithms.py — bfs, dfs, dijkstra, has_cycle
dsa/demo.py — graphs: six rooms, three questions

🧒 Explain like I'm 5

The school is rooms joined by corridors — that is a graph. Three ways to explore from the office: BFS floods — every room one corridor away, then two, then three (a lunch line of rooms to visit) — so the first time you reach a room is the fewest corridors. DFS follows one corridor to its very end before backing up and trying the next (a pile of choices). Dijkstra measures — corridors have lengths, so always extend the shortest walk you know so far (a podium of walks). A corridor leading back to a room you have seen is a cycle.

🗺️ Diagram

flowchart LR
  O["office"] ---|20| H["hall"]
  H ---|30| L["lab"] ; H ---|10| B["library"]
  B ---|60| G["gym"] ; L ---|15| G
  G ---|40| F["field"]

❓ What

Representation: adjacency list {room: [(neighbour, weight)]} — O(V + E) memory; adjacency matrix for dense graphs.
BFS: a queue; O(V + E); shortest path in hops; level order.
DFS: recursion or a stack; O(V + E); reachability, cycles, topological order, backtracking.
Dijkstra: a min-heap of (distance, room); O(E log V); shortest path by weight; no negative corridors (Bellman-Ford handles those).
Cycle (undirected): a neighbour already seen that is not the parent. Topological sort: order tasks so every corridor points forward (build systems, dependency resolvers).
Always mark visited — or walk forever.

🤔 Why

Maps, dependencies, social networks, state machines, the Networking school's routes and the Kubernetes school's pods are all graphs. BFS and DFS are the two tools you reach for first; Dijkstra when distance matters.

🔧 How (in this repo)

bfs uses deque; dfs is recursive with a seen set; dijkstra uses heapq and skips stale entries; has_cycle passes the parent down. demo.py graphs builds the six-room map and asks hops, order and metres.

🧪 Try it

python3 dsa/demo.py graphs
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from structures import Graph; from algorithms import bfs, dijkstra, has_cycle
g = Graph(directed=True)
for a, b in (("wake", "wash"), ("wash", "dress"), ("wake", "eat"), ("dress", "leave"), ("eat", "leave")): g.add_edge(a, b)
print("hops from wake:", bfs(g, "wake"))
# topological order: DFS post-order, reversed
seen, order = set(), []
def go(r):
    seen.add(r); [go(n) for n in g.neighbours(r) if n not in seen]; order.append(r)
go("wake"); print("do things in this order:", order[::-1])
EOF

✅ Verify — what you should see

BFS hops {office: 0, hall: 1, lab: 2, library: 2, gym: 3, field: 4}, a DFS order starting at the office, Dijkstra metres {…, gym: 65, field: 105} (via the lab, not the library), and cycle? True. Your morning graph prints a valid order with wake first and leave last.

🏁 What you just proved

You represented a graph, walked it three ways, saw hops and metres disagree on the best route, and derived a task order from a DFS.

⚠️ Common mistakes

Forgetting visited — infinite loops on any cycle.
DFS for shortest path (it finds a path).
Dijkstra with a negative edge; or re-processing stale heap entries.

🏭 Why this matters in production: package managers, build systems, CI pipelines (DAGs), routing tables, recommendation graphs, and "which services does this outage affect?" — all graph walks.

⏭️ Next

Lesson 11 — dynamic programming & greedy: answers on the board, and when taking the obvious step is enough.

← Previoustrees heaps Next →dp greedy

This page is the lesson's README from the lesson-10-graphs branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.