Graphs are fundamental data structures that model relationships between entities, from social networks to road maps to dependency graphs. Implementing graph algorithms in C requires careful consideration of data structures, memory management, and algorithmic efficiency. This comprehensive guide explores graph representation, traversal algorithms, shortest paths, minimum spanning trees, and advanced graph techniques.

Graph Representations

1. Adjacency Matrix

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
typedef struct {
int **matrix;
int num_vertices;
bool directed;
} AdjMatrix;
// Create adjacency matrix
AdjMatrix* create_adj_matrix(int vertices, bool directed) {
AdjMatrix *graph = malloc(sizeof(AdjMatrix));
graph->num_vertices = vertices;
graph->directed = directed;
// Allocate matrix
graph->matrix = malloc(vertices * sizeof(int*));
for (int i = 0; i < vertices; i++) {
graph->matrix[i] = calloc(vertices, sizeof(int));
}
return graph;
}
// Add edge (weighted or unweighted)
void add_edge_matrix(AdjMatrix *graph, int src, int dest, int weight) {
if (src >= graph->num_vertices || dest >= graph->num_vertices) return;
graph->matrix[src][dest] = weight;
if (!graph->directed) {
graph->matrix[dest][src] = weight;
}
}
// Remove edge
void remove_edge_matrix(AdjMatrix *graph, int src, int dest) {
if (src >= graph->num_vertices || dest >= graph->num_vertices) return;
graph->matrix[src][dest] = 0;
if (!graph->directed) {
graph->matrix[dest][src] = 0;
}
}
// Check if edge exists
bool has_edge_matrix(AdjMatrix *graph, int src, int dest) {
return graph->matrix[src][dest] != 0;
}
// Get neighbors
int* get_neighbors_matrix(AdjMatrix *graph, int vertex, int *count) {
*count = 0;
int *neighbors = malloc(graph->num_vertices * sizeof(int));
for (int i = 0; i < graph->num_vertices; i++) {
if (graph->matrix[vertex][i] != 0) {
neighbors[(*count)++] = i;
}
}
return neighbors;
}
// Free graph
void free_adj_matrix(AdjMatrix *graph) {
for (int i = 0; i < graph->num_vertices; i++) {
free(graph->matrix[i]);
}
free(graph->matrix);
free(graph);
}

2. Adjacency List

typedef struct EdgeNode {
int dest;
int weight;
struct EdgeNode *next;
} EdgeNode;
typedef struct {
EdgeNode **adj_lists;
int num_vertices;
bool directed;
} AdjList;
// Create adjacency list
AdjList* create_adj_list(int vertices, bool directed) {
AdjList *graph = malloc(sizeof(AdjList));
graph->num_vertices = vertices;
graph->directed = directed;
graph->adj_lists = malloc(vertices * sizeof(EdgeNode*));
for (int i = 0; i < vertices; i++) {
graph->adj_lists[i] = NULL;
}
return graph;
}
// Add edge
void add_edge_list(AdjList *graph, int src, int dest, int weight) {
// Add to src's list
EdgeNode *new_node = malloc(sizeof(EdgeNode));
new_node->dest = dest;
new_node->weight = weight;
new_node->next = graph->adj_lists[src];
graph->adj_lists[src] = new_node;
// If undirected, add reverse edge
if (!graph->directed) {
EdgeNode *reverse_node = malloc(sizeof(EdgeNode));
reverse_node->dest = src;
reverse_node->weight = weight;
reverse_node->next = graph->adj_lists[dest];
graph->adj_lists[dest] = reverse_node;
}
}
// Remove edge
void remove_edge_list(AdjList *graph, int src, int dest) {
EdgeNode *curr = graph->adj_lists[src];
EdgeNode *prev = NULL;
while (curr != NULL && curr->dest != dest) {
prev = curr;
curr = curr->next;
}
if (curr != NULL) {
if (prev == NULL) {
graph->adj_lists[src] = curr->next;
} else {
prev->next = curr->next;
}
free(curr);
}
// For undirected, remove reverse edge
if (!graph->directed) {
curr = graph->adj_lists[dest];
prev = NULL;
while (curr != NULL && curr->dest != src) {
prev = curr;
curr = curr->next;
}
if (curr != NULL) {
if (prev == NULL) {
graph->adj_lists[dest] = curr->next;
} else {
prev->next = curr->next;
}
free(curr);
}
}
}
// Get neighbors
EdgeNode* get_neighbors_list(AdjList *graph, int vertex) {
return graph->adj_lists[vertex];
}
// Free graph
void free_adj_list(AdjList *graph) {
for (int i = 0; i < graph->num_vertices; i++) {
EdgeNode *curr = graph->adj_lists[i];
while (curr != NULL) {
EdgeNode *temp = curr;
curr = curr->next;
free(temp);
}
}
free(graph->adj_lists);
free(graph);
}

