Graphs are one of the most powerful and versatile data structures in computer science. Social networks, maps, dependency systems, and the internet itself are all graphs. Graph problems appear frequently in coding interviews, especially at top tech companies. In this article, you will learn how to represent graphs, traverse them with BFS and DFS, detect cycles, and perform topological sort.
We show every example in Kotlin, Python, and Go.
What is a Graph?
A graph is a collection of vertices (also called nodes) connected by edges. Unlike trees, graphs can have cycles, and nodes can connect to any other node.
Key terms:
- Vertex (node): a single point in the graph
- Edge: a connection between two vertices
- Directed graph: edges have a direction (A -> B is different from B -> A)
- Undirected graph: edges go both ways (A – B means A to B and B to A)
- Weighted graph: edges have a cost or distance
- Unweighted graph: all edges are equal
- Cycle: a path that starts and ends at the same vertex
- Connected: every vertex can reach every other vertex
Graph Representation
There are two common ways to represent a graph in code.
Adjacency List
Store each vertex and a list of its neighbors. This is the most common representation in interviews.
Graph:
0 -- 1
| |
3 -- 2
Adjacency list:
0: [1, 3]
1: [0, 2]
2: [1, 3]
3: [0, 2]
Python:
# Using a dictionary
graph = {
0: [1, 3],
1: [0, 2],
2: [1, 3],
3: [0, 2],
}
Kotlin:
val graph = mapOf(
0 to listOf(1, 3),
1 to listOf(0, 2),
2 to listOf(1, 3),
3 to listOf(0, 2),
)
Go:
graph := map[int][]int{
0: {1, 3},
1: {0, 2},
2: {1, 3},
3: {0, 2},
}
Adjacency Matrix
Store a 2D array where matrix[i][j] = 1 means there is an edge from i to j.
0 1 2 3
0 [ 0, 1, 0, 1 ]
1 [ 1, 0, 1, 0 ]
2 [ 0, 1, 0, 1 ]
3 [ 1, 0, 1, 0 ]
Which One to Use?
| Adjacency List | Adjacency Matrix | |
|---|---|---|
| Space | O(V + E) | O(V^2) |
| Check if edge exists | O(degree) | O(1) |
| Get all neighbors | O(degree) | O(V) |
| Best for | Sparse graphs | Dense graphs |
Most interview problems use adjacency lists because real-world graphs are usually sparse (few edges compared to possible edges).
Building a Graph from an Edge List
Many problems give you an edge list. Here is how to convert it to an adjacency list.
Python:
def build_graph(edges, n, directed=False):
graph = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u)
return graph
edges = [[0, 1], [0, 3], [1, 2], [2, 3]]
graph = build_graph(edges, 4)
Kotlin:
fun buildGraph(edges: List<IntArray>, n: Int, directed: Boolean = false): Map<Int, List<Int>> {
val graph = (0 until n).associateWith { mutableListOf<Int>() }
for ((u, v) in edges) {
graph[u]!!.add(v)
if (!directed) graph[v]!!.add(u)
}
return graph
}
Go:
func buildGraph(edges [][]int, n int, directed bool) map[int][]int {
graph := make(map[int][]int)
for i := 0; i < n; i++ {
graph[i] = []int{}
}
for _, edge := range edges {
u, v := edge[0], edge[1]
graph[u] = append(graph[u], v)
if !directed {
graph[v] = append(graph[v], u)
}
}
return graph
}
Breadth-First Search (BFS)
BFS explores the graph level by level. It uses a queue. BFS finds the shortest path in an unweighted graph.
Algorithm:
- Start at a source vertex. Add it to the queue. Mark it as visited.
- While the queue is not empty: dequeue a vertex, process it, and enqueue all its unvisited neighbors.
Python:
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
# Example: bfs(graph, 0) -> [0, 1, 3, 2]
Kotlin:
fun bfs(graph: Map<Int, List<Int>>, start: Int): List<Int> {
val visited = mutableSetOf(start)
val queue: java.util.Queue<Int> = java.util.LinkedList()
queue.add(start)
val order = mutableListOf<Int>()
while (queue.isNotEmpty()) {
val node = queue.poll()
order.add(node)
for (neighbor in graph[node]!!) {
if (neighbor !in visited) {
visited.add(neighbor)
queue.add(neighbor)
}
}
}
return order
}
Go:
func bfs(graph map[int][]int, start int) []int {
visited := map[int]bool{start: true}
queue := []int{start}
var order []int
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
order = append(order, node)
for _, neighbor := range graph[node] {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
return order
}
Time complexity: O(V + E). Space complexity: O(V).
Depth-First Search (DFS)
DFS explores the graph by going as deep as possible before backtracking. It uses a stack or recursion.
Python:
def dfs(graph, start):
visited = set()
order = []
def explore(node):
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
explore(neighbor)
explore(start)
return order
# Example: dfs(graph, 0) -> [0, 1, 2, 3]
Kotlin:
fun dfs(graph: Map<Int, List<Int>>, start: Int): List<Int> {
val visited = mutableSetOf<Int>()
val order = mutableListOf<Int>()
fun explore(node: Int) {
visited.add(node)
order.add(node)
for (neighbor in graph[node]!!) {
if (neighbor !in visited) {
explore(neighbor)
}
}
}
explore(start)
return order
}
Go:
func dfs(graph map[int][]int, start int) []int {
visited := map[int]bool{}
var order []int
var explore func(int)
explore = func(node int) {
visited[node] = true
order = append(order, node)
for _, neighbor := range graph[node] {
if !visited[neighbor] {
explore(neighbor)
}
}
}
explore(start)
return order
}
Time complexity: O(V + E). Space complexity: O(V).
BFS vs DFS — When to Use Which
| BFS | DFS | |
|---|---|---|
| Uses | Queue | Stack / Recursion |
| Explores | Level by level | Deep first |
| Shortest path | Yes (unweighted) | No |
| Best for | Shortest path, level-order | Cycle detection, topological sort, connected components |
Interview Problem: Number of Islands
Given a 2D grid of ‘1’ (land) and ‘0’ (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent land cells horizontally or vertically. This is LeetCode #200.
Strategy: Scan the grid. When you find a ‘1’, run DFS/BFS to mark all connected land cells as visited. Each time you start a new search, that is one island.
Python:
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0' # Mark as visited
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
Kotlin:
fun numIslands(grid: Array<CharArray>): Int {
if (grid.isEmpty()) return 0
val rows = grid.size
val cols = grid[0].size
var count = 0
fun dfs(r: Int, c: Int) {
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0') return
grid[r][c] = '0'
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
}
for (r in 0 until rows) {
for (c in 0 until cols) {
if (grid[r][c] == '1') {
count++
dfs(r, c)
}
}
}
return count
}
Go:
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
count := 0
var dfs func(int, int)
dfs = func(r, c int) {
if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0' {
return
}
grid[r][c] = '0'
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
count++
dfs(r, c)
}
}
}
return count
}
Topological Sort
Topological sort orders the vertices of a directed acyclic graph (DAG) so that for every edge A -> B, A comes before B. Think of it as task scheduling — you must finish prerequisites before starting the course.
This is the pattern behind LeetCode #207 (Course Schedule).
Python (BFS — Kahn’s Algorithm):
from collections import deque
def topological_sort(num_nodes, edges):
graph = {i: [] for i in range(num_nodes)}
in_degree = {i: 0 for i in range(num_nodes)}
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque([n for n in in_degree if in_degree[n] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(order) == num_nodes:
return order # Valid topological order
return [] # Cycle detected — no valid order
Kotlin:
fun topologicalSort(numNodes: Int, edges: List<IntArray>): List<Int> {
val graph = (0 until numNodes).associateWith { mutableListOf<Int>() }
val inDegree = IntArray(numNodes)
for ((u, v) in edges) {
graph[u]!!.add(v)
inDegree[v]++
}
val queue: java.util.Queue<Int> = java.util.LinkedList()
for (i in 0 until numNodes) {
if (inDegree[i] == 0) queue.add(i)
}
val order = mutableListOf<Int>()
while (queue.isNotEmpty()) {
val node = queue.poll()
order.add(node)
for (neighbor in graph[node]!!) {
inDegree[neighbor]--
if (inDegree[neighbor] == 0) queue.add(neighbor)
}
}
return if (order.size == numNodes) order else emptyList()
}
Go:
func topologicalSort(numNodes int, edges [][]int) []int {
graph := make(map[int][]int)
inDegree := make([]int, numNodes)
for _, edge := range edges {
u, v := edge[0], edge[1]
graph[u] = append(graph[u], v)
inDegree[v]++
}
queue := []int{}
for i := 0; i < numNodes; i++ {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
var order []int
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
order = append(order, node)
for _, neighbor := range graph[node] {
inDegree[neighbor]--
if inDegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
if len(order) == numNodes {
return order
}
return nil // Cycle detected
}
Why Interviewers Ask Graph Questions
Graph questions test:
- Modeling ability — can you convert a word problem into a graph?
- BFS vs DFS — choosing the right traversal for the problem
- Handling visited nodes — avoiding infinite loops in graphs with cycles
- Recognizing patterns — islands, shortest path, topological sort, connected components
Practice Problems
Try these on LeetCode:
- Number of Islands (#200) — DFS/BFS on a grid
- Clone Graph (#133) — BFS with hash map for visited
- Course Schedule (#207) — topological sort with cycle detection
- Pacific Atlantic Water Flow (#417) — DFS from borders
- Number of Connected Components (#323) — DFS or Union-Find
What’s Next?
In the next article, we cover Tries (Prefix Trees) — the data structure behind autocomplete, spell checkers, and word search problems.
Next: DSA Tutorial #8: Tries — The Data Structure Behind Autocomplete
Full series: DSA from Zero to Interview Ready