Exploring Graphs in C: The Fundamentals

In the vast landscape of data structures, we often encounter scenarios where data isn't neatly ordered in a sequence or organized in a strict hierarchy. Instead, entities might have complex, non-linear relationships. This is where graphs come into play, offering a powerful and versatile way to model such interconnected data.

This entry in our C-Language Series will introduce you to the fundamental concepts of graphs, why they are indispensable, and most importantly, how to represent them efficiently in C.

What is a Graph?

At its core, a graph is a non-linear data structure consisting of two main components:

• Vertices (Nodes): These are the fundamental entities or points in the graph. Think of them as individual items, people, cities, or web pages.
• Edges (Links/Arcs): These represent the connections or relationships between vertices. An edge indicates that two vertices are related in some way.

Graphs can be categorized further based on the nature of their edges:

• Undirected Graph: Edges have no direction. If there's an edge from vertex A to vertex B, it implies a connection from B to A as well (e.g., a friendship on a social network).
• Directed Graph (Digraph): Edges have a specific direction. An edge from A to B means a connection only from A to B, not necessarily from B to A (e.g., following someone on social media).
• Unweighted Graph: Edges simply indicate a connection without any associated cost or value.
• Weighted Graph: Each edge has a numerical value (weight) associated with it, representing a cost, distance, time, or capacity (e.g., distance between two cities on a map).

Why Graphs? Common Applications

Graphs are incredibly versatile and are used to model a myriad of real-world problems. Here are a few prominent examples:

• Social Networks: People are vertices, and friendships/follows are edges.
• GPS and Navigation Systems: Locations (intersections, landmarks) are vertices, and roads/paths are weighted edges (representing distance or travel time).
• Computer Networks: Computers or routers are vertices, and network cables/wireless connections are edges.
• Web Crawlers: Web pages are vertices, and hyperlinks are directed edges.
• Dependency Management: Tasks in a project or software modules are vertices, and dependencies are directed edges.

Representing Graphs in C

How do we translate these abstract concepts into concrete data structures in C? There are two primary ways to represent a graph:

1. Adjacency Matrix
2. Adjacency List

1. Adjacency Matrix Representation

The adjacency matrix uses a 2D array (matrix) where adj[i][j] stores information about the edge between vertex i and vertex j.

• For an unweighted graph, adj[i][j] = 1 if an edge exists between i and j, and 0 otherwise.
• For a weighted graph, adj[i][j] would store the weight of the edge, or an indicator like 0 or infinity if no edge exists.

Pros:

• Fast Edge Lookup: Checking if an edge exists between two vertices takes O(1) time.
• Simpler Implementation: Relatively straightforward to implement.

Cons:

• Space Inefficient: Requires O(V^2) space, where V is the number of vertices. This can be very wasteful for "sparse" graphs (graphs with relatively few edges).
• Adding/Removing Vertices: Can be complex as it requires resizing the entire matrix.

C Code Example (Adjacency Matrix):

Below is a basic structure for representing an unweighted, undirected graph using an adjacency matrix.

#define MAX_VERTICES 100 // Maximum number of vertices

// Represents the graph using an adjacency matrix
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
int numVertices; // Stores the actual number of vertices in the current graph

// Function to initialize the graph with 'V' vertices
void initGraphMatrix(int V) {
    numVertices = V;
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            adjMatrix[i][j] = 0; // Initialize with no edges
        }
    }
}

// Function to add an edge between two vertices (undirected)
void addEdgeMatrix(int src, int dest) {
    if (src >= 0 && src < numVertices && dest >= 0 && dest < numVertices) {
        adjMatrix[src][dest] = 1;
        adjMatrix[dest][src] = 1; // For undirected graph
    } else {
        // Handle error: invalid vertex indices
    }
}

// Function to print the adjacency matrix
void printAdjMatrix() {
    printf("Adjacency Matrix:\n");
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("\n");
    }
}

2. Adjacency List Representation

The adjacency list representation uses an array of linked lists. Each index i in the array corresponds to vertex i, and the linked list at that index contains all vertices adjacent to i.