Graph Traversal Algorithms

1. Breadth-First Search (BFS)

#include <stdbool.h>
typedef struct QueueNode {
int data;
struct QueueNode *next;
} QueueNode;
typedef struct {
QueueNode *front;
QueueNode *rear;
} Queue;
Queue* create_queue() {
Queue *q = malloc(sizeof(Queue));
q->front = q->rear = NULL;
return q;
}
void enqueue(Queue *q, int value) {
QueueNode *node = malloc(sizeof(QueueNode));
node->data = value;
node->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = node;
} else {
q->rear->next = node;
q->rear = node;
}
}
int dequeue(Queue *q) {
if (q->front == NULL) return -1;
QueueNode *temp = q->front;
int data = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
return data;
}
bool is_queue_empty(Queue *q) {
return q->front == NULL;
}
void free_queue(Queue *q) {
while (!is_queue_empty(q)) {
dequeue(q);
}
free(q);
}
// BFS traversal (adjacency list)
void bfs(AdjList *graph, int start) {
bool *visited = calloc(graph->num_vertices, sizeof(bool));
Queue *q = create_queue();
visited[start] = true;
enqueue(q, start);
printf("BFS traversal: ");
while (!is_queue_empty(q)) {
int current = dequeue(q);
printf("%d ", current);
EdgeNode *neighbor = graph->adj_lists[current];
while (neighbor != NULL) {
if (!visited[neighbor->dest]) {
visited[neighbor->dest] = true;
enqueue(q, neighbor->dest);
}
neighbor = neighbor->next;
}
}
printf("\n");
free(visited);
free_queue(q);
}
// BFS for disconnected graphs
void bfs_disconnected(AdjList *graph) {
bool *visited = calloc(graph->num_vertices, sizeof(bool));
printf("BFS (all components): ");
for (int i = 0; i < graph->num_vertices; i++) {
if (!visited[i]) {
// BFS from i
Queue *q = create_queue();
visited[i] = true;
enqueue(q, i);
while (!is_queue_empty(q)) {
int current = dequeue(q);
printf("%d ", current);
EdgeNode *neighbor = graph->adj_lists[current];
while (neighbor != NULL) {
if (!visited[neighbor->dest]) {
visited[neighbor->dest] = true;
enqueue(q, neighbor->dest);
}
neighbor = neighbor->next;
}
}
free_queue(q);
}
}
printf("\n");
free(visited);
}
// Find shortest path in unweighted graph (BFS)
int* shortest_path_unweighted(AdjList *graph, int start, int dest, int *path_len) {
int n = graph->num_vertices;
int *dist = malloc(n * sizeof(int));
int *prev = malloc(n * sizeof(int));
bool *visited = calloc(n, sizeof(bool));
for (int i = 0; i < n; i++) {
dist[i] = -1;
prev[i] = -1;
}
Queue *q = create_queue();
visited[start] = true;
dist[start] = 0;
enqueue(q, start);
while (!is_queue_empty(q)) {
int current = dequeue(q);
if (current == dest) break;
EdgeNode *neighbor = graph->adj_lists[current];
while (neighbor != NULL) {
if (!visited[neighbor->dest]) {
visited[neighbor->dest] = true;
dist[neighbor->dest] = dist[current] + 1;
prev[neighbor->dest] = current;
enqueue(q, neighbor->dest);
}
neighbor = neighbor->next;
}
}
// Reconstruct path
if (dist[dest] == -1) {
*path_len = 0;
free(dist);
free(prev);
free(visited);
free_queue(q);
return NULL;
}
*path_len = dist[dest] + 1;
int *path = malloc((*path_len) * sizeof(int));
int current = dest;
for (int i = *path_len - 1; i >= 0; i--) {
path[i] = current;
current = prev[current];
}
free(dist);
free(prev);
free(visited);
free_queue(q);
return path;
}

