Bytebook Compiler

Graphs & Hashing

Graphs: Terminology & Representation

Vertices and edges: directed, weighted and connected graphs, degree, paths and cycles, and storing graphs as adjacency matrices and adjacency lists.

4 min read1 runnable example4-question quiz

A graph G = (V, E) is a set of vertices (nodes) V connected by edges E. Graphs model anything with connections: road maps, social networks, the web, course prerequisites, computer networks.

ABCDE
An undirected graph with 5 vertices and 6 edges.

Vocabulary

Term Meaning
Undirected graph edges have no direction: A–B means both ways
Directed graph (digraph) edges are arrows: A → B does not imply B → A
Weighted graph each edge carries a number (distance, cost, time)
Adjacent two vertices joined by an edge
Degree number of edges at a vertex; in digraphs, in-degree and out-degree
Path a sequence of vertices joined by edges
Cycle a path that starts and ends at the same vertex
Connected there is a path between every pair of vertices
Tree a connected graph with no cycles (n vertices, n − 1 edges)
DAG directed acyclic graph — a digraph with no directed cycles

Directed and weighted graphs

42158SABT
A weighted directed graph. Shortest-path algorithms like Dijkstra's work on graphs like this.

Representation 1: adjacency matrix

A V × V grid where adj[i][j] = 1 (or the weight) if there is an edge from i to j.

ABCDEA01100B10011C10010D01101E01010
Adjacency matrix of the first graph. It is symmetric because the graph is undirected.
  • Check "is there an edge i–j?" in O(1).
  • Uses O(V²) memory even if there are few edges.
  • Listing a vertex's neighbours takes O(V).

Representation 2: adjacency list

An array of lists: adj[i] holds the neighbours of vertex i.

Text
A: B C
B: A D E
C: A D
D: B C E
E: B D
  • Uses O(V + E) memory — ideal for sparse graphs (most real graphs).
  • Listing neighbours is fast: O(degree).
  • Checking a specific edge takes O(degree).
C
#include <stdio.h>
#include <stdlib.h>

typedef struct Edge { int to; struct Edge *next; } Edge;

#define V 5
Edge *adj[V];
const char *name = "ABCDE";

void addEdge(int u, int v) {                 // undirected: add both directions
    Edge *e = malloc(sizeof(Edge)); e->to = v; e->next = adj[u]; adj[u] = e;
    e = malloc(sizeof(Edge));       e->to = u; e->next = adj[v]; adj[v] = e;
}

int main(void) {
    int edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {1, 4}};
    for (int i = 0; i < 6; i++) addEdge(edges[i][0], edges[i][1]);

    int matrix[V][V] = {0};
    for (int u = 0; u < V; u++) {
        printf("%c:", name[u]);
        int deg = 0;
        for (Edge *e = adj[u]; e; e = e->next) { printf(" %c", name[e->to]); matrix[u][e->to] = 1; deg++; }
        printf("  -> degree %d\n", deg);
    }
    printf("\nAdjacency matrix:\n  ");
    for (int j = 0; j < V; j++) printf(" %c", name[j]);
    printf("\n");
    for (int i = 0; i < V; i++) {
        printf("%c ", name[i]);
        for (int j = 0; j < V; j++) printf(" %d", matrix[i][j]);
        printf("\n");
    }
    return 0;
}
Output
A: C B  -> degree 2
B: E D A  -> degree 3
C: D A  -> degree 2
D: E C B  -> degree 3
E: B D  -> degree 2

Adjacency matrix:
   A B C D E
A  0 1 1 0 0
B  1 0 0 1 1
C  1 0 0 1 0
D  0 1 1 0 1
E  0 1 0 1 0
Try it Yourself

(The list shows neighbours in reverse insertion order because each new edge is added at the head of the list.)

Matrix or list?

Adjacency matrix Adjacency list
Memory O(V²) O(V + E)
Is (u, v) an edge? O(1) O(deg(u))
Visit all neighbours of u O(V) O(deg(u))
Best for dense graphs, quick edge checks sparse graphs, traversals

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    An undirected graph has degrees 3, 3, 2, 2, 2. How many edges does it have?

  2. 2

    How much memory does an adjacency matrix need for V vertices?

  3. 3

    Which representation is better for a sparse graph with a million vertices?

  4. 4

    What is a DAG?

Esc
↑↓ move↵ open