Skip to content
Tutorials Center
My learning

Topics

Lesson 89 of 135 ยท Data Structures in C

Graphs and Heaps in C

Build a graph with adjacency lists and a binary min-heap in C - add edges, run BFS and DFS, push and pop a priority queue, and learn the index math behind heaps.

Linked lists, trees and hash tables cover a lot of ground, but two more structures show up constantly in real programs. A graph models anything made of things and connections: road maps, social networks, build dependencies, game levels. A heap is a compact tree stored in an array that always hands you the smallest (or largest) item first, which makes it the engine behind priority queues, schedulers and shortest-path algorithms.

In this lesson you will build both from scratch in C. The graph uses adjacency lists, an array of linked lists, with breadth-first and depth-first traversal. The heap is a binary min-heap stored in a dynamic array, where parent and child positions are found with simple index arithmetic rather than pointers.

Graph vocabulary

A graph is a set of vertices (also called nodes) joined by edges. In an undirected graph an edge works in both directions, like a two-way street. In a directed graph each edge has a direction, like a one-way street or a "follows" relationship. Edges can also carry a weight, such as a distance.

flowchart LR
    A((0)) --- B((1))
    A --- C((2))
    B --- D((3))
    C --- D
    D --- E((4))

An undirected graph with five vertices and five edges. Vertex 3 touches vertices 1, 2 and 4.

There are two classic ways to store a graph:

  • An adjacency matrix is a V x V table where cell [a][b] says whether an edge exists. Checking one edge is instant, but the table always uses V x V memory, even when almost no edges exist.
  • An adjacency list keeps, for each vertex, a list of its neighbors. It uses memory proportional to V + E and lets you visit a vertex's neighbors quickly. Most real graphs are sparse (few edges compared with V x V), so adjacency lists are the default choice.

An adjacency-list graph

The graph is a struct holding the vertex count and an array of list heads. Each list node stores a neighbor index and the next node. For an undirected graph, adding an edge adds two list entries, one in each direction.

C
struct edge {
    int to;
    struct edge *next;
};

struct graph {
    int vertex_count;
    struct edge **adjacent;      /* adjacent[v] = first neighbor of v */
};

Insertion at the head of a list is O(1), so building the graph is fast. The price is that neighbors appear in reverse order of insertion; that is worth remembering when you read the output below.

C Building a graph and listing neighbors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Notice that graph_free walks every list and frees each edge before freeing the array of heads and the graph itself. Memory in this structure is spread across many small allocations, so forgetting one level leaks memory (see memory errors).

Two traversals visit every vertex reachable from a start vertex. Both need a visited array, otherwise cycles would make them loop forever.

  • Breadth-first search (BFS) visits the start vertex, then all its neighbors, then their neighbors, and so on, spreading out in rings. It uses a queue, and it finds the fewest-edges path in an unweighted graph.
  • Depth-first search (DFS) follows one path as deep as it can, then backs up and tries the next branch. It is naturally recursive (the call stack acts as the stack), and it powers cycle detection, topological sorting and maze solving.
flowchart TD
    S["start: mark visited, push 0"] --> Q{"queue empty?"}
    Q -- no --> P["pop vertex v, print it"]
    P --> N["for each unvisited neighbor:<br/>mark visited, push"]
    N --> Q
    Q -- yes --> E["done"]

Breadth-first search: marking vertices when they are pushed, not when they are popped, keeps any vertex from entering the queue twice.

Because every vertex enters the queue at most once, the queue never needs more than V slots, so a plain array with head and tail indexes is enough.

C BFS, DFS and shortest hop counts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Both traversals take O(V + E) time: each vertex is visited once and each edge is examined once or twice. Vertex 5 never appears in either output, because it is not connected to vertex 0. To cover a graph with several separate pieces, loop over all vertices and start a new search from each one that is still unvisited.

Heaps

Now to a different structure. Suppose you repeatedly insert numbers and want to remove the smallest one each time (a priority queue). A sorted array makes removal cheap but insertion slow; an unsorted array does the opposite. A binary heap gets both operations down to O(log n).

A min-heap is a binary tree with two properties:

  1. Shape: every level is full except possibly the last, which fills from left to right (a "complete" tree).
  2. Order: every parent is smaller than or equal to its children. The smallest value is therefore always at the root.