2. Depth-First Search (DFS)

// Recursive DFS
void dfs_recursive_util(AdjList *graph, int vertex, bool *visited) {
visited[vertex] = true;
printf("%d ", vertex);
EdgeNode *neighbor = graph->adj_lists[vertex];
while (neighbor != NULL) {
if (!visited[neighbor->dest]) {
dfs_recursive_util(graph, neighbor->dest, visited);
}
neighbor = neighbor->next;
}
}
void dfs_recursive(AdjList *graph, int start) {
bool *visited = calloc(graph->num_vertices, sizeof(bool));
printf("DFS (recursive): ");
dfs_recursive_util(graph, start, visited);
printf("\n");
free(visited);
}
// Iterative DFS using stack
typedef struct StackNode {
int data;
struct StackNode *next;
} StackNode;
StackNode* push(StackNode *top, int value) {
StackNode *node = malloc(sizeof(StackNode));
node->data = value;
node->next = top;
return node;
}
int pop(StackNode **top) {
if (*top == NULL) return -1;
StackNode *temp = *top;
int data = temp->data;
*top = (*top)->next;
free(temp);
return data;
}
bool is_stack_empty(StackNode *top) {
return top == NULL;
}
void dfs_iterative(AdjList *graph, int start) {
bool *visited = calloc(graph->num_vertices, sizeof(bool));
StackNode *stack = NULL;
stack = push(stack, start);
printf("DFS (iterative): ");
while (!is_stack_empty(stack)) {
int current = pop(&stack);
if (!visited[current]) {
visited[current] = true;
printf("%d ", current);
// Push neighbors in reverse order for consistent order
EdgeNode *neighbor = graph->adj_lists[current];
StackNode *temp_stack = NULL;
while (neighbor != NULL) {
if (!visited[neighbor->dest]) {
temp_stack = push(temp_stack, neighbor->dest);
}
neighbor = neighbor->next;
}
// Push to main stack
while (!is_stack_empty(temp_stack)) {
int v = pop(&temp_stack);
stack = push(stack, v);
}
}
}
printf("\n");
free(visited);
}
// DFS for topological sort
void topological_sort_util(AdjList *graph, int vertex, bool *visited, 
StackNode **stack) {
visited[vertex] = true;
EdgeNode *neighbor = graph->adj_lists[vertex];
while (neighbor != NULL) {
if (!visited[neighbor->dest]) {
topological_sort_util(graph, neighbor->dest, visited, stack);
}
neighbor = neighbor->next;
}
*stack = push(*stack, vertex);
}
void topological_sort(AdjList *graph) {
bool *visited = calloc(graph->num_vertices, sizeof(bool));
StackNode *stack = NULL;
for (int i = 0; i < graph->num_vertices; i++) {
if (!visited[i]) {
topological_sort_util(graph, i, visited, &stack);
}
}
printf("Topological order: ");
while (!is_stack_empty(stack)) {
printf("%d ", pop(&stack));
}
printf("\n");
free(visited);
}

Shortest Path Algorithms

1. Dijkstra's Algorithm (Single Source Shortest Path)