Pros:

• Space Efficient: Requires O(V + E) space, where E is the number of edges. This is highly efficient for sparse graphs.
• Easier to Add/Remove Vertices and Edges: Modifying the graph is often simpler compared to an adjacency matrix.
• Efficient for Iterating Neighbors: Quickly find all neighbors of a vertex by traversing its linked list.

Cons:

• Slower Edge Lookup: Checking if an edge exists between two specific vertices can take O(degree(V)) time (where degree(V) is the number of neighbors of vertex V), as you might have to traverse the entire linked list.
• More Complex Implementation: Involves dynamic memory allocation and pointer manipulation, which can be more challenging.

C Code Example (Adjacency List):

Here’s how you might set up an unweighted, undirected graph using an adjacency list in C.

#include <stdlib.h> // Required for malloc

// A structure to represent an adjacency list node
// Each node in the list contains a destination vertex and a pointer to the next node.
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

// A structure to represent an adjacency list
// Each graph vertex has an adjacency list. The 'head' pointer points to the first node.
struct AdjList {
    struct AdjListNode *head;
};

// A structure to represent a graph
// The graph itself contains the number of vertices and an array of adjacency lists.
struct Graph {
    int numVertices;
    struct AdjList* array; // An array of AdjList structures
};

// Function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    if (newNode == NULL) {
        // Handle memory allocation failure
        return NULL;
    }
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph with 'V' vertices
struct Graph* createGraph(int numVertices) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    if (graph == NULL) {
        // Handle memory allocation failure
        return NULL;
    }
    graph->numVertices = numVertices;

    // Create an array of adjacency lists. One list for each vertex.
    graph->array = (struct AdjList*) malloc(numVertices * sizeof(struct AdjList));
    if (graph->array == NULL) {
        free(graph); // Clean up previously allocated graph memory
        return NULL;
    }

    // Initialize each adjacency list as empty (head is NULL)
    for (int i = 0; i < numVertices; ++i) {
        graph->array[i].head = NULL;
    }

    return graph;
}

// Adds an edge to an undirected graph
void addEdgeList(struct Graph* graph, int src, int dest) {
    if (src < 0 || src >= graph->numVertices || dest < 0 || dest >= graph->numVertices) {
        // Handle error: invalid vertex indices
        return;
    }

    // Add an edge from src to dest. New node is added at the beginning of src's list.
    struct AdjListNode* newNode = newAdjListNode(dest);
    if (newNode == NULL) return; // Memory allocation failed
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Since graph is undirected, add an edge from dest to src also.
    newNode = newAdjListNode(src);
    if (newNode == NULL) return; // Memory allocation failed
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Function to print the adjacency list representation of the graph
void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->numVertices; ++v) {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

// Don't forget to free allocated memory when the graph is no longer needed
void freeGraph(struct Graph* graph) {
    for (int i = 0; i < graph->numVertices; ++i) {
        struct AdjListNode* current = graph->array[i].head;
        while (current != NULL) {
            struct AdjListNode* next = current->next;
            free(current);
            current = next;
        }
    }
    free(graph->array);
    free(graph);
}

Choosing the Right Representation

The choice between an adjacency matrix and an adjacency list often depends on the specific characteristics of your graph and the operations you'll perform most frequently:

• Use an Adjacency Matrix for dense graphs (graphs with many edges, typically E close to V^2) where you need frequent O(1) checks for edge existence.
• Use an Adjacency List for sparse graphs (graphs with relatively few edges, typically E much smaller than V^2) where space efficiency is crucial, or when you frequently need to iterate through all neighbors of a specific vertex.

Conclusion

Graphs are a foundational concept in computer science, enabling us to model and solve complex problems involving relationships and networks. Understanding their basic components and the two primary representations—adjacency matrix and adjacency list—is the crucial first step. With these building blocks, you're well-equipped to delve into graph traversal algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS), and eventually, more advanced graph algorithms, all implemented effectively in C.