Day 23 of my 100 Days of DSA challenge focused on the fundamentals of graph theory. I worked on graph representation using adjacency lists and matrices, and explored essential traversal techniques like BFS and DFS. These foundational concepts are critical for solving complex problems in networking, pathfinding, and more.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s keep learning and building! 🚀
1. Represent a graph using an adjacency list and an adjacency matrix.
This program represents a graph using both an adjacency list and an adjacency matrix. It defines a Graph class where edges are added to both representations. The adjacency list is implemented using linked lists for each vertex, while the adjacency matrix uses a 2D array.
Code:
#include <iostream>
using namespace std;
#define MAX 5 // Maximum number of vertices in the graph
// Graph represented using Adjacency List
struct Node {
int vertex;
Node* next;
};
// Graph class with adjacency list and matrix
class Graph {
private:
Node* adjList[MAX]; // Adjacency list for the graph
int adjMatrix[MAX][MAX]; // Adjacency matrix for the graph
public:
// Constructor to initialize the graph
Graph() {
for (int i = 0; i < MAX; i++) {
adjList[i] = nullptr;
for (int j = 0; j < MAX; j++) {
adjMatrix[i][j] = 0; // Initialize matrix with 0 (no edges)
}
}
}
// Function to add an edge in the adjacency list
void add_edge_list(int src, int dest) {
Node* newNode = new Node;
newNode->vertex = dest;
newNode->next = adjList[src];
adjList[src] = newNode;
// For undirected graph, add the reverse edge as well
newNode = new Node;
newNode->vertex = src;
newNode->next = adjList[dest];
adjList[dest] = newNode;
}
// Function to add an edge in the adjacency matrix
void add_edge_matrix(int src, int dest) {
adjMatrix[src][dest] = 1;
adjMatrix[dest][src] = 1; // For undirected graph, mark the reverse edge
}
// Function to display the adjacency list
void display_adj_list() {
for (int i = 0; i < MAX; i++) {
cout << "Vertex " << i << ": ";
Node* temp = adjList[i];
while (temp != nullptr) {
cout << temp->vertex << " ";
temp = temp->next;
}
cout << endl;
}
}
// Function to display the adjacency matrix
void display_adj_matrix() {
cout << "Adjacency Matrix: \n";
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
Graph g;
g.add_edge_list(0, 1);
g.add_edge_list(0, 4);
g.add_edge_list(1, 2);
g.add_edge_list(1, 3);
g.add_edge_list(1, 4);
g.add_edge_list(3, 4);
g.add_edge_matrix(0, 1);
g.add_edge_matrix(0, 4);
g.add_edge_matrix(1, 2);
g.add_edge_matrix(1, 3);
g.add_edge_matrix(1, 4);
g.add_edge_matrix(3, 4);
cout << "Adjacency List Representation:\n";
g.display_adj_list();
cout << "\nAdjacency Matrix Representation:\n";
g.display_adj_matrix();
return 0;
}
Output:
2. Depth-First Search (DFS) for a Graph
This program implements a depth-first search (DFS) for an undirected graph represented using an adjacency list. It adds edges between vertices, then performs DFS starting from a specified vertex. The DFS is simulated using a stack, where the program explores each vertex, marking it as visited and pushing its unvisited neighbors onto the stack. The traversal continues until all reachable vertices from the starting point are visited.
Code:
#include <iostream>
#include <stack>
using namespace std;
#define MAX 5 // Maximum number of vertices in the graph
// Graph represented using Adjacency List
struct Node {
int vertex;
Node* next;
};
// Graph class with DFS 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; // Initialize all lists as empty
}
}
// Function to add an edge in 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 (for undirected graph)
newNode = new Node;
newNode->vertex = src;
newNode->next = adjList[dest];
adjList[dest] = newNode;
}
// Function to perform DFS starting from a given vertex
void dfs(int start) {
bool visited[MAX] = {false}; // Array to keep track of visited vertices
stack<int> s; // Stack to simulate the recursion of DFS
// Push the starting vertex onto the stack
s.push(start);
visited[start] = true;
cout << "DFS Traversal starting from vertex " << start << ": ";
// While the stack is not empty, keep performing DFS
while (!s.empty()) {
int current = s.top();
s.pop();
cout << current << " "; // Print the visited vertex
// Explore all the neighbors of the current vertex
Node* temp = adjList[current];
while (temp != nullptr) {
if (!visited[temp->vertex]) { // If the neighbor hasn't been visited
visited[temp->vertex] = true;
s.push(temp->vertex); // Push the neighbor onto the stack
}
temp = temp->next;
}
}
cout << endl;
}
};
int main() {
Graph g;
g.add_edge(0, 1);
g.add_edge(0, 4);
g.add_edge(1, 2);
g.add_edge(1, 3);
g.add_edge(1, 4);
g.add_edge(3, 4);
g.dfs(0);
return 0;
}
Output:
3. Breadth-First Search (BFS) for a Graph
This program implements a breadth-first search (BFS) for an undirected graph represented using an adjacency list. It starts BFS from a given vertex, explores all its neighbors, and then continues exploring neighbors of subsequent vertices level by level. A queue is used to manage the vertices during traversal, and a visited array ensures that each vertex is visited only once.
Code:
#include <iostream>
#include <queue>
using namespace std;
#define MAX 5 // Maximum number of vertices in the graph
// Graph represented using Adjacency List
struct Node {
int vertex;
Node* next;
};
// Graph class with BFS 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; // Initialize all lists as empty
}
}
// Function to add an edge in 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 (for undirected graph)
newNode = new Node;
newNode->vertex = src;
newNode->next = adjList[dest];
adjList[dest] = newNode;
}
// Function to perform BFS starting from a given vertex
void bfs(int start) {
bool visited[MAX] = {false}; // Array to keep track of visited vertices
queue<int> q; // Queue to manage BFS order
// Mark the starting vertex as visited and enqueue it
visited[start] = true;
q.push(start);
cout << "BFS Traversal starting from vertex " << start << ": ";
// While the queue is not empty, keep performing BFS
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current << " "; // Print the visited vertex
// Explore all the neighbors of the current vertex
Node* temp = adjList[current];
while (temp != nullptr) {
if (!visited[temp->vertex]) { // If the neighbor hasn't been visited
visited[temp->vertex] = true;
q.push(temp->vertex); // Enqueue the neighbor
}
temp = temp->next;
}
}
cout << endl;
}
};
int main() {
Graph g;
g.add_edge(0, 1);
g.add_edge(0, 4);
g.add_edge(1, 2);
g.add_edge(1, 3);
g.add_edge(1, 4);
g.add_edge(3, 4);
g.bfs(0);
return 0;
}
Output:
4. Number of Islands
This program counts the number of islands in a 2D grid, where '1' represents land and '0' represents water. It uses Depth-First Search (DFS) to explore and mark all connected land cells starting from an unvisited '1'. Each time a new unvisited land cell is found, a DFS is initiated to mark all connected land cells as visited, representing one island. The program then counts the total number of such DFS calls, which corresponds to the number of islands in the grid.
Code:
#include <iostream>
using namespace std;
#define ROWS 5 // Number of rows in the grid
#define COLS 5 // Number of columns in the grid
// Directions for moving in 4 adjacent directions (left, right, up, down)
int row_dirs[] = {-1, 1, 0, 0};
int col_dirs[] = {0, 0, -1, 1};
// Function to perform DFS and mark the connected land
void DFS(char grid[ROWS][COLS], int visited[ROWS][COLS], int row, int col) {
// Stack-based DFS approach to avoid recursion limit issues
visited[row][col] = 1;
// Explore all adjacent cells (up, down, left, right)
for (int i = 0; i < 4; i++) {
int new_row = row + row_dirs[i];
int new_col = col + col_dirs[i];
// Check if the new position is within bounds and is land ('1') and not visited
if (new_row >= 0 && new_row < ROWS && new_col >= 0 && new_col < COLS
&& grid[new_row][new_col] == '1' && visited[new_row][new_col] == 0) {
DFS(grid, visited, new_row, new_col);
}
}
}
// Function to count the number of islands in the grid
int no_islands(char grid[ROWS][COLS]) {
int visited[ROWS][COLS] = {0}; // Array to keep track of visited cells
int count = 0;
// Traverse the grid
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
// If we find an unvisited land cell, it's the start of a new island
if (grid[i][j] == '1' && visited[i][j] == 0) {
DFS(grid, visited, i, j); // Mark all connected land cells
count++; // Increment island count
}
}
}
return count;
}
int main() {
// 5x5 grid with some land ('1') and water ('0')
char grid[ROWS][COLS] = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'},
{'0', '0', '0', '0', '1'}
};
int result = no_islands(grid);
cout << "Number of islands: " << result << endl;
return 0;
}
Output:
5. Solve the "detect a cycle in an undirected graph" problem using DFS.
This program detects if there is a cycle in an undirected graph using Depth-First Search (DFS). It represents the graph using an adjacency list and performs DFS from each unvisited vertex. During DFS, it checks if an adjacent vertex is already visited and is not the parent of the current vertex, indicating a cycle.
Code:
#include <iostream>
using namespace std;
#define MAX 5 // Maximum number of vertices in the graph
// Graph represented using Adjacency List
struct Node {
int vertex;
Node* next;
};
// Graph class with cycle detection 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; // Initialize all lists as empty
}
}
// Function to add an edge in 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 (for undirected graph)
newNode = new Node;
newNode->vertex = src;
newNode->next = adjList[dest];
adjList[dest] = newNode;
}
// Helper function to perform DFS and detect cycles
bool dfs(int current, bool visited[MAX], bool parent[MAX]) {
visited[current] = true;
// Explore all the neighbors of the current vertex
Node* temp = adjList[current];
while (temp != nullptr) {
if (!visited[temp->vertex]) {
// Recur for unvisited neighbors
if (dfs(temp->vertex, visited, parent)) {
return true;
}
}
// If an adjacent vertex is visited and not the parent, a cycle is found
else if (visited[temp->vertex] && parent[current] != temp->vertex) {
return true;
}
temp = temp->next;
}
return false;
}
// Function to detect a cycle in the graph
bool detect_cycle() {
bool visited[MAX] = {false}; // Array to keep track of visited vertices
bool parent[MAX] = {false}; // Array to keep track of the parent vertices
// Run DFS from each unvisited vertex
for (int i = 0; i < MAX; i++) {
if (!visited[i]) {
if (dfs(i, visited, parent)) {
return true; // Cycle found
}
}
}
return false; // No cycle found
}
};
int main() {
Graph g;
g.add_edge(0, 1);
g.add_edge(0, 4);
g.add_edge(1, 2);
g.add_edge(1, 3);
g.add_edge(1, 4);
g.add_edge(3, 4);
if (g.detect_cycle()) {
cout << "Cycle detected in the graph." << endl;
} else {
cout << "No cycle detected in the graph." << endl;
}
return 0;
}
Output:
Day 23 highlighted the power of graph traversal techniques in solving real-world problems. Whether it's detecting cycles or counting islands, mastering BFS and DFS lays the foundation for more advanced graph algorithms and optimizations. Looking forward to diving deeper into graph theory! 🚀