Graph Traversals
We will focus on Breadth-First Search (BFS) and Depth-First Search (DFS), using the
Adjacency Matrix representation of graphs.
Learning Goals
● Implement DFS and BFS traversal algorithms in C using an adjacency matrix.
● Solve simple problems using graph traversal techniques.
● Understand the difference between BFS and DFS and when to use them.
Part 1: Introduction to Graphs and Traversal Concepts
1.1. What is a Graph?
A graph consists of nodes (vertices) and edges (connections between nodes). In a graph:
● A vertex represents a node in the graph.
● An edge connects two vertices.
A graph can be:
1. Undirected: The edges have no direction. (e.g., A-B means you can go from A to B and
from B to A.)
2. Directed: The edges have direction. (e.g., A → B means you can only go from
A to B, not the other way around.)
1.2. Graph Representations
Graphs can be represented in multiple ways. In this course, we'll use:
1. Adjacency Matrix: A 2D array matrix[i][j] is used where the value is 1 if there’s an
edge between i and j and 0 if there’s no edge.
○ For an undirected graph, if there’s an edge between vertex i and j, both
matrix[i][j] and matrix[j][i] will be 1. For directed graphs, only
matrix[i][j] will be 1.
2. Adjacency List; A more space-efficient representation, where each node has a list (or
linked list) of its neighbors.
○ Best suited for sparse graphs (graphs with fewer edges).
We'll use the Adjacency Matrix representation for this tutorial.
Part 2: Understanding BFS and DFS
2.1. Breadth-First Search (BFS)
BFS is a graph traversal algorithm that explores the graph level by level, starting from a node
and visiting all its neighbors before moving on to the next level.
BFS Algorithm:
1. Start from the root node.
2. Mark the node as visited and enqueue it.
3. While the queue is not empty:
○ Dequeue a node from the queue.
○ Visit its unvisited neighbors and enqueue them.
Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
You can check out this visualization for more clarity.
2.2. Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking. It can be implemented
recursively or iteratively using a stack.
DFS Algorithm (using recursion):
1. Start from the root node.
2. Mark the node as visited.
3. Recursively visit all its unvisited neighbors.
DFS Algorithm (using stack):
1. Push the starting node onto the stack.
2. While the stack is not empty:
○ Pop a node from the stack.
○ If unvisited, mark it as visited and push its neighbors onto the stack.
Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
Refer to this visualization for a better understanding.
Part 3: Implementing Graph Representation and BFS/DFS
Now, let's implement the graph using an Adjacency Matrix and create BFS and DFS traversal
functions.
3.1. Graph Representation with Adjacency Matrix
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 10 // Maximum number of vertices in the graph
// Adjacency matrix for the graph
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
// Function to initialize the graph (set all values to 0)
void initGraph(int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
adjMatrix[i][j] = 0;
}
}
}
// Function to add an edge to the graph (for an undirected graph)
void addEdge(int src, int dest) {
adjMatrix[src][dest] = 1;
adjMatrix[dest][src] = 1; // Remove this line for directed graph
}
// Function to display the adjacency matrix
void printGraph(int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
printf("%d ", adjMatrix[i][j]);
}
printf("\n");
}
}
3.2. BFS Implementation
Now, let's implement BFS for the graph using the adjacency matrix.
#include <stdio.h>
#include <stdbool.h>
#define MAX_QUEUE_SIZE 100
Int count = 0;
// Queue structure
struct Queue {
int items[MAX_QUEUE_SIZE];
int front;
int rear;
};
// Queue functions
void initQueue(struct Queue* q) {
q->front = 0;
q->rear = -1;
}
int isEmpty(struct Queue* q) {
return q->rear == -1;
}
void enqueue(struct Queue* q, int value) {
if (q->rear == MAX_QUEUE_SIZE - 1) {
printf("Queue is full\n");
return;
}
q->items[++(q->rear)] = value;
}
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1;
}
return q->items[q->front++];
}
// BFS function
void bfs(int vertices, int startVertex) {
bool visited[vertices];
for (int i = 0; i < vertices; i++) {
visited[i] = false;
}
struct Queue q;
initQueue(&q);
visited[startVertex] = true;
enqueue(&q, startVertex);
while (!isEmpty(&q) && count<vertices) {
int currentVertex = dequeue(&q);
count++;
printf("Visited %d\n", currentVertex);
for (int i = 0; i < vertices; i++) {
if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
visited[i] = true;
enqueue(&q, i);
}
}
}
}
3.3. DFS Implementation (Recursive)
Next, let's implement DFS using recursion.
#include <stdio.h>
#include <stdbool.h>
// DFS function
void dfs(int vertices, int vertex, bool visited[]) {
visited[vertex] = true;
printf("Visited %d\n", vertex);
for (int i = 0; i < vertices; i++) {
if (adjMatrix[vertex][i] == 1 && !visited[i]) {
dfs(vertices, i, visited);
}
}
}
void dfsTraversal(int vertices, int startVertex) {
bool visited[vertices];
for (int i = 0; i < vertices; i++) {
visited[i] = false;
}
dfs(vertices, startVertex, visited);
}
Part 4: Practice Problems
4.1. Problem 1: BFS Traversal
Task: Implement a program that performs a BFS traversal starting from any node in a graph.
● Use the starter code and modify the main() function to create a graph, add edges, and
perform BFS.
● Print the visited nodes in BFS order.
-------------------------------------------------------------------------------------------------------------------------------
4.2. Problem 2: DFS Traversal
Task: Implement a program that performs a DFS traversal starting from any node in a graph.
● Use the starter code and modify the main() function to create a graph, add edges, and
perform DFS..
● Print the visited nodes in DFS order.
-------------------------------------------------------------------------------------------------------------------------------
4.3. Problem 3: Checking Graph Connectivity
Task: Given a graph, check if it is connected or not. A graph is connected if there is a path
between every pair of vertices. If all vertices can be reached starting from any arbitrary vertex
(e.g., vertex 0), the graph is connected; otherwise, it's disconnected.
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 10 // Maximum number of vertices in the graph
// Adjacency matrix for the graph
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
// Function to initialize the graph (set all values to 0)
void initGraph(int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
adjMatrix[i][j] = 0;
}
}
}
// Function to add an edge to the graph (undirected)
void addEdge(int src, int dest) {
adjMatrix[src][dest] = 1;
adjMatrix[dest][src] = 1; // Remove this line for directed graph
}
// Function to display the adjacency matrix (for debugging)
void printGraph(int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
printf("%d ", adjMatrix[i][j]);
}
printf("\n");
}
}
// Function to check graph connectivity (you need to implement this)
bool isConnected(int vertices) {
// Use DFS or BFS to check if all vertices can be visited
// (Hint: You can use DFS or BFS from vertex 0 to see if all
nodes are visited)
return true; // Change this line with your implementation
}
int main() {
int vertices = 6;
initGraph(vertices);
// Add some edges to create the graph
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 3);
addEdge(1, 4);
addEdge(2, 5);
// Check if the graph is connected
if (isConnected(vertices)) {
printf("The graph is connected.\n");
} else {
printf("The graph is disconnected.\n");
}
return 0;
}
Hints:
1. DFS or BFS: You will need to perform a DFS or BFS starting from an arbitrary vertex
(usually vertex 0).
○ Initialize a visited[] array to keep track of visited vertices.
○ Mark the starting vertex as visited, then visit all its neighbors, recursively or
iteratively (using a queue for BFS).
2. Checking Connectivity: After the traversal, check if all vertices were visited. If they
were, the graph is connected. Otherwise, it’s disconnected.
3. Edge Case: If there's only one vertex, the graph is trivially connected.
-------------------------------------------------------------------------------------------------------------------------------
4.4. Problem 4: Detecting Cycles in an Undirected Graph
Task: Given an undirected graph, detect if the graph contains a cycle. A cycle is a path where
you can start at a vertex, traverse edges, and return to the same vertex.
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 10 // Maximum number of vertices in the graph
// Adjacency matrix for the graph
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
// Function to initialize the graph (set all values to 0)
void initGraph(int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
adjMatrix[i][j] = 0;
}
}
}
// Function to add an edge to the graph (undirected)
void addEdge(int src, int dest) {
adjMatrix[src][dest] = 1;
adjMatrix[dest][src] = 1; // Remove this line for directed graph
}
// Function to display the adjacency matrix (for debugging)
void printGraph(int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
printf("%d ", adjMatrix[i][j]);
}
printf("\n");
}
}
// Function to detect cycle in the graph (you need to implement this)
bool hasCycleUtil(int vertices, int vertex, bool visited[], int
parent) {
// Your implementation here (Use DFS to detect a cycle)
return false; // Replace this with your implementation
}
bool hasCycle(int vertices) {
bool visited[vertices];
for (int i = 0; i < vertices; i++) {
visited[i] = false;
}
// Check for cycles in the graph
for (int i = 0; i < vertices; i++) {
if (!visited[i]) {
// Start DFS from vertex i
if (hasCycleUtil(vertices, i, visited, -1)) {
return true;
}
}
}
return false;
}
int main() {
int vertices = 6;
initGraph(vertices);
// Add edges to create the graph
addEdge(0, 1);
addEdge(1, 2);
addEdge(2, 3);
addEdge(3, 0); // This edge creates a cycle (0-1-2-3-0)
// Detect cycle in the graph
if (hasCycle(vertices)) {
printf("The graph contains a cycle.\n");
} else {
printf("The graph does not contain a cycle.\n");
}
return 0;
}
Hints:
1. Cycle Detection in an Undirected Graph:
○ Use DFS to explore each vertex.
○ Track the parent of each vertex (the vertex from which we arrived at the current
vertex) to avoid confusing the cycle with the backtracking edge.
○ If you encounter a visited vertex that is not the parent, a cycle is detected.
2. DFS Utility: The function hasCycleUtil() should perform DFS and check for cycles.
3. Handling Multiple Components: Ensure you start a DFS from every unvisited vertex to
handle disconnected graphs.
-------------------------------------------------------------------------------------------------------------------------------
4.5. Problem 5: Counting the Number of Connected Components
Task: Given an undirected graph, count the number of connected components. A connected
component is a set of vertices where there is a path between any two vertices in the set, and no
vertex in the set is connected to any vertex outside the set.
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 10 // Maximum number of vertices in the graph
// Adjacency matrix for the graph
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
// Function to initialize the graph (set all values to 0)
void initGraph(int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
adjMatrix[i][j] = 0;
}
}
}
// Function to add an edge to the graph (undirected)
void addEdge(int src, int dest) {
adjMatrix[src][dest] = 1;
adjMatrix[dest][src] = 1; // Remove this line for directed graph
}
// Function to display the adjacency matrix (for debugging)
void printGraph(int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
printf("%d ", adjMatrix[i][j]);
}
printf("\n");
}
}
// Function to count the number of connected components (you need to
implement this)
int countComponents(int vertices) {
// Your implementation here
return 0; // Remove this line and implement your solution
}
int main() {
int vertices = 6;
initGraph(vertices);
// Add edges to create the graph
addEdge(0, 1);
addEdge(2, 3);
addEdge(4, 5);
// Count the number of connected components
int components = countComponents(vertices);
printf("Number of connected components: %d\n", components);
return 0;
}
Hints:
1. DFS or BFS: You will need to use DFS (or BFS) to explore the graph.
○ From an unvisited vertex, perform DFS and mark all reachable vertices as
visited.
○ Every time you start a new DFS from an unvisited vertex, you’ve discovered a
new connected component.
2. Visited Array:
○ Keep track of visited vertices with a visited[] array.
○ Initially, all elements in the visited[] array should be false.
3. Counting Components:
○ Each time you find an unvisited vertex, perform DFS from that vertex, marking all
reachable vertices as visited.
○ Increment the component count each time a DFS starts from an unvisited vertex.
4. Multiple Components:
○ If the graph is disconnected, there will be multiple DFS calls, each discovering a
different connected component.
○ Ensure that you start DFS from each unvisited vertex to account for all connected
components in the graph.
5. Edge Case:
○ If there is only one vertex, the graph has only one connected component (the
vertex itself).
Homework Problems
1. Print All Connected Components.
2. Find All Nodes at a Given Distance from a Source Node (Using BFS) in a Directed
Graph.
3. Find if a Path Exists Between Two Nodes in a Directed Graph.
4. Find the Number of Isolated Nodes.
5. Count the Number of Leaf Nodes in a Directed Graph.
6. Find the Diameter of a Graph (Longest Path Between Two Nodes).
7. Check if a Graph is Bipartite.
