Graphs

You have probably seen a map app that finds the shortest route between two cities. Or maybe you have noticed how social media shows “friends of friends.” Behind both of these is a data structure called a graph. It is one of the most powerful and widely used ideas in all of computer science - and once it clicks, you will start seeing graphs everywhere.

What is a Graph?

A graph is just a way to show relationships between things.

• The things are called vertices (or nodes)
• The relationships between them are called edges (or connections)

That is really all it is. Points and lines connecting them.

Here are some real-life examples:

• Friends on social media - each person is a vertex, each friendship is an edge
• Cities connected by roads - each city is a vertex, each road is an edge
• Computers in a network - each computer is a vertex, each cable is an edge
• Web pages connected by links - each page is a vertex, each link is an edge

Tip

Think of a graph like a map. The cities are your vertices (nodes), and the roads between them are your edges (connections). Simple as that.

Words You Need to Know

Before going further, here are some terms that come up all the time:

Word	What It Means
Vertex (Node)	A single point in the graph
Edge	A connection between two vertices
Adjacent	Two vertices that are directly connected
Degree	How many edges are connected to a vertex
Path	A route from one vertex to another
Graph Order	The total number of vertices
Graph Size	The total number of edges

Types of Graphs

Undirected Graph

In an undirected graph, edges have no direction. If A is connected to B, then B is also connected to A. It goes both ways.

A ----- B
|       |
C ----- D

If you and your friend are Facebook friends, that connection works both ways. That is an undirected graph.

Directed Graph (Digraph)

In a directed graph, edges have a direction. An arrow points from one vertex to another, and it only works one way.

A ---> B ---> C
^             |
|-------------|

If you follow someone on Twitter but they do not follow you back, that is a directed edge. A -> B does not mean B -> A.

Weighted Graph

In a weighted graph, each edge has a number attached to it called a weight. This number can represent distance, cost, time, or anything else.

A --5-- B --2-- C

Google Maps uses weighted graphs - the weights are travel times or distances between locations.

A weighted graph can be directed or undirected. Most real-world graphs are weighted.

How Graphs are Stored in Memory

You cannot just store a graph as a picture. You need to put it into memory somehow. There are two main ways to do this.

Adjacency Matrix

An adjacency matrix is a 2D grid (table) where:

• Rows and columns both represent vertices
• A 1 in the grid means there is an edge between those two vertices
• A 0 means there is no edge

Take this graph:

0 ---- 1
|      |
2 ---- 3

Its adjacency matrix looks like this:

    0  1  2  3
  ------------
0 | 0  1  1  0
1 | 1  0  0  1
2 | 1  0  0  1
3 | 0  1  1  0

Reading row 0: vertex 0 is connected to vertices 1 and 2. Makes sense!

Property	Value
Space used	O(V squared) - grows fast
Check if edge exists	O(1) - super fast
Best for	Dense graphs (lots of edges)
Bad for	Sparse graphs (few edges)

Caution

An adjacency matrix for 1000 vertices needs a 1000x1000 grid - that is 1 million cells, even if only a handful of edges exist. It wastes a lot of memory for sparse graphs.

Adjacency List

An adjacency list stores, for each vertex, a list of all its neighbors.

Same graph as before:

0 ---- 1
|      |
2 ---- 3

The adjacency list looks like this:

0 -> [1, 2]
1 -> [0, 3]
2 -> [0, 3]
3 -> [1, 2]

Only the actual connections are stored. No wasted space.

Property	Value
Space used	O(V + E) - only what you need
Check if edge exists	O(degree of vertex)
Best for	Sparse graphs
Used in	Almost every coding interview

Tip

In interviews, always use an adjacency list unless the problem specifically requires a matrix. It is more memory efficient and works better with most graph algorithms.

Python Code for a Graph

Here is a clean implementation of an undirected graph using an adjacency list:

