Jaconir
Skip to lesson
FoundationsPatternsGraphs / DPInterview
medium
35 minIntern through senior

When to use. Anything that is nodes plus edges: maps, dependencies, social graphs, grids as graphs.

Complexity. Time BFS/DFS O(V + E); Dijkstra O((V + E) log V) with a heap. Space O(V + E) for the adjacency list.

Who gets asked. Grid BFS is intern/mid. Cycle detection, topo sort, and weighted shortest path are mid/senior.

Prereq. Trees, queues, hash tables.

Graphs: Networks of Data

Explore graphs, the data structure that models complex networks and relationships, from social networks to GPS navigation.

What Is a Graph?

A graph is a non-linear data structure consisting of **nodes** (or vertices) and **edges**. An edge is a connection between two nodes. Unlike trees, graphs can have cycles (a path that starts and ends at the same node) and nodes can be connected in any way, making them perfect for representing networks.

Key Concepts

  • Directed vs. Undirected: In a directed graph, edges have a direction (like a one-way street). In an undirected graph, edges are two-way.
  • Weighted vs. Unweighted: In a weighted graph, each edge has a "cost" or "weight". This is used in GPS systems to represent distance or travel time.
  • Adjacency List: The most common way to represent a graph in code, where each node has a list of its neighbors. Time for BFS/DFS is O(V + E).

Grid BFS (islands, shortest unweighted path) is intern/mid. Cycle detection and topological sort are mid. Weighted shortest path is Dijkstra with a heap — BFS is wrong once edges have weights. Dynamic connectivity is union-find, not a full DFS from scratch after every new edge.

Interactive Graph
Build your own graph and see its representation. This visualizer demonstrates key graph concepts like **directed/undirected** edges, **weights**, and the underlying **adjacency list** data structure.
5247311ABCDEF
{
"A": [{ node: "B", weight: 5 }, { node: "C", weight: 2 }],
"B": [{ node: "A", weight: 5 }, { node: "D", weight: 4 }, { node: "E", weight: 1 }],
"C": [{ node: "A", weight: 2 }, { node: "E", weight: 7 }],
"D": [{ node: "B", weight: 4 }, { node: "F", weight: 3 }],
"E": [{ node: "B", weight: 1 }, { node: "C", weight: 7 }, { node: "F", weight: 1 }],
"F": [{ node: "D", weight: 3 }, { node: "E", weight: 1 }],
}
Traversal Visualizer (BFS & DFS)
See how different algorithms explore a graph.BFS (Breadth-First Search) explores level by level, using a Queue (FIFO).DFS (Depth-First Search) goes as deep as possible down one path before backtracking, using a Stack (LIFO).
ABCDEFGH
[]

Note: When a node has multiple neighbors, they are processed in alphabetical order for consistency.

Interview Problems
Find the shortest path between two nodes in an unweighted graph. This is a classic application of Breadth-First Search (BFS).
ABCDEF
Start. Queue has [A].
[A]
{ A }

function findShortestPath(adjList, start, end) {
  // Queue stores paths, starting with the start node
  const queue = [[start]];
  // Visited set to prevent cycles and redundant checks
  const visited = new Set([start]);

  while (queue.length > 0) {
    // Get the first path from the queue (FIFO)
    const path = queue.shift();
    const node = path[path.length - 1];

    // If we reached the end, return the path
    if (node === end) {
      return path;
    }

    // Explore neighbors
    for (const neighbor of (adjList[node] || [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        const newPath = [...path, neighbor];
        queue.push(newPath);
      }
    }
  }

  // If the queue is empty and we haven't found the end
  return null; // No path exists
}
Coding Challenge
Each node holds a value and a list of neighbors. Given one node in a connected undirected graph, return a deep copy so mutations to the copy never touch the original. Use a map from original node to copy to avoid walking a cycle forever.
Quick Quiz: Test Your Knowledge

Which traversal algorithm is best suited for finding the shortest path in an unweighted graph?

Can a graph have cycles?

In an adjacency list representation of a graph, what do the values in the list for a given key represent?

J
Dafin Edison J
Creator & Developer of Jaconir

I build things for the web. From immersive games to practical tools, my goal is to create products that people love to use and to share the knowledge I've gained along the way.

Saved in this browser. No account.

PreviousTrees
NextUnion-Find