Welcome to Day 24 of the 100 Days of DSA challenge! Graph traversal methods such as BFS and DFS are fundamental for exploring and analyzing graph structures. Today's focus was on leveraging these techniques to solve practical problems, including shortest path determination, graph connectivity, and property checks.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s dive into the challenges tackled today! 🚀✨
1. Shortest Path in an Unweighted Graph
This program finds the shortest path in an unweighted graph using BFS. It represents the graph as an adjacency list and uses a queue to explore vertices level by level. A predecessor array tracks the previous node for each vertex to reconstruct the path, and a distance array records the shortest distance from the source. BFS starts from the source vertex, marks vertices as visited, and stops when the destination is reached. The shortest path and its length are then printed by backtracking through the predecessor array.
Code:
#include <iostream>
#include <queue>
using namespace std;
#define MAX 10 // Maximum number of vertices in the graph
// Graph represented using adjacency list
struct Node {
int vertex;
Node* next;
};
// Graph class with BFS-based shortest path functionality
class Graph {
private:
Node* adjList[MAX]; // Adjacency list for the graph
public:
// Constructor to initialize the graph
Graph() {
for (int i = 0; i < MAX; i++) {
adjList[i] = nullptr;
}
}
// Function to add an edge to the graph (undirected)
void add_edge(int src, int dest) {
// Add edge from src to dest
Node* newNode = new Node;
newNode->vertex = dest;
newNode->next = adjList[src];
adjList[src] = newNode;
// Add edge from dest to src (since it's an undirected graph)
newNode = new Node;
newNode->vertex = src;
newNode->next = adjList[dest];
adjList[dest] = newNode;
}
// BFS function to find the shortest path from source to destination
void shortest_path(int source, int destination) {
bool visited[MAX] = {false}; // Visited array
int predecessor[MAX]; // Array to store predecessors
int distance[MAX]; // Array to store distances from the source
// Initialize distance and predecessor arrays
for (int i = 0; i < MAX; i++) {
predecessor[i] = -1;
distance[i] = -1;
}
// BFS queue
queue<int> q;
visited[source] = true;
distance[source] = 0;
q.push(source);
// Perform BFS
while (!q.empty()) {
int current = q.front();
q.pop();
// Explore all neighbors of the current vertex
Node* temp = adjList[current];
while (temp != nullptr) {
if (!visited[temp->vertex]) {
visited[temp->vertex] = true;
distance[temp->vertex] = distance[current] + 1;
predecessor[temp->vertex] = current;
q.push(temp->vertex);
// Stop BFS when the destination is reached
if (temp->vertex == destination) {
break;
}
}
temp = temp->next;
}
}
// If destination is not reachable
if (!visited[destination]) {
cout << "No path exists between " << source << " and " << destination << endl;
return;
}
// Reconstruct the shortest path using the predecessor array
int crawl = destination;
cout << "Shortest path length is: " << distance[destination] << endl;
cout << "Path: ";
while (crawl != -1) {
cout << crawl << " ";
crawl = predecessor[crawl];
}
cout << endl;
}
};
int main() {
Graph g;
g.add_edge(0, 1);
g.add_edge(0, 2);
g.add_edge(1, 3);
g.add_edge(2, 3);
g.add_edge(3, 4);
g.add_edge(4, 5);
int source = 0, destination = 5;
g.shortest_path(source, destination);
return 0;
}
Output:
2. Flood Fill Problem
This program implements the flood-fill algorithm using DFS to change the color of a starting pixel and all its connected pixels with the same color to a new color. It uses recursive calls to explore 4-directional neighbors while ensuring boundary and color constraints.
Code:
#include <iostream>
using namespace std;
#define MAX_ROWS 10
#define MAX_COLS 10
// Function to perform DFS for flood fill
void flood_fill_dfs(int image[MAX_ROWS][MAX_COLS], int x, int y, int originalColor, int newColor, int rows, int cols) {
// Boundary checks and color match check
if (x < 0 || x >= rows || y < 0 || y >= cols || image[x][y] != originalColor || image[x][y] == newColor)
return;
// Change the color of the current pixel
image[x][y] = newColor;
// Recursive calls for 4-directional neighbors
flood_fill_dfs(image, x + 1, y, originalColor, newColor, rows, cols); // Down
flood_fill_dfs(image, x - 1, y, originalColor, newColor, rows, cols); // Up
flood_fill_dfs(image, x, y + 1, originalColor, newColor, rows, cols); // Right
flood_fill_dfs(image, x, y - 1, originalColor, newColor, rows, cols); // Left
}
// Wrapper function to start flood fill
void flood_fill(int image[MAX_ROWS][MAX_COLS], int startX, int startY, int newColor, int rows, int cols) {
int originalColor = image[startX][startY];
// If the color to change is the same as the new color, no need to do anything
if (originalColor == newColor)
return;
// Call the DFS function
flood_fill_dfs(image, startX, startY, originalColor, newColor, rows, cols);
}
// Function to display the grid
void display_image(int image[MAX_ROWS][MAX_COLS], int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cout << image[i][j] << " ";
}
cout << endl;
}
}
int main() {
int image[MAX_ROWS][MAX_COLS] = {
{1, 1, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 1, 1, 1},
{0, 0, 1, 1, 0}
};
int rows = 4, cols = 5; // Size of the image
cout << "Original Image:" << endl;
display_image(image, rows, cols);
int startX = 1, startY = 1; // Starting point
int newColor = 2; // New color to fill
flood_fill(image, startX, startY, newColor, rows, cols);
cout << "Image after Flood Fill:" << endl;
display_image(image, rows, cols);
return 0;
}
Output:
3. Solve the "find connected components in a graph" problem using BFS/DFS.
This program represents an undirected graph using an adjacency list and identifies all connected components in the graph. It initializes the graph structure, adds edges between vertices, and traverses the graph using Depth-First Search (DFS). For each unvisited vertex, it explores and prints the vertices of the connected component to which it belongs. This process ensures that all components are identified and displayed.
Code:
#include <iostream>
#include <queue>
using namespace std;
#define MAX 10 // Maximum number of vertices
// Structure to represent the adjacency list
struct Node {
int vertex;
Node* next;
};
// Graph class
class Graph {
private:
Node* adj_list[MAX]; // Adjacency list
bool visited[MAX]; // Visited array
public:
// Constructor to initialize the graph
Graph() {
for (int i = 0; i < MAX; i++) {
adj_list[i] = nullptr;
visited[i] = false;
}
}
// Add an undirected edge
void add_edge(int src, int dest) {
// Add edge from src to dest
Node* new_node = new Node;
new_node->vertex = dest;
new_node->next = adj_list[src];
adj_list[src] = new_node;
// Add edge from dest to src
new_node = new Node;
new_node->vertex = src;
new_node->next = adj_list[dest];
adj_list[dest] = new_node;
}
// DFS to explore a connected component
void dfs(int v) {
visited[v] = true;
cout << v << " ";
Node* temp = adj_list[v];
while (temp != nullptr) {
if (!visited[temp->vertex]) {
dfs(temp->vertex);
}
temp = temp->next;
}
}
// Function to find and print all connected components
void connected_components() {
for (int i = 0; i < MAX; i++) {
if (!visited[i] && adj_list[i] != nullptr) { // Check for unvisited vertex
cout << "Connected Component: ";
dfs(i); // Explore the component using DFS
cout << endl;
}
}
}
};
int main() {
Graph g;
g.add_edge(0, 1);
g.add_edge(1, 2);
g.add_edge(3, 4);
g.add_edge(5, 6);
g.add_edge(7, 8);
g.add_edge(8, 9);
cout << "Connected Components in the Graph:" << endl;
g.connected_components();
return 0;
}
Output:
4. Check if a Graph is Bipartite
This program checks if an undirected graph is bipartite by using a BFS approach. It represents the graph using an adjacency list and colors each vertex with one of two colors (0 or 1). Starting from an unvisited vertex, it colors the vertex and its neighbors alternately. If any two adjacent vertices end up with the same color, the graph is determined to be non-bipartite. The program checks all connected components of the graph to ensure that the entire graph is bipartite.
Code:
#include <iostream>
#include <queue>
using namespace std;
#define MAX 10 // Maximum number of vertices
// Structure to represent the adjacency list
struct Node {
int vertex;
Node* next;
};
// Graph class
class Graph {
private:
Node* adj_list[MAX]; // Adjacency list
bool visited[MAX]; // Visited array
int color[MAX]; // Array to store colors (0 or 1)
public:
// Constructor to initialize the graph
Graph() {
for (int i = 0; i < MAX; i++) {
adj_list[i] = nullptr;
visited[i] = false;
color[i] = -1; // No color assigned initially
}
}
// Add an undirected edge
void add_edge(int src, int dest) {
Node* new_node = new Node;
new_node->vertex = dest;
new_node->next = adj_list[src];
adj_list[src] = new_node;
new_node = new Node;
new_node->vertex = src;
new_node->next = adj_list[dest];
adj_list[dest] = new_node;
}
// Function to check if the graph is bipartite
bool is_bipartite(int start) {
queue<int> q;
// Start with the given vertex, color it with 0
color[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
Node* temp = adj_list[u];
while (temp != nullptr) {
int v = temp->vertex;
// If the vertex is not visited, color it with opposite color
if (color[v] == -1) {
color[v] = 1 - color[u];
q.push(v);
}
// If the adjacent vertex has the same color, the graph is not bipartite
else if (color[v] == color[u]) {
return false;
}
temp = temp->next;
}
}
return true;
}
// Function to check all components for bipartite property
bool check_bipartite() {
// Check for each unvisited component
for (int i = 0; i < MAX; i++) {
if (!visited[i] && adj_list[i] != nullptr) {
if (!is_bipartite(i)) {
return false;
}
}
}
return true;
}
};
int main() {
Graph g;
g.add_edge(0, 1);
g.add_edge(1, 2);
g.add_edge(2, 3);
g.add_edge(3, 4);
g.add_edge(4, 5);
g.add_edge(5, 0);
if (g.check_bipartite()) {
cout << "The graph is bipartite." << endl;
} else {
cout << "The graph is not bipartite." << endl;
}
return 0;
}
Output:
5. Word Ladder Problem
This program implements the "Word Ladder" problem using a breadth-first search (BFS) approach. It maintains a dictionary of words and checks for valid transformations between words that differ by exactly one character. Starting from the start_word, it uses a queue to explore all possible one-letter transformations level by level until it finds the end_word, returning the shortest transformation sequence length. If no valid sequence exists, it returns 0.
Code:
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 50 // Maximum number of words in the dictionary
// Graph class for Word Ladder problem
class WordLadder {
private:
char dictionary[MAX][50]; // Dictionary of words
int word_count; // Total number of words in the dictionary
public:
// Constructor to initialize the dictionary
WordLadder() {
word_count = 0;
}
// Add word to the dictionary
void add_word(const char* word) {
strcpy(dictionary[word_count++], word);
}
// Function to check if two words differ by exactly one character
bool one_letter_diff(const char* word1, const char* word2) {
int diff_count = 0;
int len1 = strlen(word1);
int len2 = strlen(word2);
if (len1 != len2) return false; // Words must have the same length
for (int i = 0; i < len1; i++) {
if (word1[i] != word2[i]) {
diff_count++;
}
}
return (diff_count == 1); // They should differ by exactly one letter
}
// BFS to find the shortest transformation sequence
int find_word_ladder(const char* start, const char* end) {
if (strcmp(start, end) == 0) return 0; // If the start and end words are the same
bool visited[MAX] = {false}; // Keep track of visited words
queue<pair<const char*, int>> q; // Queue for BFS, storing word and level (steps)
q.push({start, 1});
visited[0] = true;
while (!q.empty()) {
const char* current_word = q.front().first;
int level = q.front().second;
q.pop();
// Check all words in the dictionary for possible transformation
for (int i = 0; i < word_count; i++) {
if (!visited[i] && one_letter_diff(current_word, dictionary[i])) {
// If end word is found, return the current level + 1
if (strcmp(dictionary[i], end) == 0) {
return level + 1;
}
visited[i] = true;
q.push({dictionary[i], level + 1});
}
}
}
return 0; // If no transformation is found
}
};
int main() {
WordLadder word_ladder;
word_ladder.add_word("hit");
word_ladder.add_word("hot");
word_ladder.add_word("dot");
word_ladder.add_word("dog");
word_ladder.add_word("cog");
const char* start_word = "hit";
const char* end_word = "cog";
int result = word_ladder.find_word_ladder(start_word, end_word);
if (result == 0) {
cout << "No transformation sequence found." << endl;
} else {
cout << "The shortest transformation sequence length is: " << result << endl;
}
return 0;
}
Output:
BFS and DFS highlighted their adaptability in addressing a range of problems, from network analysis to connectivity checks. These traversal algorithms are foundational tools, paving the way for mastering more advanced graph concepts and real-world applications. 🚀