Graphs

A non-linear data structure consisting of nodes (vertices) and edges that connect them. Can represent complex relationships.

What is it?

Graphs are the ultimate structure for representing networks and relationships. In Google Maps, every city or intersection is a node (vertex), and the roads connecting them are edges. Each edge has a "weight," which could be the distance or the current travel time. When you ask for directions, Google Maps uses a graph algorithm like Dijkstra's to find the shortest path from your starting node to your destination node. Similarly, on LinkedIn, you are a node, and your connections are edges linking you to other nodes (people). "Mutual connections" are found by traversing this graph to see which nodes are just two edges away from you.

Time Complexity

AccessO(V+E)

SearchO(V+E)

InsertionO(1)

DeletionO(E)

Implementation Example

// Adjacency List representation
const graph = new Map();

function addNode(airport) {
  graph.set(airport, []);
}

function addEdge(origin, destination) {
  graph.get(origin).push(destination);
  graph.get(destination).push(origin);
}

addNode("SFO");
addNode("LAX");
addEdge("SFO", "LAX");

Graphs

Graphs Deep Dive

Graphs capture relationships between entities—social networks, routing tables, knowledge graphs—and unlock traversal-heavy insights.

?But why does this matter?

Choosing adjacency lists, matrices, or compressed sparse row representations changes memory usage by orders of magnitude.

Visual Flow

How it actually moves

Traversal (BFS/DFS)

O(V + E)

Visits vertices proportional to edges encountered.

Edge lookup (adj list)

O(degree)

Scrolls neighbors stored per node.

Pathfinding

O(E log V)

Dijkstra with priority queue when weights are non-negative.

Shortest path with BFS (unweighted graph)

Enqueue the start node with distance 0 and mark it visited.

While queue not empty: dequeue node, and if it is the target, return distance.

For each neighbor, if unseen, mark visited, enqueue with distance + 1, and record the previous node to rebuild the path.

If traversal ends without hitting target, no route exists.

Watch the best explainer

Graph Algorithms for Technical Interviews — Full Course

freeCodeCamp · Alvin Zablan

Millions of views: BFS, DFS, islands, and shortest paths explained visually.

Metro map mental model

Stations are vertices and tracks are edges. To travel, you traverse edges connecting stations; express trains (weighted edges) might cost less time.

Real-world analogy

Ride-sharing apps treat drivers and riders as nodes, edges appear when they are close enough to match.

Takeaway

Graphs let you express complex, many-to-many relationships and run explorations like shortest path or influence spread.

Practical applications

• Navigation systems running Dijkstra/A* to route vehicles.
• Fraud detection linking transactions via shared attributes.
• Recommendation engines performing similarity searches on bipartite graphs.

Technical insights

• Sparse graphs favor adjacency lists; dense graphs benefit from matrices for O(1) edge checks.
• Graph databases store edges as first-class citizens, optimizing traversals.
• Partitioning and sharding graphs is hard; techniques like vertex-cut and edge-cut balance workloads.

When to reach for it

• Social/product graphs
• Compiler dependency analysis
• Network routing

Operations Breakdown

Traversal (BFS/DFS)

O(V + E)

Visits vertices proportional to edges encountered.

Edge lookup (adj list)

O(degree)

Scrolls neighbors stored per node.

Pathfinding

O(E log V)

Dijkstra with priority queue when weights are non-negative.

Best practices

• Keep edges directional even when graph is conceptually undirected; explicit edges avoid double counting.
• Index high-degree nodes separately to prevent hotspot traversals.
• Cache traversal results (reachability, connected components) when the graph is mostly read-heavy.

Common pitfalls

• Graph algorithms are memory bound; failing to compress IDs explodes storage.
• Recursive DFS can overflow on large or cyclic graphs; convert to iterative.
• Ignoring cycle detection leads to infinite loops in dependency resolution.

Every kind of Graphs

Interviewers rarely say which flavor they mean — they expect you to recognize it from the problem. Each variant below comes with the algorithms it unlocks.

Type 1 of 8

Undirected Graph

→ full page

Edges have no direction — if A connects to B, B connects to A. The simplest mental model: friendships, roads, network cables.

What to know

Stored as adjacency list (sparse, most common) or adjacency matrix (dense, O(1) edge check).
A connected component is a set of nodes all reachable from each other.
Cycles exist whenever edges ≥ nodes within a component.
Degree of a node = number of edges touching it.

Algorithms to reach for

BFS (Breadth-First Search)

O(V + E)

Shortest path in unweighted graphs, level-order exploration

DFS (Depth-First Search)

O(V + E)

Explore all paths, detect cycles, flood fill

Union-Find (Disjoint Set)

