Graph Fundamentals
Terminology, representations (adjacency list/matrix/edge list), graph properties, and complexity analysis.
41 lessons
105 min
Lessons
1. Intro
Welcome
1m
2. What is a Graph?
Intuition
2m
3. Real World Example - The Map
Cities and Roads
2m
4. Real World Example - Social Networks
Users and Friendships
2m
5. Why Graphs Matter
Applications
2m
6. Vocabulary - The Vertex
The "Dots"
2m
7. Vocabulary - The Edge
The "Lines"
2m
8. Quiz: Vertices and Edges
Knowledge check
2m1 problems
9. Formal Notation
Speaking Math
2m
10. Types of Graphs - Undirected
Two-way streets
3m
11. Types of Graphs - Directed
One-way streets
3m
12. Classify the Graph
Mental Check
3m
13. The Representation Problem
How to tell the computer?
2m
14. Quiz: Directed vs Undirected
Knowledge check
2m1 problems
15. Method 1 - The Adjacency Matrix
The Grid Approach
3m
16. Matrix - Visual Example
Seeing the Grid
3m
17. Matrix - The Problem
Why we rarely use it
3m
18. Method 2 - The Adjacency List
The Efficient Approach
3m
19. Adjacency List - Visual Example
Seeing the Lists
3m
20. Adjacency List - Efficiency
Memory Usage
3m
21. Quiz: Adjacency Matrix vs List
Knowledge check
2m1 problems
22. Implementing in C++
Vectors to the rescue
2m
23. Explaining the Syntax
vector adj[N]
3m
24. Adding Directed Edges
Code Snippet
3m
25. Adding Undirected Edges
Code Snippet
3m
26. Graph Degrees
Node Popularity
2m
27. Directed Degrees
In and Out
3m
28. Quiz: Graph Degrees
Knowledge check
2m1 problems
29. Problem Time - Town Judge
LeetCode 997
2m1 problems
30. Town Judge - The Story
Understanding the Rules
3m
31. Town Judge - Graph Translation
From English to Graph
3m
32. Town Judge - The Algorithm
How to solve it
3m
33. Town Judge - Implementation
Writing the Code
5m1 problems
34. Problem Time - Star Graph
LeetCode 1791
2m1 problems
35. Star Graph - Method 1
Using Degrees
3m
36. Star Graph - Method 2
Pure Logic
3m
37. Star Graph - The Trick
O(1) Solution
3m
38. Star Graph - Implementation
Writing the Code
3m1 problems
39. Quiz: Graph Representations in Code
Knowledge check
2m1 problems
40. Cities and Roads
Codeforces 330B
3m1 problems
41. Section Recap
What we learned
2m