#include <limits.h>
typedef struct MinHeapNode {
int vertex;
int distance;
} MinHeapNode;
typedef struct MinHeap {
int size;
int capacity;
int *pos;  // Position mapping for decrease-key
MinHeapNode **array;
} MinHeap;
MinHeap* create_min_heap(int capacity) {
MinHeap *heap = malloc(sizeof(MinHeap));
heap->pos = malloc(capacity * sizeof(int));
heap->size = 0;
heap->capacity = capacity;
heap->array = malloc(capacity * sizeof(MinHeapNode*));
return heap;
}
void swap_min_heap_node(MinHeapNode **a, MinHeapNode **b) {
MinHeapNode *temp = *a;
*a = *b;
*b = temp;
}
void min_heapify(MinHeap *heap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < heap->size && 
heap->array[left]->distance < heap->array[smallest]->distance) {
smallest = left;
}
if (right < heap->size && 
heap->array[right]->distance < heap->array[smallest]->distance) {
smallest = right;
}
if (smallest != idx) {
MinHeapNode *smallestNode = heap->array[smallest];
MinHeapNode *idxNode = heap->array[idx];
heap->pos[smallestNode->vertex] = idx;
heap->pos[idxNode->vertex] = smallest;
swap_min_heap_node(&heap->array[smallest], &heap->array[idx]);
min_heapify(heap, smallest);
}
}
bool is_heap_empty(MinHeap *heap) {
return heap->size == 0;
}
MinHeapNode* extract_min(MinHeap *heap) {
if (is_heap_empty(heap)) return NULL;
MinHeapNode *root = heap->array[0];
MinHeapNode *lastNode = heap->array[heap->size - 1];
heap->array[0] = lastNode;
heap->pos[root->vertex] = heap->size - 1;
heap->pos[lastNode->vertex] = 0;
heap->size--;
min_heapify(heap, 0);
return root;
}
void decrease_key(MinHeap *heap, int vertex, int distance) {
int i = heap->pos[vertex];
heap->array[i]->distance = distance;
while (i && heap->array[i]->distance < heap->array[(i - 1) / 2]->distance) {
heap->pos[heap->array[i]->vertex] = (i - 1) / 2;
heap->pos[heap->array[(i - 1) / 2]->vertex] = i;
swap_min_heap_node(&heap->array[i], &heap->array[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
bool is_in_heap(MinHeap *heap, int vertex) {
return heap->pos[vertex] < heap->size;
}
void dijkstra(AdjList *graph, int source) {
int n = graph->num_vertices;
int *dist = malloc(n * sizeof(int));
int *prev = malloc(n * sizeof(int));
MinHeap *heap = create_min_heap(n);
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
prev[i] = -1;
heap->array[i] = malloc(sizeof(MinHeapNode));
heap->array[i]->vertex = i;
heap->array[i]->distance = INT_MAX;
heap->pos[i] = i;
}
dist[source] = 0;
decrease_key(heap, source, 0);
heap->size = n;
while (!is_heap_empty(heap)) {
MinHeapNode *minNode = extract_min(heap);
int u = minNode->vertex;
EdgeNode *neighbor = graph->adj_lists[u];
while (neighbor != NULL) {
int v = neighbor->dest;
int weight = neighbor->weight;
if (is_in_heap(heap, v) && dist[u] != INT_MAX &&
dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
prev[v] = u;
decrease_key(heap, v, dist[v]);
}
neighbor = neighbor->next;
}
free(minNode);
}
// Print distances
printf("Dijkstra's Algorithm (from %d):\n", source);
for (int i = 0; i < n; i++) {
if (dist[i] == INT_MAX) {
printf("  %d -> %d: INF\n", source, i);
} else {
printf("  %d -> %d: %d\n", source, i, dist[i]);
}
}
free(dist);
free(prev);
free(heap->pos);
free(heap->array);
free(heap);
}

2. Bellman-Ford Algorithm (Handles Negative Weights)

typedef struct {
int src;
int dest;
int weight;
} Edge;
void bellman_ford(AdjList *graph, int source) {
int n = graph->num_vertices;
// Collect all edges
Edge *edges = malloc(n * n * sizeof(Edge));
int edge_count = 0;
for (int i = 0; i < n; i++) {
EdgeNode *neighbor = graph->adj_lists[i];
while (neighbor != NULL) {
edges[edge_count].src = i;
edges[edge_count].dest = neighbor->dest;
edges[edge_count].weight = neighbor->weight;
edge_count++;
neighbor = neighbor->next;
}
}
int *dist = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
}
dist[source] = 0;
// Relax edges n-1 times
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < edge_count; j++) {
int u = edges[j].src;
int v = edges[j].dest;
int w = edges[j].weight;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// Check for negative cycles
bool has_negative_cycle = false;
for (int j = 0; j < edge_count; j++) {
int u = edges[j].src;
int v = edges[j].dest;
int w = edges[j].weight;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
has_negative_cycle = true;
break;
}
}
printf("Bellman-Ford (from %d):\n", source);
if (has_negative_cycle) {
printf("  Graph contains negative cycle!\n");
} else {
for (int i = 0; i < n; i++) {
if (dist[i] == INT_MAX) {
printf("  %d -> %d: INF\n", source, i);
} else {
printf("  %d -> %d: %d\n", source, i, dist[i]);
}
}
}
free(dist);
free(edges);
}

3. Floyd-Warshall (All Pairs Shortest Path)

void floyd_warshall(AdjMatrix *graph) {
int n = graph->num_vertices;
// Initialize distance matrix
int **dist = malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
dist[i] = malloc(n * sizeof(int));
for (int j = 0; j < n; j++) {
if (i == j) {
dist[i][j] = 0;
} else if (graph->matrix[i][j] != 0) {
dist[i][j] = graph->matrix[i][j];
} else {
dist[i][j] = INT_MAX / 2;  // Avoid overflow
}
}
}
// Floyd-Warshall algorithm
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// Print results
printf("All-pairs shortest paths:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] >= INT_MAX / 2) {
printf(" INF");
} else {
printf(" %3d", dist[i][j]);
}
}
printf("\n");
}
// Free memory
for (int i = 0; i < n; i++) {
free(dist[i]);
}
free(dist);
}

