Graphs

A graph is one of the most powerful and versatile data structures in computer science. Unlike arrays, trees, or linked lists, a graph can model virtually any relationship between objects — from road networks and social connections to package dependencies and web links.

Note

A graph G is defined as G = (V, E) where V is a set of vertices (nodes) and E is a set of edges (connections between vertices). Almost every real-world network is a graph.

Vertices and Edges

The two building blocks of every graph are vertices and edges. A vertex (also called a node) represents an entity. An edge represents a relationship or connection between two vertices.

Graph with 5 vertices and 5 edges:

    (A)----(B)
     |      |  \
     |      |   (E)
     |      |  /
    (C)----(D)

  Vertices: { A, B, C, D, E }
  Edges:    { A-B, A-C, B-D, B-E, C-D, D-E }

Directed vs Undirected Graphs

In an undirected graph, edges have no direction — if A is connected to B, then B is also connected to A. Think of a two-way street. In a directed graph (digraph), each edge has a direction — an arrow pointing from one vertex to another. Think of a one-way street or a Twitter follow relationship.

UNDIRECTED GRAPH           DIRECTED GRAPH (Digraph)

  (A)----(B)                   (A) ──► (B)
   |      |                     |       |
   |      |                     ▼       ▼
  (C)----(D)                   (C) ◄── (D)

  A-B means A connects to B    A→B means A points to B
  AND B connects to A          but B does NOT point to A

Undirected: friendship on Facebook, road networks, molecule bonds
Directed: Twitter follows, web links, task dependencies, call graphs

Weighted vs Unweighted Graphs

A weighted graph assigns a numeric value (weight) to each edge. Weights commonly represent distance, cost, time, or capacity. An unweighted graph treats all edges as equal.

WEIGHTED GRAPH (road distances in km)

       5km       3km
  (A)-------(B)-------(E)
   |          \         |
  8km        2km       6km
   |            \       |
  (C)-----------(D)----+
         4km

  Shortest path A→E might be A→B→D→E = 5+2+6 = 13km
  Not the direct A→B→E = 5+3 = 8km ... wait, that IS shorter!
  (This illustrates why we need algorithms like Dijkstra's)

Cyclic vs Acyclic Graphs

A cyclic graph contains at least one cycle — a path that starts and ends at the same vertex. An acyclic graph has no cycles. A DAG (Directed Acyclic Graph) is a directed graph with no cycles. DAGs are extremely common in practice: build systems, course prerequisites, version control history.

CYCLIC GRAPH                 ACYCLIC GRAPH (DAG)

  (A)→(B)→(C)              (A)→(B)→(D)
       ↑    |                    ↓    ↓
       +----+               (A)→(C)→(E)

  A→B→C→B is a cycle!      No way to return to a
                            previously visited node

Connected vs Disconnected Graphs

A graph is connected if there is a path between every pair of vertices. A disconnected graph has two or more isolated components with no edges between them. For directed graphs, we use strongly connected (path exists in both directions between every pair) and weakly connected (connected if we ignore edge direction).

CONNECTED GRAPH              DISCONNECTED GRAPH

  (A)---(B)---(C)            (A)---(B)     (D)---(E)
         |                                   |
        (D)---(E)            (C)            (F)

  Every node reachable        Two separate components:
  from every other node       {A,B,C} and {D,E,F}

Graph Vocabulary

Term	Definition	Example
Degree	Number of edges connected to a vertex	In the graph above, B has degree 3
In-degree	Edges pointing INTO a vertex (directed only)	If A→B and C→B, B has in-degree 2
Out-degree	Edges pointing OUT of a vertex (directed only)	If A→B and A→C, A has out-degree 2
Path	Sequence of vertices connected by edges	A→B→C→D is a path of length 3
Cycle	Path that starts and ends at same vertex	A→B→C→A is a cycle
Component	Maximal connected subgraph	A disconnected graph has multiple components
Neighbor	Vertex directly connected by an edge	Neighbors of B: A, C, D
Adjacent	Two vertices sharing an edge	A and B are adjacent if edge A-B exists
Subgraph	A graph formed from a subset of vertices/edges	Remove vertex D to get a subgraph
Spanning tree	Connected acyclic subgraph touching all vertices	Used in Prim's and Kruskal's algorithms

Dense vs Sparse Graphs

The density of a graph describes how many edges it has relative to the maximum possible. For an undirected graph with V vertices, the maximum number of edges is V(V-1)/2. For a directed graph it is V(V-1). - Dense graph: E ≈ V² — many edges, close to the maximum - Sparse graph: E ≈ V — few edges relative to vertices This distinction matters when choosing your graph representation (covered in the next page).

SPARSE GRAPH (6 vertices, 5 edges)    DENSE GRAPH (6 vertices, 13 edges)

  A-B                                   A-B, A-C, A-D, A-E, A-F
  B-C                                   B-C, B-D, B-E, B-F
  C-D                                   C-D, C-E, C-F
  D-E                                   D-E, D-F
  E-F                                   E-F

  Like a long chain                     Nearly every pair connected
  Max edges = 6×5/2 = 15               13 out of 15 possible

Real-World Graph Examples

Application	Vertices	Edges	Type
GPS / Maps	Intersections	Roads with distances	Weighted directed
Social network (Facebook)	People	Friendships	Unweighted undirected
Social network (Twitter)	Users	Follows	Unweighted directed
Package manager (npm)	Packages	Dependencies	Unweighted DAG
Web crawler	Web pages	Hyperlinks	Unweighted directed
Airline routes	Airports	Flights with prices	Weighted directed
Network topology	Servers/routers	Cables	Weighted undirected
Task scheduler	Tasks	Prerequisites	Unweighted DAG
Recommendation engine	Users & items	Ratings/interactions	Weighted bipartite

Graph Properties Summary

// Key graph properties at a glance
const graphTypes = {
  undirected: {
    description: "Edges have no direction",
    edgeSymmetry: "if A-B exists, then B-A exists",
    examples: ["friendship networks", "road maps", "molecule bonds"],
  },
  directed: {
    description: "Edges have direction (arrows)",
    edgeSymmetry: "A→B does NOT imply B→A",
    examples: ["web links", "Twitter follows", "dependencies"],
  },
  weighted: {
    description: "Edges carry a numeric value",
    extras: ["can be directed or undirected"],
    examples: ["road distances", "flight costs", "network latency"],
  },
  dag: {
    description: "Directed Acyclic Graph — no cycles",
    keyProperty: "has a valid topological ordering",
    examples: ["build systems", "course prereqs", "version history"],
  },
};

// Simple graph as adjacency list (JavaScript)
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "D"],
  D: ["B", "C"],
  E: ["B"],
};

