C Notes
HubApplications of C Programming LanguageFeatures of C Programming LanguageHistory of C Programming LanguageWhat is C Language?Why Learn C Programming in 2024?First C Program - Hello World in C with ExplanationGCC Compiler - Complete Guide to GNU C CompilerInstall C Compiler on Linux - GCC Setup Guide for All DistrosInstall C Compiler on macOS - Xcode Command Line Tools and Homebrew GCCInstall C Compiler on Windows - MinGW, MSYS2, and WSL GuideSetup VS Code for C Programming - Complete Configuration GuideC Syntax Rules — Complete GuideComments in C ProgrammingConstants in C ProgrammingData Types in CIdentifiers in C ProgrammingKeywords in C ProgrammingStructure of a C ProgramVariables in C ProgrammingArithmetic Operators in C ProgrammingAssignment Operators in C ProgrammingBitwise Operators in C ProgrammingIncrement and Decrement Operators in CLogical Operators in C ProgrammingRelational Operators in C ProgrammingTernary Operator in C ProgrammingBreak Statement in C ProgrammingContinue Statement in C ProgrammingDo-While Loop in C ProgrammingFor Loop in C ProgrammingGoto Statement in C Programmingif-else Statement in C Programmingif Statement in C ProgrammingNested if Statements in C ProgrammingSwitch Statement in C ProgrammingWhile Loop in C ProgrammingFunction Arguments in C - Pass by Value vs Pass by ReferenceFunction Call in C ProgrammingFunction Declaration (Prototype) in CFunction Definition in C ProgrammingIntroduction to Functions in C ProgrammingRecursion in C ProgrammingReturn Statement in C ProgrammingStorage Classes in C ProgrammingArray Operations in C - Searching, Sorting, Insert and DeleteArray Programs in C - Reverse, Rotate, Duplicates, MergeIntroduction to Arrays in C ProgrammingMultidimensional Arrays in C ProgrammingOne Dimensional Arrays in C ProgrammingPassing Arrays to Functions in CTwo Dimensional Arrays in C ProgrammingString Comparison in C - strcmp, strncmp, Case-InsensitiveString Functions in C - strlen, strcpy, strcat, strcmpC String Handling Library - Complete string.h ReferenceString Manipulation in C - Reverse, Uppercase, PalindromeString Programs in C - Anagram, Word Count, Vowels, FrequencyStrings in C Programming - Complete IntroductionDouble Pointers in C - Pointer to PointerPointer Arithmetic in C ProgrammingPointer Declaration and Initialization in CPointer Programs in C - Swap, String Reversal, Dynamic AllocationPointers and Arrays in C - The Relationship ExplainedPointers and Functions in C - Pass by ReferenceIntroduction to Pointers in C ProgrammingVoid Pointers in C - Generic Pointers Guidecalloc() in C – Contiguous Memory AllocationDynamic Arrays in C – Runtime-Sized Arraysfree() in C – Releasing Dynamic Memorymalloc() in C – Dynamic Memory AllocationMemory Management Best Practices in Crealloc() in C – Resizing Dynamic MemoryBinary Files in C – fread and fwriteFile Handling in C – IntroductionFile Handling Projects in C – Student Records & Phone BookFile Modes in C – Complete Guidefopen() and fclose() in C – Opening and Closing FilesReading Files in C – fgetc, fgets, fscanf, freadWriting Files in C – fputc, fputs, fprintf, fwriteConditional Compilation in C – #ifdef, #ifndef, #if#define Macros in C – Constants and Macro FunctionsHeader Files in C – Creating Custom Headers#include Directive in C – File InclusionMacro Functions in C – Parameterized MacrosC Preprocessor – Overview and DirectivesGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSHash Tables in C – Implementation, Collision Handling, and ChainingLinked List in C – Singly, Doubly, and Circular with ImplementationQueue in C – Linear, Circular, and Priority Queue ImplementationStack in C – Array and Linked List Implementation with ApplicationsTrees in C – Binary Search Tree Implementation with TraversalsC Programming Best Practices – Coding Standards, Safety, and PerformanceBit Fields in C – Definition, Use Cases, and Protocol HeadersC Standard Library Overview – All Headers and Common FunctionsCommand Line Arguments in C – argc and argv ExplainedDebugging Techniques in C – GDB, Valgrind, and SanitizersFunction Pointers in C – Complete Guide with ExamplesMemory Layout of a C Program – Text, Data, BSS, Heap, StackBank Management System in C – Complete Project with File StorageFile Encryption Tool in C – XOR Cipher ImplementationLibrary Management System in C – Complete Project with Source CodeMini Compiler in C – Lexer and Parser for Simple ExpressionsSnake Game in C – Console-Based Game with Source CodeStudent Management System in C – Complete Project with Source CodeC Programming Cheatsheet – Complete Quick Reference GuideTop 50 C Programming Interview Questions with Answers (2025)Memory Management Interview Questions in C with AnswersOutput Prediction Questions in C – What Will This Program Print?Pointer Interview Questions in C – Tricky Problems with AnswersCommon C Programming Errors and Solutions – Debugging GuideImportant C Programs – 50+ Frequently Asked Programs with SolutionsQuick Revision Notes for C Programming – Complete C in 10 MinutesRecommended C Programming Books – From Beginner to ExpertFormat Specifiers in C - Complete Referencegetchar() and putchar() in C Programminggets() and puts() in C ProgrammingC Input Output Programs and Examplesprintf() Function in C Programmingscanf() Function in C ProgrammingArrays of Structures in C – Managing CollectionsEnums in C – Enumerated Data TypesNested Structures in C – Struct Within StructPointers to Structures in C – Arrow OperatorStructures in C – User-Defined Data Typestypedef in C – Creating Type AliasesUnions in C – Shared Memory Data Types
Learn graph data structure in C with adjacency matrix and adjacency list representations, BFS and DFS traversal algorithms, and complete implementation examples.
A graph is a non-linear data structure consisting of vertices (nodes) connected by edges. Graphs model real-world relationships like social networks, maps, computer networks, and dependencies. Unlike trees, graphs can have cycles and any vertex can connect to any other vertex.
Graph Terminology
| Term | Definition |
|---|---|
| Vertex/Node | A point in the graph |
| Edge | Connection between two vertices |
| Directed Graph | Edges have direction (one-way) |
| Undirected Graph | Edges go both ways |
| Weighted Graph | Edges have associated costs/weights |
| Degree | Number of edges connected to a vertex |
| Path | Sequence of vertices connected by edges |
| Cycle | Path that starts and ends at the same vertex |
Graph Representation: Adjacency Matrix
An adjacency matrix uses a 2D array where matrix[i][j] = 1 if there's an edge from vertex i to vertex j.
Example
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 10
typedef struct {
int matrix[MAX_VERTICES][MAX_VERTICES];
int numVertices;
} Graph;
void initGraph(Graph *g, int vertices) {
g->numVertices = vertices;
for (int i = 0; i < vertices; i++)
for (int j = 0; j < vertices; j++)
g->matrix[i][j] = 0;
}
void addEdge(Graph *g, int src, int dest) {
g->matrix[src][dest] = 1;
g->matrix[dest][src] = 1; // Remove for directed graph
}
void removeEdge(Graph *g, int src, int dest) {
g->matrix[src][dest] = 0;
g->matrix[dest][src] = 0;
}
bool hasEdge(Graph *g, int src, int dest) {
return g->matrix[src][dest] == 1;
}
void displayMatrix(Graph *g) {
printf("Adjacency Matrix:\n ");
for (int i = 0; i < g->numVertices; i++)
printf("%d ", i);
printf("\n");
for (int i = 0; i < g->numVertices; i++) {
printf("%d|", i);
for (int j = 0; j < g->numVertices; j++)
printf("%d ", g->matrix[i][j]);
printf("\n");
}
}
int main() {
Graph g;
initGraph(&g, 5);
addEdge(&g, 0, 1);
addEdge(&g, 0, 4);
addEdge(&g, 1, 2);
addEdge(&g, 1, 3);
addEdge(&g, 1, 4);
addEdge(&g, 2, 3);
addEdge(&g, 3, 4);
displayMatrix(&g);
printf("\nEdge 1-3: %s\n", hasEdge(&g, 1, 3) ? "Yes" : "No");
printf("Edge 0-2: %s\n", hasEdge(&g, 0, 2) ? "Yes" : "No");
return 0;
}
Output
Adjacency Matrix: 0 1 2 3 4 0|0 1 0 0 1 1|1 0 1 1 1 2|0 1 0 1 0 3|0 1 1 0 1 4|1 1 0 1 0 Edge 1-3: Yes Edge 0-2: No
Graph Representation: Adjacency List
Uses an array of linked lists. More memory-efficient for sparse graphs.
Example
#include <stdio.h>
#include <stdlib.h>
typedef struct AdjNode {
int vertex;
struct AdjNode *next;
} AdjNode;
typedef struct {
AdjNode **adjLists;
int numVertices;
} Graph;
AdjNode* createAdjNode(int vertex) {
AdjNode *node = (AdjNode*)malloc(sizeof(AdjNode));
node->vertex = vertex;
node->next = NULL;
return node;
}
Graph* createGraph(int vertices) {
Graph *g = (Graph*)malloc(sizeof(Graph));
g->numVertices = vertices;
g->adjLists = (AdjNode**)malloc(vertices * sizeof(AdjNode*));
for (int i = 0; i < vertices; i++)
g->adjLists[i] = NULL;
return g;
}
void addEdge(Graph *g, int src, int dest) {
// Add edge src -> dest
AdjNode *node = createAdjNode(dest);
node->next = g->adjLists[src];
g->adjLists[src] = node;
// Add edge dest -> src (undirected)
node = createAdjNode(src);
node->next = g->adjLists[dest];
g->adjLists[dest] = node;
}
void displayGraph(Graph *g) {
printf("Adjacency List:\n");
for (int i = 0; i < g->numVertices; i++) {
printf("Vertex %d: ", i);
AdjNode *temp = g->adjLists[i];
while (temp) {
printf("-> %d ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
void freeGraph(Graph *g) {
for (int i = 0; i < g->numVertices; i++) {
AdjNode *temp = g->adjLists[i];
while (temp) {
AdjNode *next = temp->next;
free(temp);
temp = next;
}
}
free(g->adjLists);
free(g);
}
int main() {
Graph *g = createGraph(5);
addEdge(g, 0, 1);
addEdge(g, 0, 4);
addEdge(g, 1, 2);
addEdge(g, 1, 3);
addEdge(g, 2, 3);
displayGraph(g);
freeGraph(g);
return 0;
}
Output
Adjacency List: Vertex 0: -> 4 -> 1 Vertex 1: -> 3 -> 2 -> 0 Vertex 2: -> 3 -> 1 Vertex 3: -> 2 -> 1 Vertex 4: -> 0
BFS – Breadth First Search
BFS explores vertices level by level using a queue. It finds the shortest path in unweighted graphs.
Example
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 100
int adjMatrix[MAX][MAX];
bool visited[MAX];
int queue[MAX], front = 0, rear = -1;
void enqueue(int v) { queue[++rear] = v; }
int dequeue() { return queue[front++]; }
bool isEmpty() { return front > rear; }
void BFS(int start, int n) {
for (int i = 0; i < n; i++) visited[i] = false;
front = 0; rear = -1;
visited[start] = true;
enqueue(start);
printf("BFS from vertex %d: ", start);
while (!isEmpty()) {
int current = dequeue();
printf("%d ", current);
for (int i = 0; i < n; i++) {
if (adjMatrix[current][i] == 1 && !visited[i]) {
visited[i] = true;
enqueue(i);
}
}
}
printf("\n");
}
int main() {
int n = 6;
// Initialize
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
adjMatrix[i][j] = 0;
// Add edges
int edges[][2] = {{0,1},{0,2},{1,3},{2,4},{3,4},{3,5},{4,5}};
for (int i = 0; i < 7; i++) {
adjMatrix[edges[i][0]][edges[i][1]] = 1;
adjMatrix[edges[i][1]][edges[i][0]] = 1;
}
BFS(0, n);
BFS(3, n);
return 0;
}
Output
BFS from vertex 0: 0 1 2 3 4 5 BFS from vertex 3: 3 1 4 5 0 2
DFS – Depth First Search
DFS explores as deep as possible before backtracking. It uses recursion (or an explicit stack).
Example
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
int adjMatrix[MAX][MAX];
bool visited[MAX];
int n = 6;
void DFS(int vertex) {
visited[vertex] = true;
printf("%d ", vertex);
for (int i = 0; i < n; i++) {
if (adjMatrix[vertex][i] == 1 && !visited[i]) {
DFS(i);
}
}
}
// Iterative DFS using explicit stack
void DFS_iterative(int start) {
int stack[MAX], top = -1;
bool vis[MAX] = {false};
stack[++top] = start;
printf("DFS iterative from %d: ", start);
while (top >= 0) {
int v = stack[top--];
if (!vis[v]) {
vis[v] = true;
printf("%d ", v);
// Push neighbors in reverse order for correct traversal
for (int i = n - 1; i >= 0; i--) {
if (adjMatrix[v][i] == 1 && !vis[i])
stack[++top] = i;
}
}
}
printf("\n");
}
int main() {
// Initialize
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
adjMatrix[i][j] = 0;
int edges[][2] = {{0,1},{0,2},{1,3},{2,4},{3,4},{3,5},{4,5}};
for (int i = 0; i < 7; i++) {
adjMatrix[edges[i][0]][edges[i][1]] = 1;
adjMatrix[edges[i][1]][edges[i][0]] = 1;
}
// Recursive DFS
for (int i = 0; i < n; i++) visited[i] = false;
printf("DFS recursive from 0: ");
DFS(0);
printf("\n");
// Iterative DFS
DFS_iterative(0);
return 0;
}
Output
DFS recursive from 0: 0 1 3 4 2 5 DFS iterative from 0: 0 1 3 4 2 5
BFS vs DFS Comparison
| Feature | BFS | DFS |
|---|---|---|
| Data structure | Queue | Stack (or recursion) |
| Approach | Level by level | Go deep, then backtrack |
| Shortest path | Yes (unweighted) | Not guaranteed |
| Memory usage | O(V) for queue | O(V) for stack/recursion |
| Best for | Shortest path, level-order | Topological sort, cycle detection |
| Connected components | Yes | Yes |
Interview Questions on Graphs
Q1: How do you detect a cycle in an undirected graph? Using DFS: if you visit a vertex that's already visited and isn't the parent of the current vertex, there's a cycle.
Q2: What's the difference between adjacency matrix and adjacency list? Matrix: O(V²) space, O(1) edge lookup, better for dense graphs. List: O(V+E) space, O(degree) edge lookup, better for sparse graphs.
Q3: How do you find the shortest path in an unweighted graph? Use BFS from the source vertex. The first time BFS reaches a vertex, it's found the shortest path to it.
Q4: Can BFS/DFS work on disconnected graphs? Not directly – they only traverse the connected component of the starting vertex. Loop through all vertices and start BFS/DFS from unvisited ones to cover all components.
Q5: What's topological sorting and when is it used? A linear ordering of vertices in a DAG (Directed Acyclic Graph) where for every edge u→v, u comes before v. Used in task scheduling, build systems, and course prerequisites.
Summary
Graphs are versatile data structures for modeling relationships. Choose adjacency matrix for dense graphs with frequent edge lookups, and adjacency list for sparse graphs. BFS traverses level-by-level and finds shortest paths in unweighted graphs. DFS explores depth-first and is useful for topological sorting, cycle detection, and connected component analysis. Understanding both representations and traversals is fundamental for solving graph problems in interviews and real applications.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Graphs in C – Adjacency Matrix, Adjacency List, BFS, and DFS.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this C Programming topic.
Search Terms
c-programming, c programming, programming, data, structures, graphs, graphs in c – adjacency matrix, adjacency list, bfs, and dfs
Related C Programming Topics
Continue learning this concept
Data Structures In CHash Tables in C – Implementation, Collision Handling, and ChainingLearn hash table implementation in C with hash functions, collision resolution using chaining and open addressing, performance analysis, and practical examples.Data Structures In CLinked List in C – Singly, Doubly, and Circular with ImplementationComplete guide to implementing linked lists in C covering singly linked list, doubly linked list, circular linked list, all operations with code examples and output.Data Structures In CQueue in C – Linear, Circular, and Priority Queue ImplementationLearn queue data structure in C with linear queue, circular queue, and priority queue implementations using arrays and linked lists with complete code examples.Data Structures In CStack in C – Array and Linked List Implementation with ApplicationsLearn stack data structure in C with array-based and linked list implementations, push/pop operations, applications like expression evaluation, and interview questions.Data Structures In CTrees in C – Binary Search Tree Implementation with TraversalsLearn tree data structure in C with BST implementation covering insertion, deletion, searching, inorder/preorder/postorder traversals, and tree operations.BasicsComments in C ProgrammingLearn about comments in C — single-line comments, multi-line comments, best practices, nested comments, and when to use comments effectively in your code.