Graph Data Structure In C

Introduction

Graphs are powerful data structures that represent relationships between entities. In computer science, graphs are widely used to solve various problems, from network routing to social network analysis. This article explores the basics of graphs and provides practical examples of C programs to work with them.

What is a Graph?

A graph is a collection of nodes connected by edges. Nodes represent entities, and edges represent relationships between those entities. There are two main types of graphs: directed and undirected.

• Directed Graph (Digraph): Edges have a direction, indicating a one-way relationship.
• Undirected Graph: Edges have no direction, representing a two-way relationship.

Basic Concepts

1. Vertices and Edges

In C, we can represent a graph using structures to define vertices and edges. Consider the following example:

#include <stdio.h>

// Structure to represent a vertex
struct Vertex {
    int data;
};

// Structure to represent an edge
struct Edge {
    struct Vertex* start;
    struct Vertex* end;
};

2. Adjacency Matrix

An adjacency matrix is a 2D array where each element matrix[i][j] represents an edge between vertex i and vertex j. A value of 1 indicates an edge, and 0 indicates no edge.

#include <stdio.h>

#define MAX_VERTICES 100

int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];

// Function to add an edge to the adjacency matrix
void addEdge(int start, int end) {
    adjacencyMatrix[start][end] = 1;
    adjacencyMatrix[end][start] = 1; // For undirected graphs
}

3. Adjacency List

An adjacency list is an array of linked lists, where each array index represents a vertex, and the linked list associated with it contains all adjacent vertices.

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

// Structure to represent a node in the adjacency list
struct Node {
    int data;
    struct Node* next;
};

// Structure to represent an adjacency list
struct AdjList {
    struct Node* head;
};

// Array of adjacency lists
struct AdjList adjacencyList[MAX_VERTICES];

// Function to add an edge to the adjacency list
void addEdgeList(int start, int end) {
    // Create a new node for the end vertex
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = end;
    newNode->next = adjacencyList[start].head;

    // Update the head of the list
    adjacencyList[start].head = newNode;

    // For undirected graphs, add the reverse edge
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = start;
    newNode->next = adjacencyList[end].head;
    adjacencyList[end].head = newNode;
}

Example Usage

Let's create a simple undirected graph with three vertices and three edges using the previously defined structures and functions.

int main() {
    // Create vertices
    struct Vertex v1 = {1};
    struct Vertex v2 = {2};
    struct Vertex v3 = {3};

    // Add edges
    addEdge(0, 1);
    addEdge(1, 2);
    addEdge(2, 0);

    // Add edges using adjacency list
    addEdgeList(0, 1);
    addEdgeList(1, 2);
    addEdgeList(2, 0);

    // Perform graph-related operations here

    return 0;
}

Conclusion

Understanding and implementing graph-related operations in C is essential for solving various real-world problems. Whether you're working on network algorithms or social network analysis, a solid grasp of graph theory and C programming can be a valuable asset.