Minimum Spanning Tree Algorithms

1. Prim's Algorithm

int* prim_mst(AdjList *graph, int start) {
int n = graph->num_vertices;
bool *in_mst = calloc(n, sizeof(bool));
int *key = malloc(n * sizeof(int));
int *parent = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
key[i] = INT_MAX;
parent[i] = -1;
}
key[start] = 0;
for (int count = 0; count < n - 1; count++) {
// Find vertex with minimum key not in MST
int u = -1;
int min_key = INT_MAX;
for (int i = 0; i < n; i++) {
if (!in_mst[i] && key[i] < min_key) {
min_key = key[i];
u = i;
}
}
if (u == -1) break;
in_mst[u] = true;
// Update keys of adjacent vertices
EdgeNode *neighbor = graph->adj_lists[u];
while (neighbor != NULL) {
int v = neighbor->dest;
int weight = neighbor->weight;
if (!in_mst[v] && weight < key[v]) {
key[v] = weight;
parent[v] = u;
}
neighbor = neighbor->next;
}
}
// Print MST
printf("Prim's MST (starting from %d):\n", start);
int total_weight = 0;
for (int i = 0; i < n; i++) {
if (parent[i] != -1) {
printf("  %d - %d (weight: %d)\n", parent[i], i, key[i]);
total_weight += key[i];
}
}
printf("Total weight: %d\n", total_weight);
free(in_mst);
free(key);
return parent;
}

2. Kruskal's Algorithm

