Command Palette

Search for a command to run...

Hectal

Module 20

Graph Fundamentals

Nodes and edges: directed, undirected and weighted graphs, adjacency lists and matrices, degrees, and grids treated as graphs.

Intermediate 4 lessons 6 problems ~45 min of lessons
Graph BFSGraph DFS and Flood FillMatrix Traversal

A graph is the most general structure in this course: things (nodes) and connections between them (edges). Road maps, social networks, course prerequisites, web links and game boards are all graphs. Trees and linked lists are special graphs with extra rules.

This module gives you the vocabulary and the three ways to store a graph in code, shows how to read problems as graphs (including 2D grids, where every cell is a node), and solves first problems that need nothing more than degrees and a single traversal. The next modules build BFS, DFS, topological sort, union-find, shortest paths and spanning trees on top of it.

Best after: Binary Trees

Part 1

Learn the ideas

  1. 20.1What a Graph IsNodes (vertices) joined by edges. Edges can be one-way or two-way, weighted or not; the graph can have cycles and many components.12 min
  2. 20.2Storing a Graph: Edge List, Matrix, Adjacency ListProblems usually hand you an edge list; you almost always convert it to an adjacency list, which uses O(V + E) memory and lists each node's neighbours directly.14 min
  3. 20.3Grids Are GraphsIn a 2D grid each cell is a node and its up/down/left/right cells are its neighbours. A direction array and a bounds check replace the adjacency list.10 min
  4. 20.4Which Graph Algorithm?The question decides the algorithm: reachability, fewest steps, ordering, grouping, cheapest path or cheapest network.8 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 20.1Find Center of Star GraphEasyGraph BFS

    Reading structure from edges: the centre is the node shared by every edge, so two edges are enough.

  2. 20.2Find the Town JudgeEasyGraph BFS

    In-degree and out-degree on a directed graph, computed straight from the edge list.

  3. 20.3Find if Path Exists in GraphEasyGraph BFS

    The first traversal: build an adjacency list, then explore from the source with a visited array.

  4. 20.4Minimum Number of Vertices to Reach All NodesMediumTopological Sort

    In-degree reasoning on a DAG: a node with no incoming edge can only be reached by starting there.

  5. 20.5Maximal Network RankMediumGraph BFS

    Degrees plus an adjacency matrix for O(1) "are these two connected?" checks.

  6. 20.6Island PerimeterEasyMatrix Traversal

    Grid as graph without a traversal: count land cells and shared sides.