// Check neighbors
console.log(graph["B"]); // ["A", "D", "E"]

// Count edges (undirected — each edge counted twice)
const edgeCount = Object.values(graph)
  .reduce((sum, neighbors) => sum + neighbors.length, 0) / 2;
console.log("Edge count:", edgeCount); // 5

Common Graph Problems

Graphs unlock an enormous class of algorithmic problems. Here is a map of the most important ones:

Problem	Algorithm(s)	Use Case
Traversal (visit all nodes)	BFS, DFS	Web crawling, reachability
Shortest path (unweighted)	BFS	Minimum hops in a network
Shortest path (weighted)	Dijkstra's, Bellman-Ford	GPS navigation
All-pairs shortest path	Floyd-Warshall	Network routing tables
Minimum spanning tree	Kruskal's, Prim's	Cable/network layout
Cycle detection	DFS (color marking)	Deadlock detection
Topological sort	DFS, Kahn's algorithm	Build order, task scheduling
Strongly connected components	Kosaraju's, Tarjan's	Web community detection
Bipartite check	BFS 2-coloring	Matching problems
Max flow / Min cut	Ford-Fulkerson	Network capacity, bipartite matching

Graph Traversal: BFS and DFS Overview

The two fundamental ways to explore a graph are Breadth-First Search (BFS) and Depth-First Search (DFS). Both visit every reachable vertex exactly once but in different orders.

Graph:  A - B - D
        |       |
        C       E

BFS from A (level by level):   A → B → C → D → E
DFS from A (go deep first):    A → B → D → E → C  (one possible order)

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A"],
  D: ["B"],
  E: ["B"],
};

// BFS — uses a queue, explores layer by layer
function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const order = [];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift(); // dequeue front
    order.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

// DFS — uses recursion (implicit call stack), goes deep first
function dfs(graph, node, visited = new Set(), order = []) {
  visited.add(node);
  order.push(node);

  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, order);
    }
  }
  return order;
}

console.log("BFS:", bfs(graph, "A")); // ["A", "B", "C", "D", "E"]
console.log("DFS:", dfs(graph, "A")); // ["A", "B", "D", "E", "C"]

Time and Space Complexity

Operation	Time Complexity	Notes
BFS traversal	O(V + E)	Visits every vertex and edge once
DFS traversal	O(V + E)	Same as BFS, just different order
Dijkstra's (binary heap)	O((V + E) log V)	Weighted shortest path
Bellman-Ford	O(V × E)	Handles negative weights
Floyd-Warshall	O(V³)	All-pairs shortest paths
Kruskal's MST	O(E log E)	Sort edges, use Union-Find
Prim's MST	O(E log V)	Grow tree greedily with heap
Topological sort	O(V + E)	Only valid on DAGs

Tip

When solving graph problems, always clarify: Is the graph directed or undirected? Weighted or unweighted? Can it have cycles? Can it be disconnected? These four questions narrow down which algorithm to use.

Classic Graph Problems to Practice

Number of Islands (LeetCode 200) — DFS/BFS on a grid graph
Clone Graph (LeetCode 133) — deep copy with BFS and a node map
Course Schedule (LeetCode 207) — cycle detection in a directed graph
Course Schedule II (LeetCode 210) — topological sort
Network Delay Time (LeetCode 743) — Dijkstra's algorithm
Cheapest Flights Within K Stops (LeetCode 787) — modified Bellman-Ford
Pacific Atlantic Water Flow (LeetCode 417) — multi-source BFS
Word Ladder (LeetCode 127) — BFS shortest path on implicit graph
Reconstruct Itinerary (LeetCode 332) — Eulerian path with DFS
Alien Dictionary (LeetCode 269) — topological sort from character order

Note

The next page covers Graph Representations — how to actually store a graph in memory using adjacency matrices, adjacency lists, and edge lists, and when to choose each.