You might be tempted to think that because a 2D array is the most intuitive way to visualize a grid of connections, it should be your default choice for every graph you implement in C. It feels natural: rows are "from" nodes, columns are "to" nodes, and a 1 means there's a path. It's simple, right?

Here is where that logic falls apart. Imagine you're building a social network graph for a small town of 10,000 people. If you use an adjacency matrix (a 2D array of integers), you're looking at $10,000 \times 10,000$ entries. That's 100 million integers. On a standard system, that's roughly 400MB of memory just to store the structure. But in a real town, most people only know maybe 50 other people. You'd be wasting 99.5% of that memory storing zeros. This is the "sparse graph" problem, and if you try to allocate that on the stack, your program will segfault before it even starts.

The Space Trap vs. The Lookup Win

The adjacency matrix isn't a general-purpose tool; it's a specialized one. I only reach for it when the graph is "dense"—meaning the number of edges is close to the square of the number of vertices—or when I absolutely need to answer the question "Is node A connected to node B?" in constant time, $O(1)$. If you're doing that check thousands of times per second, the matrix is your best friend. If you're mostly iterating over a node's neighbors, you're better off with an adjacency list.

When we implement this in C, we typically wrap the matrix in a struct. This keeps the metadata (like the number of vertices) bundled with the data, preventing you from having to pass around three different variables to every function.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int numVertices;
    int** matrix;
} Graph;

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;

    // Allocate the row pointers
    graph->matrix = malloc(vertices * sizeof(int*));
    for (int i = 0; i < vertices; i++) {
        // Allocate each row and initialize to 0
        graph->matrix[i] = calloc(vertices, sizeof(int));
    }
    return graph;
}

Mapping Vertices to Indices and Flipping Bits

One thing that trips people up is how to handle the "names" of the nodes. A matrix only understands indices (0, 1, 2...). If your graph represents cities like "New York" and "London", you can't use those strings as array indices. You need a mapping system—usually a simple array or a hash map—that assigns "New York" to index 0 and "London" to index 1.

To add an edge, you simply flip the value at the intersection of the two indices. If the graph is undirected (like a friendship), you must flip both [i][j] and [j][i]. If it's directed (like a Twitter follow), you only flip one.

void addEdge(Graph* graph, int src, int dest) {
    if (src < 0 || src >= graph->numVertices || dest < 0 || dest >= graph->numVertices) {
        fprintf(stderr, "Vertex index out of bounds\n");
        return;
    }
    graph->matrix[src][dest] = 1;
    // For undirected graphs, uncomment the line below:
    // graph->matrix[dest][src] = 1;
}

Handling Weights Instead of Booleans

The real power of the matrix emerges when you move beyond simple connectivity. Instead of storing a 1 for "connected" and 0 for "not connected," you can store weights. For example, in a flight map, the value at matrix[src][dest] could be the ticket price or the distance in miles.

I've seen a lot of engineers make the mistake of using 0 to represent "no edge" in a weighted graph. But what if the weight of a path actually is 0? To fix this, use a sentinel value like -1 or a very large constant (Infinity) to represent the absence of an edge. This is a crucial distinction when you eventually start implementing algorithms like Dijkstra's.

📋 Practical Task

Implementing a Weighted City-Distance Matrix

Your task is to create a program that models the distances between four cities: New York (0), London (1), Tokyo (2), and Paris (3). Instead of a simple boolean "connected" matrix, you will implement a weighted adjacency matrix where the values represent distance in kilometers.

Requirements:

• Define a Graph struct that uses a dynamically allocated 2D array.
• Initialize the matrix such that all distances are set to -1 (indicating no direct flight exists).
• Implement a function void addDistance(Graph* g, int src, int dest, int dist) that adds a bidirectional edge (since flights usually go both ways).
• Set the following distances:
  • New York to London: 5570
  • London to Paris: 344
  • Tokyo to London: 9550
  • New York to Tokyo: 10850
• Write a function void printMatrix(Graph* g) that prints the matrix in a grid format.
• Properly free() all allocated memory before the program exits.