class UndirectedGraph:
    def __init__(self):
        self.nodes = {}

    def addVertices(self, v):
        if v not in self.nodes:
            self.nodes[v] = set()

    def addEdge(self, v1, v2):
        if v1 not in self.nodes or v2 not in self.nodes:
            raise ValueError("Vertex not found")

        self.nodes[v1].add(v2)
        self.nodes[v2].add(v1)

    def addEdgeAndVertices(self, v1, v2):
        if v1 == v2:
            raise ValueError("Self loop not allowed")
        self.addVertices(v1)
        self.addVertices(v2)
        self.addEdge(v1, v2)

Why use a set() instead of a list for neighbors?

• It automatically prevents duplicate edges
• Adding and checking membership is O(1) - very fast

Degree of a Vertex

The degree of a vertex is simply how many edges are connected to it.

A ---- B ---- C
       |
       D

• Degree of A = 1 (only connected to B)
• Degree of B = 3 (connected to A, C, and D)
• Degree of C = 1 (only connected to B)
• Degree of D = 1 (only connected to B)

There is a neat formula that always holds true:

Sum of all degrees = 2 x number of edges

This makes sense - every edge contributes to the degree of two vertices.

In-degree and Out-degree (for Directed Graphs)

In a directed graph, each vertex has two types of degree:

• In-degree - how many edges point INTO this vertex
• Out-degree - how many edges point OUT of this vertex

A --> B --> C
      ^
      |
      D

• In-degree of B = 2 (arrows from A and D point into B)
• Out-degree of B = 1 (one arrow from B points to C)

Formula that always holds for directed graphs:

Sum of all in-degrees = Sum of all out-degrees = number of edges

Must-Know Formulas

These show up in interviews. Worth memorizing.

Undirected Graph:

• Maximum edges = V x (V - 1) / 2
• Maximum degree of any single vertex = V - 1
• Minimum edges = 0 (disconnected graph)

Directed Graph:

• Maximum edges = V x (V - 1)
• Maximum in-degree = V - 1
• Maximum out-degree = V - 1

The undirected formula is halved because the edge between A and B is the same as the edge between B and A.

Special Types of Graphs

Complete Graph

Every vertex is connected to every other vertex. Nothing is missing.

A ----- B
| \   / |
|  \ /  |
|  / \  |
| /   \ |
C ----- D

Number of edges = V x (V - 1) / 2

Connected vs Disconnected

A connected graph has a path from every vertex to every other vertex. You can reach anywhere from anywhere.

A disconnected graph is split into separate pieces. Some vertices are isolated and cannot be reached from others.

Cyclic vs Acyclic

A cyclic graph contains at least one cycle - a path that loops back to where it started.

A --> B --> C
^           |
|-----------|

An acyclic graph has no cycles at all. A tree is a classic example. A DAG (Directed Acyclic Graph) is a directed graph with no cycles - used in dependency resolution, build systems, and scheduling.

Things That Are Usually Not Allowed

Self Loop - an edge from a vertex back to itself. Most standard graph problems do not allow these.

Parallel Edges - more than one edge between the same two vertices. Graphs with parallel edges are called multigraphs. Most interview problems use simple graphs (no self loops, no parallel edges).

Graph Traversal - Visiting Every Vertex

A graph is not like an array where you can just loop through it in order. Graphs have no clear “start” or “end.” Vertices can connect in all kinds of ways.

Traversal means visiting every single vertex in the graph systematically. Without a strategy, you might miss nodes, visit the same node twice, or get stuck in a loop forever.

Traversal is the foundation for everything: searching for an element, checking connectivity, detecting cycles, finding shortest paths, and topological sort.

There are two main traversal techniques you need to know.

DFS - Depth First Search

The Simple Idea

DFS says: go as deep as possible first. When you hit a dead end, backtrack and try another path.

Think of exploring a maze. You pick one corridor and keep walking until you either find the exit or hit a wall. Then you go back to the last fork and try the next corridor.

Visualizing DFS

Take this graph:

    1
   / \
  2   3
  |
  4

DFS starting from vertex 1:

