Articles/General

What Is a Graph (Data Structure)?

A graph is a collection of nodes (vertices) connected by edges, representing relationships that don't necessarily form a simple linear or hierarchical struct...

Published November 14, 2026

A graph is a set of nodes (vertices) connected by edges, used to model relationships such as roads, social networks and dependencies. Edges can be directed or undirected, weighted or unweighted.

The concept

Store a graph as an adjacency list (node → neighbours), which is efficient for sparse graphs, or an adjacency matrix for dense ones.

Core algorithms: BFS (shortest path in unweighted graphs), DFS (explore/detect cycles), Dijkstra (weighted shortest path) and topological sort (ordering dependencies).

BFS layer by layer

  1. Start at A, mark visited
  2. Visit all neighbours of A
  3. Then their neighbours, level by level
  4. Stop when the target is found: shortest path

Practical examples

Adjacency list

const g = { A: ['B', 'C'], B: ['D'], C: ['D'], D: [] }

BFS shortest path length

function bfs(g, s, t) {
  const q = [[s, 0]], seen = new Set([s])
  while (q.length) {
    const [n, d] = q.shift()
    if (n === t) return d
    for (const m of g[n]) if (!seen.has(m)) { seen.add(m); q.push([m, d + 1]) }
  }
  return -1
}

DFS cycle-safe traversal

function dfs(g, n, seen = new Set()) { seen.add(n); for (const m of g[n]) if (!seen.has(m)) dfs(g, m, seen); return seen }

Common mistakes

  • Forgetting a visited set and looping forever on cycles.
  • Using an adjacency matrix for huge sparse graphs.
  • Using BFS for weighted shortest paths.

Key takeaways

  • Nodes + edges model relationships.
  • Adjacency list for sparse graphs.
  • BFS, DFS, Dijkstra are the core tools.

FAQ

Tree vs graph?

A tree is a connected graph with no cycles.

Directed vs undirected?

Directed edges have a direction (follows); undirected are two-way (friends).

More General articles