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

Algorithm	Time Complexity	Space Complexity
BFS	O(V + E)	O(V)
DFS	O(V + E)	O(V)
Dijkstra	O((V + E) log V)	O(V)
Bellman-Ford	O(VE)	O(V)
Floyd-Warshall	O(V³)	O(V²)
Prim	O((V + E) log V)	O(V)
Kruskal	O(E log E)	O(V + E)
Kosaraju	O(V + E)	O(V + E)

Best Practices

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

Complete C Programming Guide + Compilers Collection

1. C srand() Function – Understanding Seed Initialization

https://macronepal.com/understanding-the-c-srand-function
Explains how srand() initializes the pseudo-random number generator in C by setting a seed value. Using the same seed produces the same sequence, while time(NULL) gives different results each run.

2. C rand() Function Mechanics and Limitations

https://macronepal.com/c-rand-function-mechanics-and-limitations
Explains how rand() generates pseudo-random numbers between 0 and RAND_MAX, its deterministic nature, and limitations for security use cases.

3. C log() Function

https://macronepal.com/c-log-function-2
Covers natural logarithm calculation using <math.h> and its applications.

4. Mastering Date and Time in C

https://macronepal.com/mastering-date-and-time-in-c
Explains <time.h> functions like time(), clock(), difftime(), and struct tm.

5. Mastering time_t Type in C

https://macronepal.com/mastering-the-c-time_t-type-for-time-management
Explains time representation as seconds since Unix epoch and conversion functions.

6. C exp() Function

https://macronepal.com/c-exp-function-mechanics-and-implementation
Explains exponential function exp(x) and its scientific applications.

7. C log() Function (Alternate Guide)

https://macronepal.com/c-log-function
Comparison of log() and log10() with usage examples.

8. C log10() Function

https://macronepal.com/mastering-the-log10-function-in-c
Explains base-10 logarithm for engineering and scientific applications.

9. C tan() Function

https://macronepal.com/understanding-the-c-tan-function
Explains tangent function and radian-based calculations.

10. Random Numbers in C (Secure vs Predictable)

https://macronepal.com/mastering-c-random-numbers-for-secure-and-predictable-applications
Explains difference between rand() and secure randomness methods.

11. Free Online C Compiler

https://macronepal.com/free-online-c-code-compiler-2
Browser-based compiler for testing C programs instantly.

C Functions, Arguments, Parameters & Flow

Mastering Functions in C – Complete Guide

https://macronepal.com/c/mastering-functions-in-c-a-complete-guide/
Covers function structure, modular programming, and real-world usage.

Function Arguments in C

https://macronepal.com/c-function-arguments/
Explains how arguments are passed and used in function calls.

Function Parameters in C

https://macronepal.com/c-function-parameters/
Explains defining inputs for functions and matching them with arguments.

Function Declarations in C

https://macronepal.com/c-function-declarations-syntax-rules-and-best-practices/
Covers prototypes, syntax rules, and best practices.

Function Calls in C

https://macronepal.com/understanding-function-calls-in-c-syntax-mechanics-and-best-practices/
Explains execution flow and parameter handling during function calls.

Void Functions in C

https://macronepal.com/understanding-void-functions-in-c-syntax-patterns-and-best-practices/
Explains functions that do not return values.

Return Values in C

https://macronepal.com/c-return-values-mechanics-types-and-best-practices/
Explains different return types and how functions return results.

Pass-by-Value in C

https://macronepal.com/aws/understanding-pass-by-value-in-c-mechanics-implications-and-best-practices/
Explains how copies of variables are passed into functions.

Pass-by-Reference in C

https://macronepal.com/c/understanding-pass-by-reference-in-c-pointers-semantics-and-safe-practices/
Explains using pointers to modify original variables.

C strstr() Function

https://macronepal.com/aws/c-strstr-function/
Explains substring search inside strings in C.

C Preprocessor & Macros

C Structures, Memory, Scope & Linkage

C Scope, Storage Classes & Typedef

Extra Articles

https://macronepal.com/13757-2/
https://macronepal.com/13748-2/
https://macronepal.com/13747-2/
https://macronepal.com/13746-2/
https://macronepal.com/13745-2/
https://macronepal.com/13708-2/
https://macronepal.com/13707-2/
https://macronepal.com/13702-2/

Online Compilers