1 -> 2 -> 4 -> back up -> 3

Visit order: 1, 2, 4, 3

It goes as deep as possible (all the way to 4) before coming back and visiting 3.

What DFS Needs

• A visited set - to remember which nodes have already been seen (prevents infinite loops in cyclic graphs)
• A stack - to remember which node to go to next (can be an explicit stack or the call stack via recursion)

Tip

The call stack in recursion works exactly like an explicit stack. When you call a function, it gets pushed. When it returns, it gets popped. That is why DFS recursion feels so natural.

DFS Using a Stack (Iterative)

1. Create an empty visited set and an empty stack

2. Push the starting node into the stack

3. While the stack is not empty:

   • Pop a node from the top
   • If it is already visited, skip it
   • Mark it as visited and process it
   • Push all its unvisited neighbors into the stack

Dry run on:

0 --- 1
|     |
2 --- 3

Starting from vertex 0:

Stack: [0]        -> pop 0, visit 0
Stack: [1, 2]     -> pop 2, visit 2
Stack: [1, 3]     -> pop 3, visit 3
Stack: [1]        -> pop 1, visit 1
Done!

def dfs_iterative(graph):
    visited = set()
    stack = []

    for start in graph:
        if start in visited:
            continue

        stack.append(start)

        while stack:
            node = stack.pop()

            if node in visited:
                continue

            print(node, end=", ")
            visited.add(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

DFS Using Recursion

This is the version you will use most in interviews. The recursion itself acts as the stack.

DFS(node):
    if node is already visited -> stop
    mark node as visited
    process node
    for each neighbor:
        call DFS(neighbor)

What the call stack looks like for a simple chain 1 -> 2 -> 3:

DFS(1)
 └── DFS(2)
      └── DFS(3)
           └── no more neighbors, return

def dfs_recursive_util(graph, node, visited):
    if node in visited:
        return

    print(node, end=", ")
    visited.add(node)

    for neighbor in graph[node]:
        dfs_recursive_util(graph, neighbor, visited)


def dfs_recursive(graph):
    visited = set()

    for node in graph:
        if node not in visited:
            dfs_recursive_util(graph, node, visited)

Handling Disconnected Graphs

This is something a lot of beginners miss, and it costs them in interviews.

If a graph is disconnected, starting DFS from one vertex will only reach the vertices in that piece. The rest will never be visited.

0 --- 1     5
|           |
2           6

If you start DFS from 0, you visit 0, 1, and 2. But vertices 5 and 6 are never touched.

The fix is always loop over every vertex and start a new traversal from any unvisited one:

for node in graph:
    if node not in visited:
        dfs_recursive_util(graph, node, visited)

The code above already does this. That outer for loop is what makes your solution correct for all graphs, not just connected ones.

Caution

This is one of the most common interview mistakes. Always ask yourself: “What if the graph is disconnected?” If your code does not handle it, add the outer loop. This applies to both DFS and BFS.

BFS - Breadth First Search

The Simple Idea

BFS says: visit all neighbors first, then move to the next level.

Think of dropping a stone in a pond. Ripples spread outward in rings, one level at a time. BFS works exactly like that.

Visualizing BFS

Same graph:

    1
   / \
  2   3
  |
  4

BFS starting from vertex 1:

1 -> 2 -> 3 -> 4

Visit order: 1, 2, 3, 4

It visits 1 first, then all neighbors of 1 (which are 2 and 3), then all neighbors of those (which is 4).

Notice the difference from DFS. DFS went 1, 2, 4, 3. BFS goes 1, 2, 3, 4. BFS respects levels.

What BFS Needs

• A visited set - same as DFS, prevents revisiting
• A queue - first in, first out. This is what gives BFS its level-by-level behavior

Tip

The key difference between DFS and BFS is just the data structure: DFS uses a stack (last in, first out), BFS uses a queue (first in, first out). This one change flips the entire traversal order.

BFS Step by Step

1. Create an empty visited set and an empty queue

2. Add the starting node to the queue

3. While the queue is not empty:

   • Remove a node from the front of the queue
   • If it is already visited, skip it
   • Mark it as visited and process it
   • Add all unvisited neighbors to the back of the queue

Dry run on:

0 --- 1
|     |
2 --- 3

Starting from vertex 0:

Queue: [0]        -> dequeue 0, visit 0, add neighbors 1 and 2
Queue: [1, 2]     -> dequeue 1, visit 1, add neighbor 3
Queue: [2, 3]     -> dequeue 2, visit 2, neighbor 3 already queued
Queue: [3]        -> dequeue 3, visit 3
Done!

from collections import deque

def bfs(graph):
    visited = set()
    queue = deque()

    for start in graph:
        if start in visited:
            continue

        queue.append(start)

        while queue:
            node = queue.popleft()

            if node in visited:
                continue

            print(node, end=", ")
            visited.add(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

Use deque from Python’s collections module. It has O(1) popleft(), while a regular list’s pop(0) is O(n).

DFS vs BFS - Side by Side

Feature	DFS	BFS
Data structure	Stack or Recursion	Queue
How it travels	Goes deep first	Goes level by level
Finds shortest path	No	Yes (unweighted graphs)
Memory usage	Usually less	Usually more
Good for	Cycles, components, topological sort	Shortest path, minimum steps, level order

Use DFS when the problem is about:

• Detecting if a cycle exists
• Finding all connected components
• Topological sorting (ordering tasks with dependencies)
• Maze solving or exploring all possibilities

Use BFS when the problem is about:

• Finding the shortest path in an unweighted graph
• Finding the minimum number of steps to reach something
• Level order traversal (process nodes layer by layer)
• Spreading problems (fire spreading, water flooding, infection)

Tip

Quick shortcut: if the problem says “shortest” or “minimum steps” and the graph has no weights, reach for BFS. If it says “all paths,” “detect cycle,” or “explore,” reach for DFS.

Complexity for Both

Both DFS and BFS have the same complexity when using an adjacency list:

	Time	Space
DFS	O(V + E)	O(V)
BFS	O(V + E)	O(V)

Visit every vertex once, check every edge once. Space is for the visited set plus the stack or queue.

Common Interview Mistakes

These come up again and again:

• Not handling disconnected graphs - always use the outer for node in graph loop
• Forgetting the visited set - your code will loop forever on cyclic graphs
• Saying DFS uses a queue - it does not, DFS uses a stack
• Saying BFS uses a stack - it does not, BFS uses a queue
• Saying time complexity is O(V squared) - it is O(V + E) with an adjacency list

One-Line Memory Trick

• DFS -> Stack -> go Deep
• BFS -> Queue -> go Broad

Summary

Graph Basics

• A graph is made of vertices (nodes) and edges (connections)
• Undirected graphs go both ways, directed graphs go one way
• Weighted graphs have numbers on edges representing cost or distance
• Use an adjacency list in almost every interview (O(V + E) space vs O(V squared) for matrix)
• Key formulas: undirected max edges = V(V-1)/2, directed max edges = V(V-1)

DFS

• Goes as deep as possible, then backtracks
• Uses a stack (or recursion, which uses the call stack)
• Good for: cycle detection, connected components, topological sort, mazes
• Time: O(V + E), Space: O(V)
• Always use an outer loop over all vertices to handle disconnected graphs

BFS

• Visits all neighbors first, then the next level
• Uses a queue - always use deque in Python for O(1) popleft
• Good for: shortest path, minimum steps, level order traversal
• Time: O(V + E), Space: O(V)
• Always use an outer loop over all vertices to handle disconnected graphs

Interview Checklist

• Handle disconnected graphs with an outer loop - this is the most common mistake
• Always use a visited set or you will loop forever
• DFS = stack, BFS = queue - never mix these up
• Complexity is O(V + E) with adjacency list, not O(V squared)
• Shortest path with no weights -> BFS. Cycle detection or all paths -> DFS