The shape property means the tree needs no pointers at all. Store it level by level in an array, and the relatives of the item at index i (starting at 0) are found by arithmetic:

  • parent: (i - 1) / 2
  • left child: 2 * i + 1
  • right child: 2 * i + 2
flowchart TD
    A["2 (index 0)"] --> B["5 (index 1)"]
    A --> C["3 (index 2)"]
    B --> D["9 (index 3)"]
    B --> E["6 (index 4)"]
    C --> F["8 (index 5)"]

The heap stored in the array [2, 5, 3, 9, 6, 8]. Index 4 holds 6; its parent is index (4 - 1) / 2 = 1, which holds 5.

Push and pop

Push adds the new value at the end of the array (the next free slot in the last level) and then sifts it up: while it is smaller than its parent, swap them. The tree height is about log2(n), so this takes at most that many swaps.

Pop removes the root. To keep the tree complete, move the last element into the root's place, then sift it down: swap it with the smaller child until neither child is smaller than it.

The heap needs room to grow, so it is a dynamic array whose capacity doubles when full.

C A min-heap priority queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The popped values come out sorted. That is the idea behind heapsort: push everything, pop everything, and you have sorted the data in O(n log n) time. (The in-place version of heapsort builds the heap inside the original array.) Compare it with the other methods in sorting algorithms.

Why this matters

Heaps appear wherever you need "the next most important thing": a task scheduler picking the highest-priority job, an event simulator choosing the earliest event, merging several sorted files, finding the top k items in a stream, and Dijkstra's shortest-path algorithm on weighted graphs, which repeatedly pops the closest unvisited vertex from a heap. C has no built-in heap, so every one of these programs carries a small struct like the one above. For a max-heap, flip the two comparisons, or store negated values. To make a heap of structures, add a comparison function pointer (see function pointers) as qsort does.

Common mistakes

  • Forgetting to mark vertices as visited in a search with cycles, so it never ends.
  • Marking visited when popping instead of pushing in BFS, which can enqueue a vertex many times.
  • Using recursion for DFS on a huge graph. A path with a million vertices overflows the call stack; use an explicit stack array instead.
  • Popping an empty heap. Check size > 0 first; the function above assumes the caller did.
  • Mixing up 0-based and 1-based heap formulas. With 1-based indexes the children of i are 2i and 2i + 1; with 0-based they are 2i + 1 and 2i + 2.
  • Leaking on cleanup. A graph owns many small allocations; free each edge, then the array, then the graph.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. When is an adjacency list a better choice than an adjacency matrix?

    A list uses memory proportional to V + E, while a matrix always uses V x V cells. A matrix wins for dense graphs or when single-edge lookups dominate.
  2. 2. Which data structure does breadth-first search use to decide what to visit next?

    A queue gives first-in, first-out order, so all vertices at distance 1 are visited before those at distance 2, and so on.
  3. 3. In a 0-based array heap, where is the left child of the item at index 5?

    The left child of index i is 2*i + 1 = 11. The right child is 12, and the parent of index 5 is (5 - 1) / 2 = 2.
  4. 4. What does heap_pop do right after removing the root?

    Moving the last element keeps the tree complete. Sifting it down, swapping with the smaller child, restores the ordering in O(log n).
  5. 5. What is the time cost of push and pop on a binary heap with n items?

    Each operation moves an item along one root-to-leaf path, and a complete binary tree with n nodes has height about log2(n).

Summary

  • A graph is vertices plus edges; adjacency lists store each vertex's neighbors and use O(V + E) memory.
  • An undirected edge is stored twice, once per endpoint; inserting at the head of a list is O(1).
  • BFS uses a queue and finds fewest-edge paths; DFS uses recursion or an explicit stack; both need a visited array and run in O(V + E).
  • A binary min-heap is a complete tree stored in an array: parent (i - 1) / 2, children 2i + 1 and 2i + 2.
  • Push sifts the new item up; pop moves the last item to the root and sifts it down; both are O(log n).
  • Heaps power priority queues, heapsort, top-k problems and Dijkstra's algorithm.

Next: Multi-File Programs, where you learn to split larger programs like these into headers and source files.