BasicsStorage: O(V+E) list / O(V²) matrix· Level 00

Graph Basics & Representations

Vertices, edges, adjacency lists vs matrices.

Intuition

A graph is a set of vertices (nodes) connected by edges. Choosing the right representation is the most important early decision — it dictates the time complexity of every algorithm you build on top.

Step-by-step

1
Identify whether the graph is directed or undirected.
2
Decide if edges are weighted or unweighted.
3
Choose adjacency list for sparse graphs (E ≪ V²).
4
Choose adjacency matrix for dense graphs or O(1) edge lookup.
5
Wrap it in a class with helper methods: add_vertex, add_edge, neighbors.

Pseudocode

pseudocode

class Graph:
  V: set of vertices
  adj: map vertex -> list of (neighbor, weight)

  add_edge(u, v, w):
    adj[u].append((v, w))
    if undirected: adj[v].append((u, w))

Implementation (Python)

python

from collections import defaultdict

class Graph:
    def __init__(self, directed=False):
        self.adj = defaultdict(list)
        self.directed = directed

    def add_edge(self, u, v, w=1):
        self.adj[u].append((v, w))
        if not self.directed:
            self.adj[v].append((u, w))

    def neighbors(self, u):
        return self.adj[u]

Real-world applications

Foundation for every other graph algorithm
Social networks (users + follows)
Road networks (intersections + streets)