O(α(n)) per op

Count/merge connected components, detect cycles online

Tarjan’s bridges & articulation points

O(V + E)

Find edges/nodes whose removal disconnects the graph

In the wild: Facebook friend graphs, LAN topology, road networks without one-way streets.

Practice problems — hints, approach & solution on their own pages

Number of ProvincesMedium Redundant ConnectionMedium Critical Connections in a NetworkHard

Type 2 of 8

Directed Graph (Digraph)

→ full page

Edges point one way: A → B does not imply B → A. Models dependency, flow, and hierarchy.

What to know

Each node has separate in-degree and out-degree.
Cycle detection needs three DFS states (white/gray/black) — a gray→gray edge is a back edge.
Strongly connected component (SCC): every node reaches every other node within it.
Reversing all edges (transpose) is a key trick used by Kosaraju’s algorithm.

Algorithms to reach for

DFS cycle detection (3-color)

O(V + E)

Detect deadlocks / circular dependencies

Kosaraju / Tarjan SCC

O(V + E)

Collapse strongly connected components

Kahn’s algorithm (BFS topo sort)

O(V + E)

Order tasks by dependency, detect cycles by leftover nodes

In the wild: Twitter follows, web page links, import graphs, deadlock detection in databases.

Practice problems — hints, approach & solution on their own pages

Course ScheduleMedium Find Eventual Safe StatesMedium

Type 3 of 8

DAG (Directed Acyclic Graph)

→ full page

A digraph with no cycles — there is always a valid linear ordering of nodes (topological order). The backbone of schedulers and build systems.

What to know

Topological order is not unique; any order respecting all edges is valid.
Dynamic programming on a DAG processes nodes in topological order.
Longest path is NP-hard on general graphs but linear-time on DAGs.
Course Schedule (LeetCode 207/210) is the canonical interview DAG problem.

Algorithms to reach for

Topological sort (Kahn or DFS)

O(V + E)

Linearize dependencies (build order, course order)

DAG shortest/longest path (DP)

O(V + E)

Critical path in project scheduling

Memoized DFS counting

O(V + E)

Count paths between nodes without recomputation

In the wild: Makefiles/CI pipelines, Airflow task DAGs, Git commit history, spreadsheet formula evaluation.

Practice problems — hints, approach & solution on their own pages

Course Schedule IIMedium All Paths From Source to TargetMedium Longest Increasing Path in a MatrixHard

Type 4 of 8

Weighted Graph

→ full page

Every edge carries a cost (distance, latency, price). "Shortest" now means minimum total weight, not fewest hops — BFS is no longer enough.

What to know

Dijkstra requires non-negative weights; one negative edge breaks its greedy proof.
Bellman-Ford tolerates negative edges and detects negative cycles with one extra relaxation round.
Floyd-Warshall computes all-pairs distances with three nested loops.
A* = Dijkstra + admissible heuristic; it never expands more nodes than Dijkstra.

Algorithms to reach for

Dijkstra (min-heap)

O((V + E) log V)

Single-source shortest path, non-negative weights

Bellman-Ford

O(V · E)

Shortest path with negative edges, arbitrage detection

Floyd-Warshall

O(V³)

All-pairs shortest paths on small dense graphs

A* search

O(E log V), often far less

Goal-directed pathfinding with a heuristic

In the wild: Google Maps routing, network latency optimization, flight price search, game NPC pathfinding.

Practice problems — hints, approach & solution on their own pages

Network Delay TimeMedium Cheapest Flights Within K StopsMedium Path With Minimum EffortMedium

Type 5 of 8

Weighted Undirected Graph → Minimum Spanning Tree

→ full page

Connect all nodes with minimum total edge weight and no cycles. The result is always a tree with exactly V−1 edges.

What to know

Kruskal sorts edges globally and unions components — great for sparse graphs and edge lists.
Prim grows one tree outward with a heap — great when adjacency lists are already built.
The cut property proves both: the lightest edge crossing any cut belongs to some MST.
If all edge weights are distinct the MST is unique.

Algorithms to reach for

Kruskal + Union-Find

O(E log E)

MST from a sorted edge list

Prim + min-heap

O(E log V)

MST grown from a start node

In the wild: Laying fiber/electric cable at minimum cost, network design, clustering (single-linkage).

Practice problems — hints, approach & solution on their own pages

Min Cost to Connect All PointsMedium Find Critical and Pseudo-Critical Edges in MSTHard

Type 6 of 8

Bipartite Graph

→ full page

Nodes split into two groups with edges only across groups — never within. Equivalent to "2-colorable" and to "no odd-length cycle".

What to know

