Skip to main content

Graphs

Premium

A graph is a data structure that consists of vertices (or “nodes”) and links between these vertices, called “edges.” Edges can be directed or undirected, depending on the application. Graph representations of data have many practical use cases; in social networks we can represent people as vertices and friendships as undirected edges, and for maps and GPS navigation, we can represent intersections as vertices and road segments as directed edges.

Graphs help solve problems involving:

  • Connectivity (paths, components)
  • Shortest paths
  • Cycles
  • Topological ordering
  • Network flows
  • Minimum spanning trees
  • Search queries (DFS/BFS)
  • Routing and navigation

They are foundational in interviews involving dynamic systems, networks, and traversal problems.

Types of graphs

1. Undirected graph

Edges do not have a specific direction, meaning the connection between two vertices is bidirectional.

Used in:

  • Friend networks
  • Road networks (two-way)
  • Component detection

2. Directed graph (Digraph)

Edges are unidirectional, with a defined source and destination vertex. A → B is not the same as B → A.

Used in:

  • Dependencies
  • Web links
  • One-way systems

3. Weighted graph

Each edge has an associated value, or "weight," representing a cost, distance, or time.

Used in:

  • Dijkstra's algorithm
  • Minimum spanning tree
  • Navigation systems

4. Unweighted graph

All edges are treated equally, with no associated weights. Used for shortest path via BFS.

5. Cyclic & acyclic

Cyclic graph: Contains at least one cycle, which is a path that starts and ends at the same vertex.

Acyclic graph: A graph with no cycles. A Directed Acyclic Graph (DAG) is a common example.

6. Connected vs disconnected

Connected: Every pair of vertices has a path

Disconnected: Some nodes are isolated

Graph representations

1. Adjacency list (Most common)

An adjacency list stores each node along with a list of its neighbors. It is the most memory-efficient representation for sparse graphs.

Python
graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}

Characteristics

  • Uses a list/array of lists (or hash map of lists).
  • Great for BFS & DFS.
  • Space: O(V + E).

2. Adjacency matrix

A 2D matrix V × V where matrix[u][v] = 1 (or weight) if an edge exists.

Python
[[0 1 1 0]
[0 0 1 0]
[1 0 0 1]
[0 0 0 1]]

Characteristics

  • Fast edge lookup: O(1)
  • Space: O(V²) — not memory-friendly for large graphs
  • Works well for dense graphs
  • Used for weighted graphs too

3. Edge list

A simple list containing all edges as pairs (or triples when weighted).

Python
edges = [
    (0, 1),
    (0, 2),
    (1, 2),
    (2, 3),
    (3, 3)
]

Characteristics

  • Most compact representation
  • Great when you only need edges (e.g., Kruskal’s algorithm)
  • Space: O(E)

graph TC

Calculating memory usage

The memory used by a graph is a function of the number of vertices V and the number of edges E. For an adjacency list implementation, the total space usage can be expressed as V + E, where edges are IDs or pointers. For an adjacency matrix, the memory usage is V^2 since the state of all edges is stored.

Common edge cases & pitfalls

  1. Not checking for cycles

  2. Running DFS/BFS without a visited set will lead to infinite loops

  3. Incorrectly treating a directed graph as undirected

  4. Confusing adjacency matrix with adjacency list indexing

  5. Not handling disconnected graphs (need to run traversal multiple times)

  6. Using BFS for weighted graph shortest path (should use Dijkstra)

  7. Using DFS for shortest path (not guaranteed)

Quiz

  1. BFS is best for finding shortest path in which type of graph?

a) Weighted

b) Negative weighted

c) Unweighted

d) Cyclic

  1. What structure does DFS use internally?

a) Queue

b) Stack

c) Heap

d) Hash map

  1. Topological sort only works on:

a) Trees

b) DAGs

c) Weighted graphs

d) Cyclic graphs

Practice problems

Next Lesson