A
AiTechWorlds
AiTechWorlds
Open Google Maps. Type in a destination. In an instant, it shows you a route — perhaps multiple routes, with distances and estimated times. It knows which roads connect which intersections, which roads are one-way, which highways are faster despite being longer.
Under the hood, the entire road network is a graph. Cities and intersections are nodes (also called vertices). Roads connecting them are edges. Can you get from City A to City B? What is the shortest path? What cities can you reach at all if some roads are blocked? These are graph problems, and they appear everywhere.
Social networks, the internet itself, flight routes, recommendation engines, dependency resolvers — all graphs. This is one of the most universally important data structures in computer science.
Graph: A data structure consisting of a set of vertices (nodes) and a set of edges (connections between pairs of vertices).
Formally: G = (V, E) where V is the set of vertices and E is the set of edges.
Vertices: {A, B, C, D, E}
Edges: {(A,B), (A,C), (B,D), (C,D), (D,E)}
A
/ \
B C
\ /
D
|
E
Directed vs Undirected:
| Type | Description | Example |
|---|---|---|
| Undirected | Edge (A,B) means you can go A→B and B→A | Friendships on Facebook |
| Directed | Edge (A,B) means A→B only; B→A needs its own edge | Twitter follows, web links |
Weighted vs Unweighted:
| Type | Description | Example |
|---|---|---|
| Unweighted | Edges have no cost; all connections equal | Friend connections |
| Weighted | Each edge has a numerical value (cost, distance, time) | Road distances, flight prices |
A 2D array (matrix) of size V × V where matrix[i][j] = 1 (or the weight) if there is an edge from vertex i to vertex j, and 0 otherwise.
A B C D E
A [ 0 1 1 0 0 ]
B [ 1 0 0 1 0 ]
C [ 1 0 0 1 0 ]
D [ 0 1 1 0 1 ]
E [ 0 0 0 1 0 ]
# Adjacency matrix for the graph above (0-indexed: A=0, B=1, C=2, D=3, E=4)
matrix = [
[0, 1, 1, 0, 0], # A connects to B, C
[1, 0, 0, 1, 0], # B connects to A, D
[1, 0, 0, 1, 0], # C connects to A, D
[0, 1, 1, 0, 1], # D connects to B, C, E
[0, 0, 0, 1, 0], # E connects to D
]
# Check if A and B are connected: O(1)
print(matrix[0][1]) # 1 — yes, they are connected
# Find all neighbors of D (index 3): O(V)
neighbors_of_D = [i for i, connected in enumerate(matrix[3]) if connected]
print(neighbors_of_D) # [1, 2, 4] — B, C, E
Adjacency matrix: when to use:
Drawback: Uses O(V²) memory even when most edges are absent. For a social network with 1 billion users, a matrix would be impossible.
Each vertex stores a list of its neighbors. In Python, this is naturally a dictionary of lists.
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C, E]
E: [D]
This is sparse-friendly: if vertex A has 3 neighbors, we store exactly 3 entries — not V entries.
class Graph:
def __init__(self, directed=False):
self.adjacency_list = {} # Dict: vertex → list of neighbors
self.directed = directed # True = directed, False = undirected
def add_vertex(self, vertex):
if vertex not in self.adjacency_list:
self.adjacency_list[vertex] = [] # New vertex with no edges yet
def add_edge(self, u, v, weight=None):
self.add_vertex(u) # Ensure both vertices exist
self.add_vertex(v)
# Store (neighbor, weight) if weighted, else just neighbor
entry_uv = (v, weight) if weight is not None else v
self.adjacency_list[u].append(entry_uv) # u → v edge
if not self.directed:
entry_vu = (u, weight) if weight is not None else u
self.adjacency_list[v].append(entry_vu) # v → u edge (undirected)
def get_neighbors(self, vertex):
return self.adjacency_list.get(vertex, [])
def has_edge(self, u, v):
neighbors = self.adjacency_list.get(u, [])
# Handle both weighted (tuples) and unweighted (plain values) formats
return any((n[0] if isinstance(n, tuple) else n) == v for n in neighbors)
def display(self):
print("Graph (Adjacency List):")
for vertex, neighbors in self.adjacency_list.items():
print(f" {vertex}: {neighbors}")
Social Network Example:
social = Graph(directed=False)
social.add_edge("Alice", "Bob")
social.add_edge("Alice", "Charlie")
social.add_edge("Bob", "Diana")
social.add_edge("Charlie", "Diana")
social.add_edge("Diana", "Eve")
social.display()
print("\nAlice's friends:", social.get_neighbors("Alice"))
print("Are Bob and Diana connected?", social.has_edge("Bob", "Diana"))
print("Are Alice and Eve connected?", social.has_edge("Alice", "Eve"))
Output:
Graph (Adjacency List):
Alice: ['Bob', 'Charlie']
Bob: ['Alice', 'Diana']
Charlie: ['Alice', 'Diana']
Diana: ['Bob', 'Charlie', 'Eve']
Eve: ['Diana']
Alice's friends: ['Bob', 'Charlie']
Are Bob and Diana connected? True
Are Alice and Eve connected? False
Weighted Directed Graph Example:
cities = Graph(directed=True)
cities.add_edge("NYC", "LA", weight=2800)
cities.add_edge("NYC", "Chicago", weight=790)
cities.add_edge("Chicago", "LA", weight=2020)
cities.add_edge("LA", "Seattle", weight=1140)
cities.display()
Output:
Graph (Adjacency List):
NYC: [('LA', 2800), ('Chicago', 790)]
Chicago: [('LA', 2020)]
LA: [('Seattle', 1140)]
Seattle: []
The simplest representation — just a list of all edges as tuples:
edges = [
("A", "B"),
("A", "C"),
("B", "D"),
("C", "D"),
("D", "E"),
]
Use case: When you primarily need to iterate over all edges (e.g., Kruskal's algorithm for minimum spanning trees). Checking if a specific edge exists is O(E) — slow.
| Feature | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space complexity | O(V²) | O(V + E) |
| Add vertex | O(V²) — resize matrix | O(1) |
| Add edge | O(1) | O(1) |
| Check edge (u, v) | O(1) | O(degree of u) |
| Find all neighbors | O(V) | O(degree of u) |
| Best for | Dense graphs | Sparse graphs (most) |
| Memory for 1M vertices | 10^12 entries | Only as many as edges |
In practice, use adjacency lists. Most real-world graphs are sparse — social networks, road maps, web links. Adjacency lists use only the memory they need.
| Term | Meaning |
|---|---|
| Degree | Number of edges connected to a vertex |
| Path | A sequence of vertices connected by edges |
| Cycle | A path that starts and ends at the same vertex |
| Connected | Every vertex is reachable from every other vertex |
| DAG | Directed Acyclic Graph — directed graph with no cycles |
| Sparse graph | Few edges relative to the number of vertices |
| Dense graph | Many edges, close to V² edges maximum |
A graph is the most general relationship structure in computer science — it can model anything with connections. Choose the right representation for your problem: adjacency matrices for dense graphs requiring fast edge checks, adjacency lists for everything else. The Python adjacency list using a dict of lists is clean, flexible, and efficient, and it is the representation used by virtually every graph algorithm you will encounter in practice.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises