Week 29 of 43
Advanced DSA
WEEK 29 LEARNING MODULE
Graph Theory Fundamentals & Representations
Introduces Graph Theory terminology, directed/undirected edges, weighted/unweighted graphs, Adjacency Matrix vs. Adjacency List, node degrees, sources, and sinks.
4 Practice Problems4 Core ConceptsVerified Curriculum: high Confidence
What You'll Learn
- ✓Master Graph Theory definitions: Vertices ($V$), Edges ($E$), Directed/Undirected, Weighted/Unweighted, Connected Components.
- ✓Implement Adjacency Matrix ($O(1)$ edge lookup, $O(V^2)$ memory) and Adjacency List ($O(V + E)$ memory).
- ✓Convert between Adjacency Matrices and Adjacency Lists.
- ✓Compute in-degrees, out-degrees, and identify Graph Sources and Sinks.
Core Concepts
Graph Classifications
Directed vs Undirected, Weighted vs Unweighted, Cyclic vs Acyclic, Connected vs Disconnected components.
Adjacency Matrix
O(V²) space, O(1) edge check2D V x V array where matrix[u][v] indicates edge existence; optimal for dense graphs.
Adjacency List
O(V + E) space, O(deg(u)) edge checkArray / dictionary of neighbor lists; optimal for sparse graphs.
Degrees, Sources & Sinks
O(V + E)In-degree (incoming edges), Out-degree (outgoing edges), Source (in=0), Sink (out=0).
Algorithms Covered
Graph Matrix-to-List ConversionDegree ComputationStar Graph Center IdentificationSource & Sink Detection
Data Structures Applied
Graphs (Adjacency Matrix, Adjacency List, Edge List)
“You can always recognize truth by its beauty and simplicity.”
— Richard P. Feynman
Lecture Materials (1)
Curated Practice Problems (4)
Eolymp
W29