Check bipartiteness by BFS/DFS coloring: alternate colors, any same-color edge fails it.
Matching = pairing nodes across the two sides so no node is used twice.
Maximum matching relates to minimum vertex cover via Kőnig’s theorem.

Algorithms to reach for

BFS/DFS two-coloring

O(V + E)

Verify a graph is bipartite (LeetCode 785)

Hungarian algorithm

O(V³)

Minimum-cost assignment of workers to jobs

Hopcroft-Karp

O(E · √V)

Maximum bipartite matching fast

In the wild: Matching riders to drivers, students to schools, ads to slots, jobs to machines.

Practice problems — hints, approach & solution on their own pages

Is Graph Bipartite?Medium Possible BipartitionMedium

Type 7 of 8

Flow Network

→ full page

A digraph where edges have capacities and material "flows" from a source to a sink. Max-flow equals min-cut — the deepest duality in graph theory.

What to know

Residual graph tracks remaining capacity plus reverse "undo" edges.
Ford-Fulkerson repeatedly finds augmenting paths until none remain.
Many matching and scheduling problems reduce to max-flow.

Algorithms to reach for

Edmonds-Karp (BFS Ford-Fulkerson)

O(V · E²)

Max flow with guaranteed termination

Dinic’s algorithm

O(V² · E)

Max flow on larger networks via level graphs

In the wild: Traffic/pipeline capacity planning, image segmentation, sports elimination, project selection.

Type 8 of 8

Grid as an Implicit Graph

→ full page

A 2D matrix where each cell is a node and neighbors are edges — no adjacency list ever built. The most common disguise a graph wears in interviews.

What to know

Number of Islands, Rotting Oranges, Word Search are all graph problems on grids.
Directions array [(0,1),(1,0),(0,-1),(-1,0)] replaces adjacency lists.
Multi-source BFS starts the queue with every source cell at distance 0.
Visited state can be stored in the grid itself to save memory.

Algorithms to reach for

Flood fill (DFS/BFS)

O(rows · cols)

Count islands, fill regions

Multi-source BFS

O(rows · cols)

Nearest-exit / rotting-oranges style spreading

0-1 BFS (deque)

O(rows · cols)

Shortest path when edges cost 0 or 1

In the wild: Image editing flood fill, game maps, maze solving, wildfire/epidemic spread simulation.

Practice problems — hints, approach & solution on their own pages

Number of IslandsMedium Rotting OrangesMedium Shortest Path in Binary MatrixMedium Word SearchMedium

Signature algorithms

Algorithm

Breadth-first search

Guarantees the shortest number-of-edges path in an unweighted graph by exploring layer by layer.

Time

O(V + E)

Space

O(V)

function bfs(graph, start) {
  const queue = [start];
  const seen = new Set([start]);
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph[node] ?? []) {
      if (!seen.has(neighbor)) {
        seen.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

Algorithm

Depth-first search

Follow one path as deep as possible before backtracking; excellent for cycle detection and topological sorts.

Time

O(V + E)

Space

O(V)

function dfs(graph, node, seen = new Set(), order = []) {
  if (seen.has(node)) return order;
  seen.add(node);
  order.push(node);
  for (const neighbor of graph[node] ?? []) {
    dfs(graph, neighbor, seen, order);
  }
  return order;
}

Algorithm

Dijkstra’s algorithm

Uses a priority queue to compute the shortest weighted path in graphs with non-negative edge weights.

Time

O(E log V)

Space

O(V)

function dijkstra(graph, start) {
  const dist = {};
  Object.keys(graph).forEach((node) => (dist[node] = Infinity));
  dist[start] = 0;
  const pq = [[0, start]];
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [distance, node] = pq.shift();
    if (distance > dist[node]) continue;
    for (const edge of graph[node] ?? []) {
      const nextDist = distance + edge.weight;
      if (nextDist < dist[edge.to]) {
        dist[edge.to] = nextDist;
        pq.push([nextDist, edge.to]);
      }
    }
  }
  return dist;
}

Pseudo Code • Shortest path with BFS (unweighted graph)

Flow Diagram

Enqueue the start node with distance 0 and mark it visited.
While queue not empty: dequeue node, and if it is the target, return distance.
For each neighbor, if unseen, mark visited, enqueue with distance + 1, and record the previous node to rebuild the path.
If traversal ends without hitting target, no route exists.

Hands-on code

Compare how the same idea looks in JavaScript, Python, and Go.

function shortestPath(graph, start, target) {
  const queue = [[start, 0]];
  const visited = new Set([start]);

  while (queue.length) {
    const [node, dist] = queue.shift();
    if (node === target) return dist;
    for (const neighbor of graph[node] ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }
  return -1;
}