Why This Matters
Graph problems often begin with raw edges. collections.defaultdict makes it simple to build adjacency lists, degree maps, and grouping buckets without repeated key-existence checks.
Core Idea
Choose the default factory by the value you are building.
| Structure | Use |
|---|---|
defaultdict(list) | adjacency list with repeated neighbors |
defaultdict(set) | adjacency set with duplicate removal |
defaultdict(int) | degree counts or frequencies |
defaultdict(dict) | weighted adjacency by neighbor |
Non-Example or Failure Mode
Reading graph[node] on a defaultdict(list) creates node if it was missing. That is convenient while building, but it can accidentally mutate the graph during validation or debugging.
Runnable Drill
defaultdict graph adjacency drill
Output will appear here.
Common Mistakes
| Mistake | Correction |
|---|---|
| Forgetting isolated nodes. | Add all nodes explicitly if the problem includes them. |
| Accidentally creating keys during reads. | Use graph.get(node, []) when you do not want mutation. |
Using list when duplicates should be removed. | Use defaultdict(set). |
| Mixing directed and undirected edge construction. | For undirected graphs, add both directions. |
| Forgetting degrees for topological sort. | Maintain indegree while building. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What does collections.defaultdict do? | It creates missing values from a default factory. |
| Example / non-example | Should duplicate neighbors use defaultdict(set)? | Yes, if duplicates should collapse. |
| Computation | What does an adjacency list store? | For each node, a list or set of outgoing neighbors. |
| Transfer | How does this feed BFS? | Build adjacency first, then traverse neighbors from the queue. |
Exercises
Beginner:
- Build a directed adjacency list from edge pairs.
- Build an undirected adjacency list by adding both directions.
- Count indegrees with
defaultdict(int).
Intermediate:
- Use
defaultdict(set)to deduplicate edges. - Build weighted adjacency with
defaultdict(dict).
Challenge:
- Implement topological sort from an edge list using adjacency plus indegree.
References
- Python documentation.
collections.defaultdict: https://docs.python.org/3/library/collections.html#collections.defaultdict - Princeton Algorithms. Graph representations and graph processing: https://algs4.cs.princeton.edu/40graphs/