Skip to content
Ameen Abozaid
Englishالعربية
BEG-043

Graph basics

  • 6 Lessons
  • 71 min of reading
  • 3 h practice (estimate)
Start module
On this page 8 topics

Overview

Topics

  • Vertices
  • edges
  • BFS
  • DFS
  • common applications

Learn first

71 min of reading · 3 h of practice (estimate)

Learning outcomes

  1. Represent a graph with an adjacency list.
  2. Implement BFS and DFS and choose between them.
  3. Find a shortest path in an unweighted graph with BFS.
  4. Recognize graph problems in real systems (dependencies, networks, routes).

Lessons

  1. 01Graphs everywhere12 min read
  2. 02Representing graphs12 min read
  3. 03Breadth-first search12 min read
  4. 04Depth-first search12 min read
  5. 05Applications: dependencies and cycles11 min read
  6. 06Demo: metro route finder with BFS12 min read

Lab and exercises

Lab

BEG-043-LAB1 · Metro route finder

Outcomes: 1–4 · Time: ~3 h

  1. Load a small metro map (a text file of "station-station" lines) into an adjacency list.
  2. Implement BFS that returns the fewest-stops route between two stations.
  3. Handle unknown and unreachable stations without crashing.
  4. Add a DFS "can I get there at all" check and say when you would use it instead of BFS.

Acceptance: correct routes; unreachable stations handled.

Exercises (assessment: 3 problems)

IDOutcomeTask
BEG-043-EX011Write the adjacency list for edges A-B, A-C, B-D, C-D, D-E (undirected).
BEG-043-EX022Write the BFS visiting order from A for the graph in EX01 (visit neighbors in alphabetical order).
BEG-043-EX032Write the DFS visiting order from A for the same graph, same neighbor order.
BEG-043-EX043Using BFS, give the shortest path from A to E and its number of edges.
BEG-043-EX054Name the nodes and edges of: a course prerequisite plan; a social network; a map of airports and flights. Say whether each is directed.
BEG-043-EX062Explain what happens if BFS has no visited set on a graph with a cycle.
Show solutions
  • EX01 A: [B, C]; B: [A, D]; C: [A, D]; D: [B, C, E]; E: [D].
  • EX02 A, B, C, D, E.
  • EX03 A, B, D, C, E (A -> B -> D -> C, back to D -> E).
  • EX04 A -> B -> D -> E (or via C), 3 edges.
  • EX05 Prerequisites: courses are nodes, "needs" are directed edges. Social network: people are nodes; "friend" is undirected, "follows" is directed. Airports: nodes airports, edges flights, usually directed.
  • EX06 It keeps re-adding the same nodes around the cycle and never finishes (an infinite loop or a memory error).

Quiz

Outcomes: O1 adjacency list · O2 BFS and DFS · O3 shortest path · O4 graph problems in systems.

A self-check for you: nothing is graded, saved or sent anywhere. Choose an answer, then check it. You can try again as often as you like.

  1. 1A graph is made of:O1
  2. 2An adjacency list stores for each node:O1
  3. 3A one-way street is best modeled as a(n):O1
  4. 4BFS uses a:O2
  5. 5Without a visited set, BFS on a graph with a cycle may:O2
  6. 6Recursive DFS relies on the:O2
  7. 7In an unweighted graph, the shortest path (fewest edges) is found by:O3
  8. 8BFS time for V nodes and E edges with an adjacency list:O3
  9. 9"Library A needs B, B needs A" is a:O4
  10. 10Which is a graph problem?O4

Practical part

Three problems (BEG-043-EX02, EX03, EX04) plus the metro route finder lab and exercises EX01, EX05, EX06. Pass: at least 2 of 3 problems correct, correct routes, unreachable stations handled, and at least 8 of 10 quiz answers correct.

Common mistakes

Forgetting a visited set (infinite loops).

Assessment

3 problems.

Career relevance

Dependency mapping (SRC-009) and service graphs.

Type to search levels, phases, modules and lessons.