Graphs are versatile data structures used to represent relationships between entities. A graph consists of:
- Vertices (nodes): Represent entities.
- Edges (links): Represent connections between entities.
Graphs can be directed (edges have a direction) or undirected (edges have no direction). They can also be weighted or unweighted.
In C, graphs are typically represented using two main methods:
- Adjacency Matrix
- Adjacency List
1. Adjacency Matrix Representation
An adjacency matrix is a 2D array where:
- Rows and columns represent vertices.
- A cell matrix[i][j]matrix[i][j]matrix[i][j]:
- 111 (or weight) if there is an edge between vertices iii and jjj.
- 000 otherwise.
Characteristics
- Space Complexity: O(V2)O(V^2)O(V2), where VVV is the number of vertices.
- Best for dense graphs.
C Code Example:
#include <stdio.h>
#define V 4 // Number of vertices
void printMatrix(int graph[V][V]) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
printf(“%d “, graph[i][j]);
}
printf(“\n”);
}
}
int main() {
// Graph represented as an adjacency matrix
int graph[V][V] = {
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
printf(“Adjacency Matrix:\n”);
printMatrix(graph);
return 0;
}
2. Adjacency List Representation
An adjacency list represents a graph as an array of linked lists:
- Each vertex has a list of all adjacent vertices.
- Space Complexity: O(V+E)O(V + E)O(V+E), where EEE is the number of edges.
- Best for sparse graphs.
Characteristics
- More space-efficient than adjacency matrices for sparse graphs.
- Traversal requires more overhead due to linked list traversal.
C Code Example:
#include <stdio.h>
#include <stdlib.h>
// Structure for an adjacency list node
typedef struct Node {
int vertex;
struct Node* next;
} Node;
// Structure for an adjacency list
typedef struct Graph {
int numVertices;
Node** adjLists;
} Graph;
// Create a node
Node* createNode(int vertex) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = vertex;
newNode->next = NULL;
return newNode;
}
// Create a graph
Graph* createGraph(int vertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
}
return graph;
}
// Add an edge
void addEdge(Graph* graph, int src, int dest) {
// Add edge from src to dest
Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Add edge from dest to src (for undirected graph)
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// Print the graph
void printGraph(Graph* graph) {
for (int v = 0; v < graph->numVertices; v++) {
Node* temp = graph->adjLists[v];
printf(“Vertex %d: “, v);
while (temp) {
printf(“%d -> “, temp->vertex);
temp = temp->next;
}
printf(“NULL\n”);
}
}
int main() {
int vertices = 4;
Graph* graph = createGraph(vertices);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
printf(“Adjacency List:\n”);
printGraph(graph);
return 0;
}
3. Edge List Representation
An edge list represents the graph as a list of all edges. Each edge specifies the two vertices it connects and, optionally, its weight.
Characteristics
- Space Complexity: O(E)O(E)O(E).
- Best for edge-centric operations like Kruskal’s algorithm.
C Code Example:
#include <stdio.h>
// Structure for an edge
typedef struct Edge {
int src, dest, weight;
} Edge;
int main() {
int numVertices = 4, numEdges = 5;
// Edge list
Edge edges[] = {
{0, 1, 2},
{0, 2, 4},
{1, 2, 1},
{1, 3, 7},
{2, 3, 3}
};
printf(“Edge List Representation:\n”);
for (int i = 0; i < numEdges; i++) {
printf(“Edge: (%d -> %d), Weight: %d\n”, edges[i].src, edges[i].dest, edges[i].weight);
}
return 0;
}
Comparison of Graph Representations
| Representation | Space Complexity | Best For | Limitations |
| Adjacency Matrix | O(V2)O(V^2)O(V2) | Dense Graphs | Wastes space for sparse graphs. |
| Adjacency List | O(V+E)O(V + E)O(V+E) | Sparse Graphs | Traversal can be slower. |
| Edge List | O(E)O(E)O(E) | Edge-centric Tasks | Inefficient for adjacency checks. |
Applications of Graphs
- Adjacency Matrix:
- Dense graphs.
- Algorithms like Floyd-Warshall (all-pairs shortest path).
- Adjacency List:
- Sparse graphs.
- Algorithms like Depth-First Search (DFS), Breadth-First Search (BFS), and Dijkstra’s.
- Edge List:
- Edge-centric algorithms like Kruskal’s for Minimum Spanning Tree.
Efficient representation of graphs is key to optimizing algorithms for tasks like shortest path, connectivity, and traversal. Each representation has its own advantages and is chosen based on the problem requirements.