Graph

Explanation

A graph G = (V, E) is defined by a set of vertices V and a set of edges E connecting pairs of vertices. Graphs generalize trees: a tree is a connected, acyclic, undirected graph. Remove the acyclic constraint and you get a general graph. Key graph properties: directed vs. undirected (do edges have direction? Twitter follows are directed; Facebook friendships are undirected), weighted vs. unweighted (do edges have costs? Road distances are weighted), cyclic vs. acyclic (does the graph have cycles? DAGs — Directed Acyclic Graphs — are used for dependency resolution and topological sort), connected vs. disconnected (can you reach every vertex from every other vertex?). Graphs are typically represented in two ways: an adjacency list (an array or hash map where each vertex maps to a list of its neighbors — O(V+E) space, efficient for sparse graphs) or an adjacency matrix (a V×V matrix where matrix[i][j] = 1 if an edge exists — O(V²) space, efficient for dense graphs and O(1) edge lookup). Most real-world graphs are sparse (few edges relative to vertices), making adjacency lists the default choice. Real-world graphs: social networks (users = vertices, friendships = edges), web pages (pages = vertices, hyperlinks = edges — what PageRank operates on), road maps (intersections = vertices, roads = edges), dependency graphs (npm packages), circuit boards, and knowledge graphs.

Code Example

// Undirected graph as adjacency list
class Graph {
  constructor() { this.adj = new Map(); }

  addVertex(v) {
    if (!this.adj.has(v)) this.adj.set(v, []);
  }

  addEdge(u, v) {
    this.addVertex(u); this.addVertex(v);
    this.adj.get(u).push(v);
    this.adj.get(v).push(u); // undirected
  }

  // BFS — shortest path in unweighted graph
  bfs(start) {
    const visited = new Set([start]);
    const queue = [start];
    const order = [];
    while (queue.length) {
      const v = queue.shift();
      order.push(v);
      for (const neighbor of this.adj.get(v)) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return order;
  }
}

const g = new Graph();
['A','B','C','D'].forEach(v => g.addVertex(v));
g.addEdge('A','B'); g.addEdge('A','C'); g.addEdge('B','D');
console.log(g.bfs('A')); // ['A', 'B', 'C', 'D']

Why It Matters for Engineers

Graph problems appear in almost every domain of software engineering: route planning (GPS navigation uses Dijkstra's algorithm on a weighted graph), dependency resolution (npm, Maven, and pip all solve topological sort on a dependency DAG), social network features (finding mutual friends, detecting communities), and web crawlers (BFS on the hyperlink graph of the internet). Understanding graphs also unlocks a class of algorithm problems that initially look unrelated but reduce to graph traversal: number of islands (BFS/DFS on a 2D grid), course schedule (cycle detection in a DAG), and word ladder (BFS on a word-transformation graph). Recognizing the graph structure in a problem is the first step to solving it.