EasyDSA13 min read

What is a graph, and how do you represent it?

Q: What is a graph, and how do you represent it?

**Target Audience:** Beginners preparing for coding interviews — no graph knowledge needed, just arrays and loops **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Think of a group chat for a school trip. Some pairs of students are friends, some are not. If you drew every student as a dot and every friendship as a line between two dots, you would have drawn a **graph**. Now swap the words: dots can be cities and lines can be roads; dots can be web pages and lines can be links; dots can be squares on a chessboard and lines can be legal knight moves. The same

921 views

7 of 154

The problem

Question presented to candidate: "What is a graph, and how would you store one in memory in Python? Walk me through the options and when you would pick each one."

What a strong answer should cover:

Vertices and edges; directed vs undirected; weighted vs unweighted; degree.
The three representations — edge list, adjacency list, adjacency matrix — with their space (O(E), O(V + E), O(V²)) and edge-lookup costs.
Sparse vs dense: why the adjacency list is the default for interview problems.
Implicit graphs: a grid or a word puzzle is a graph you never build explicitly.
Python details: [[] for _ in range(n)] (not [[]] * n, which shares one list), dict/defaultdict(list) for string labels, set neighbours for O(1) edge checks.

Code / implementation expected: Optional — building an adjacency list from an edge list in a few lines of Python.

dsa
graph
adjacency-list

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no graph knowledge needed, just arrays and loops
Difficulty: Easy
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Think of a group chat for a school trip. Some pairs of students are friends, some are not. If you drew every student as a dot and every friendship as a line between two dots, you would have drawn a graph. Now swap the words: dots can be cities and lines can be roads; dots can be web pages and li

The solution is hidden so you can try first

13 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonOne graph, three representations: edge list, adjacency list, matrix

Practice

PythonWeighted directed graph, sparse-graph space, implicit grid graph

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 7 of 154 in DSA

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All DSA questions

Up nextEasy→

What is the difference between a stack and a queue?

Continue