DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All data structures

Non-Linear Data Structures

Graphs

Vertices connected by edges — the most general way to model relationships and networks.

Interactive2 visualizer(s)

1Introduction

Maps, social networks, the web, course prerequisites and computer networks are all graphs. Learning to model a problem as a graph unlocks a huge toolbox: BFS, DFS, shortest paths, spanning trees and topological sorting.

2What is it?

A graph G = (V, E) is a set of vertices V and a set of edges E connecting pairs of vertices. Edges can be undirected (friendship) or directed (follows), and weighted (distance) or unweighted.

3Why do we use it?

  • Model any network of relationships.
  • Find shortest routes and connectivity.
  • Schedule tasks with dependencies.
  • Detect cycles and communities.

4Real-world examples

  • Road maps and GPS navigation.
  • Social networks (friends, followers).
  • Web pages and hyperlinks.
  • Course prerequisites.

5Internal working

Adjacency list: for every vertex, a list of its neighbours. Space O(V + E) — best for sparse graphs.

Adjacency matrix: a V × V table where cell [u][v] marks an edge. O(1) edge lookup but O(V²) space.

Traversals keep a visited set so each vertex is processed once, even when the graph has cycles.

6Memory representation

Undirected graph and its adjacency list:

   A --- B --- D
   |     |     |
   C     E     G
    \   /     /
      F ------

A: [B, C]      B: [A, D, E]   C: [A, F]
D: [B, G]      E: [B, F]      F: [C, E, G]
G: [D, F]

7Operations

OperationHow it works
Add vertexNew empty adjacency list.
Add edgeAppend to both lists (undirected).
Check edge (u, v)Scan u's list (matrix: O(1)).
BFS / DFSEvery vertex and edge once.
Shortest path (unweighted)BFS distances.

8Visual explanation

Graph BFS (Breadth-First Search)interactive Open full visualizer
ABCDEFG

Queue (front → rear)

empty

Traversal order

—
Current vertexIn queueDiscoveredProcessedUnvisited

Explores the graph level by level using a queue. Because vertices are discovered in order of distance, BFS also finds the shortest path (fewest edges) from the start in an unweighted graph.

1 / 78
Graph DFS (Depth-First Search)Open the step-by-step visualizer

9Code implementation

Complete, runnable programs (verified in all four languages). JavaScript and Python can be executed in the Coding Playground.

function bfs(graph, start) {
  const visited = new Set([start]);
  const dist = { [start]: 0 };
  const queue = [start];
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        dist[neighbor] = dist[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return { order, dist };
}

const edges = [["A", "B"], ["A", "C"], ["B", "D"], ["B", "E"], ["C", "F"], ["E", "F"], ["D", "G"], ["F", "G"]];
const graph = {};
for (const [u, v] of edges) {
  (graph[u] ??= []).push(v);
  (graph[v] ??= []).push(u);
}
const { order, dist } = bfs(graph, "A");
console.log("BFS order:", order.join(" -> "));
console.log("Distances:", order.map((v) => v + "=" + dist[v]).join(", "));

10Time complexity

OperationTime
Add vertexO(1)
Add edgeO(1)
Check edge (u, v)O(deg u)
BFS / DFSO(V + E)
Shortest path (unweighted)O(V + E)

11Space complexity

Adjacency lists use O(V + E); adjacency matrices use O(V²). BFS/DFS need O(V) extra space for the visited set and queue/stack.

12Advantages

  • Extremely expressive.
  • Rich set of well-studied algorithms.
  • Adjacency lists are compact for sparse graphs.

13Disadvantages

  • Many algorithms are complex to implement correctly.
  • Dense graphs are memory-heavy.
  • Cycles require careful visited tracking.

14Common mistakes

  • Forgetting to mark vertices visited → infinite loops on cycles.
  • Marking visited on dequeue in BFS (vertices get enqueued multiple times).
  • Adding an undirected edge in only one direction.
  • Ignoring disconnected components (loop over all vertices).
  • Using BFS for shortest paths in weighted graphs (use Dijkstra).

15Interview questions

Number of IslandsMedium

16Practice exercises

  1. Count connected components.
  2. Detect a cycle in an undirected graph.
  3. Check whether a graph is bipartite.
  4. Find the shortest path in a grid with obstacles.
  5. Clone a graph.

Try them in the Coding Playground.

On this page

  1. 01Introduction
  2. 02What is it?
  3. 03Why do we use it?
  4. 04Real-world examples
  5. 05Internal working
  6. 06Memory representation
  7. 07Operations
  8. 08Visual explanation
  9. 09Code implementation
  10. 10Time complexity
  11. 11Space complexity
  12. 12Advantages
  13. 13Disadvantages
  14. 14Common mistakes
  15. 15Interview questions
  16. 16Practice exercises