typedef struct {
int parent;
int rank;
} Subset;
int find(Subset subsets[], int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
void union_sets(Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
int compare_edges(const void *a, const void *b) {
Edge *e1 = (Edge*)a;
Edge *e2 = (Edge*)b;
return e1->weight - e2->weight;
}
void kruskal_mst(AdjList *graph) {
int n = graph->num_vertices;
// Collect all edges
Edge *edges = malloc(n * n * sizeof(Edge));
int edge_count = 0;
for (int i = 0; i < n; i++) {
EdgeNode *neighbor = graph->adj_lists[i];
while (neighbor != NULL) {
// Add each edge only once for undirected graph
if (i < neighbor->dest) {
edges[edge_count].src = i;
edges[edge_count].dest = neighbor->dest;
edges[edge_count].weight = neighbor->weight;
edge_count++;
}
neighbor = neighbor->next;
}
}
// Sort edges by weight
qsort(edges, edge_count, sizeof(Edge), compare_edges);
// Initialize subsets
Subset *subsets = malloc(n * sizeof(Subset));
for (int i = 0; i < n; i++) {
subsets[i].parent = i;
subsets[i].rank = 0;
}
Edge *result = malloc((n - 1) * sizeof(Edge));
int result_count = 0;
int total_weight = 0;
for (int i = 0; i < edge_count && result_count < n - 1; i++) {
int x = find(subsets, edges[i].src);
int y = find(subsets, edges[i].dest);
if (x != y) {
result[result_count++] = edges[i];
total_weight += edges[i].weight;
union_sets(subsets, x, y);
}
}
// Print MST
printf("Kruskal's MST:\n");
for (int i = 0; i < result_count; i++) {
printf("  %d - %d (weight: %d)\n", 
result[i].src, result[i].dest, result[i].weight);
}
printf("Total weight: %d\n", total_weight);
free(edges);
free(subsets);
free(result);
}

Cycle Detection

1. Cycle Detection in Directed Graph (DFS)

bool is_cyclic_directed_util(AdjList *graph, int vertex, 
bool *visited, bool *rec_stack) {
visited[vertex] = true;
rec_stack[vertex] = true;
EdgeNode *neighbor = graph->adj_lists[vertex];
while (neighbor != NULL) {
if (!visited[neighbor->dest]) {
if (is_cyclic_directed_util(graph, neighbor->dest, visited, rec_stack)) {
return true;
}
} else if (rec_stack[neighbor->dest]) {
return true;  // Back edge found
}
neighbor = neighbor->next;
}
rec_stack[vertex] = false;
return false;
}
bool is_cyclic_directed(AdjList *graph) {
bool *visited = calloc(graph->num_vertices, sizeof(bool));
bool *rec_stack = calloc(graph->num_vertices, sizeof(bool));
for (int i = 0; i < graph->num_vertices; i++) {
if (!visited[i]) {
if (is_cyclic_directed_util(graph, i, visited, rec_stack)) {
free(visited);
free(rec_stack);
return true;
}
}
}
free(visited);
free(rec_stack);
return false;
}

2. Cycle Detection in Undirected Graph (Union-Find)

bool is_cyclic_undirected(AdjList *graph) {
int n = graph->num_vertices;
Subset *subsets = malloc(n * sizeof(Subset));
for (int i = 0; i < n; i++) {
subsets[i].parent = i;
subsets[i].rank = 0;
}
// Check each edge
for (int u = 0; u < n; u++) {
EdgeNode *neighbor = graph->adj_lists[u];
while (neighbor != NULL) {
int v = neighbor->dest;
// Process each edge only once
if (u < v) {
int x = find(subsets, u);
int y = find(subsets, v);
if (x == y) {
free(subsets);
return true;  // Cycle found
}
union_sets(subsets, x, y);
}
neighbor = neighbor->next;
}
}
free(subsets);
return false;
}

Strongly Connected Components (Kosaraju's Algorithm)

void dfs_fill_order(AdjList *graph, int vertex, bool *visited, StackNode **stack) {
visited[vertex] = true;
EdgeNode *neighbor = graph->adj_lists[vertex];
while (neighbor != NULL) {
if (!visited[neighbor->dest]) {
dfs_fill_order(graph, neighbor->dest, visited, stack);
}
neighbor = neighbor->next;
}
*stack = push(*stack, vertex);
}
AdjList* get_transpose(AdjList *graph) {
AdjList *transpose = create_adj_list(graph->num_vertices, graph->directed);
for (int i = 0; i < graph->num_vertices; i++) {
EdgeNode *neighbor = graph->adj_lists[i];
while (neighbor != NULL) {
add_edge_list(transpose, neighbor->dest, i, neighbor->weight);
neighbor = neighbor->next;
}
}
return transpose;
}
void dfs_scc(AdjList *graph, int vertex, bool *visited, int *scc_id, int id) {
visited[vertex] = true;
scc_id[vertex] = id;
printf("%d ", vertex);
EdgeNode *neighbor = graph->adj_lists[vertex];
while (neighbor != NULL) {
if (!visited[neighbor->dest]) {
dfs_scc(graph, neighbor->dest, visited, scc_id, id);
}
neighbor = neighbor->next;
}
}
void kosaraju_scc(AdjList *graph) {
int n = graph->num_vertices;
StackNode *stack = NULL;
bool *visited = calloc(n, sizeof(bool));
// First pass: fill order
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs_fill_order(graph, i, visited, &stack);
}
}
// Get transpose graph
AdjList *transpose = get_transpose(graph);
// Reset visited
for (int i = 0; i < n; i++) {
visited[i] = false;
}
int *scc_id = malloc(n * sizeof(int));
int scc_count = 0;
printf("Strongly Connected Components:\n");
while (!is_stack_empty(stack)) {
int vertex = pop(&stack);
if (!visited[vertex]) {
printf("  SCC %d: ", scc_count + 1);
dfs_scc(transpose, vertex, visited, scc_id, scc_count);
printf("\n");
scc_count++;
}
}
printf("Total SCCs: %d\n", scc_count);
free(visited);
free(scc_id);
free_adj_list(transpose);
}

Complete Example Program

int main() {
printf("=== Graph Algorithms Demo ===\n\n");
// Create a weighted undirected graph
int vertices = 9;
AdjList *graph = create_adj_list(vertices, false);
// Add edges (example graph)
add_edge_list(graph, 0, 1, 4);
add_edge_list(graph, 0, 7, 8);
add_edge_list(graph, 1, 2, 8);
add_edge_list(graph, 1, 7, 11);
add_edge_list(graph, 2, 3, 7);
add_edge_list(graph, 2, 5, 4);
add_edge_list(graph, 2, 8, 2);
add_edge_list(graph, 3, 4, 9);
add_edge_list(graph, 3, 5, 14);
add_edge_list(graph, 4, 5, 10);
add_edge_list(graph, 5, 6, 2);
add_edge_list(graph, 6, 7, 1);
add_edge_list(graph, 6, 8, 6);
add_edge_list(graph, 7, 8, 7);
// Traversals
printf("1. Graph Traversals:\n");
bfs(graph, 0);
dfs_recursive(graph, 0);
dfs_iterative(graph, 0);
// Shortest paths
printf("\n2. Shortest Path Algorithms:\n");
dijkstra(graph, 0);
printf("\n");
bellman_ford(graph, 0);
// Minimum Spanning Trees
printf("\n3. Minimum Spanning Trees:\n");
prim_mst(graph, 0);
printf("\n");
kruskal_mst(graph);
// Check for cycles
printf("\n4. Cycle Detection:\n");
if (is_cyclic_undirected(graph)) {
printf("  Graph contains a cycle\n");
} else {
printf("  Graph is acyclic\n");
}
// Clean up
free_adj_list(graph);
// Directed graph example for SCC
printf("\n5. Strongly Connected Components (Directed Graph):\n");
AdjList *digraph = create_adj_list(5, true);
add_edge_list(digraph, 0, 1, 1);
add_edge_list(digraph, 1, 2, 1);
add_edge_list(digraph, 2, 0, 1);
add_edge_list(digraph, 1, 3, 1);
add_edge_list(digraph, 3, 4, 1);
kosaraju_scc(digraph);
free_adj_list(digraph);
return 0;
}

Complexity Analysis

Best Practices

1. Choose the right representation: Adjacency matrix for dense graphs (|E| ≈ |V|²), adjacency list for sparse graphs (|E| ≪ |V|²)
2. Use appropriate algorithms: Consider graph characteristics (directed/undirected, weighted/unweighted, dense/sparse)
3. Handle edge cases: Empty graphs, disconnected graphs, self-loops
4. Optimize with priority queues: For Dijkstra and Prim
5. Check for overflow: Use appropriate data types for distances
6. Free memory: Graph algorithms can allocate significant memory
7. Validate input: Check vertex indices before access
8. Consider parallelization: For large graphs, consider parallel algorithms

Conclusion

Graph algorithms form the backbone of many computational problems. From social network analysis to routing in networks, understanding and implementing these algorithms efficiently is crucial for systems programming in C. By mastering the representations, traversals, and advanced algorithms covered in this guide, you can tackle complex graph problems with confidence.