Welcome to Day 32 of my 100 Days of DSA challenge! Today’s focus was on tackling hard graph problems, pushing the boundaries of algorithmic thinking and optimization. The tasks included solving challenges like finding the smallest cycle, identifying critical edges, and determining the cheapest flights within constraints. These problems required advanced traversal techniques, modifications to classic algorithms, and a deep understanding of graph theory.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let's dive into the solutions! 🚀
1. Minimum Cost to Make At Least One Path Between Any Two Nodes
This program solves the minimum cost to connect all nodes (Minimum Spanning Tree problem) using Prim's Algorithm. The graph is represented using an adjacency matrix graph. The find_minimum_cost method iteratively selects the edge with the smallest weight that connects an unvisited node to the current tree. It ensures all nodes are visited while minimizing the total cost. The result is the total cost of the minimum spanning tree.
Code:
#include <iostream>
#include <cstring>
#include <climits>
using namespace std;
#define MAX_NODES 100
#define INF INT_MAX
class MinimumCostPath {
private:
int graph[MAX_NODES][MAX_NODES]; // Adjacency matrix to store edge costs
int num_nodes;
public:
MinimumCostPath(int nodes) {
num_nodes = nodes;
for (int i = 0; i < num_nodes; i++) {
for (int j = 0; j < num_nodes; j++) {
if (i == j)
graph[i][j] = 0; // No cost for self-loops
else
graph[i][j] = INF; // Initialize other edges with INF
}
}
}
void add_edge(int u, int v, int cost) {
graph[u][v] = cost;
graph[v][u] = cost; // Assuming undirected graph
}
int find_minimum_cost() {
bool visited[MAX_NODES] = {false}; // Track visited nodes
int min_cost[MAX_NODES]; // Minimum cost to include each node
for (int i = 0; i < num_nodes; i++) {
min_cost[i] = INF; // Initialize all costs to INF
}
min_cost[0] = 0; // Start with the first node
int total_cost = 0;
for (int count = 0; count < num_nodes; count++) {
int u = -1;
// Find the unvisited node with the smallest cost
for (int i = 0; i < num_nodes; i++) {
if (!visited[i] && (u == -1 || min_cost[i] < min_cost[u])) {
u = i;
}
}
visited[u] = true; // Mark the node as visited
total_cost += min_cost[u]; // Add its cost to the total
// Update costs of adjacent nodes
for (int v = 0; v < num_nodes; v++) {
if (graph[u][v] != INF && !visited[v] && graph[u][v] < min_cost[v]) {
min_cost[v] = graph[u][v];
}
}
}
return total_cost; // Return the minimum cost to connect all nodes
}
};
int main() {
int num_nodes, num_edges;
cout << "Enter the number of nodes and edges: ";
cin >> num_nodes >> num_edges;
MinimumCostPath min_cost_path(num_nodes);
cout << "Enter the edges (u v cost):" << endl;
for (int i = 0; i < num_edges; i++) {
int u, v, cost;
cin >> u >> v >> cost;
min_cost_path.add_edge(u, v, cost);
}
cout << "Minimum cost to connect all nodes: " << min_cost_path.find_minimum_cost() << endl;
return 0;
}
Output:
2. Cheapest Flights Within K Stops
This program uses a breadth-first search (BFS) approach with a queue to explore all possible routes from the source city to the destination city within k stops. Each queue entry stores the number of stops, current city, and cumulative cost. It keeps track of the minimum cost to reach each city. If the current route cost is lower, the route is added to the queue for further exploration. The adjacency matrix represents the direct flight connections and their costs.
Code:
#include <iostream>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;
#define MAX 1000 // Maximum number of cities
class CheapestFlights {
private:
int adj_matrix[MAX][MAX]; // Adjacency matrix to store flight costs
int num_cities; // Number of cities
public:
CheapestFlights(int cities) {
num_cities = cities;
for (int i = 0; i < num_cities; i++) {
for (int j = 0; j < num_cities; j++) {
adj_matrix[i][j] = -1; // Initialize with no direct connection
}
}
}
void add_flight(int src, int dest, int cost) {
adj_matrix[src][dest] = cost;
}
int find_cheapest_flight(int src, int dest, int k) {
queue<pair<int, pair<int, int>>> bfs_queue; // {stops, {current_city, cost}}
bfs_queue.push({0, {src, 0}});
int min_cost[MAX];
// Initialize minimum cost to reach each city as infinity
for (int i = 0; i < num_cities; i++) {
min_cost[i] = INT_MAX;
}
min_cost[src] = 0;
while (!bfs_queue.empty()) {
auto front = bfs_queue.front();
bfs_queue.pop();
int stops = front.first;
int current_city = front.second.first;
int current_cost = front.second.second;
// If the number of stops exceeds k, skip further processing
if (stops > k) {
continue;
}
// Explore neighbors
for (int neighbor = 0; neighbor < num_cities; neighbor++) {
if (adj_matrix[current_city][neighbor] != -1) {
int new_cost = current_cost + adj_matrix[current_city][neighbor];
// Only proceed if the new cost is lower
if (new_cost < min_cost[neighbor]) {
min_cost[neighbor] = new_cost;
bfs_queue.push({stops + 1, {neighbor, new_cost}});
}
}
}
}
return min_cost[dest] == INT_MAX ? -1 : min_cost[dest];
}
};
int main() {
int num_cities = 4;
CheapestFlights flights(num_cities);
flights.add_flight(0, 1, 100);
flights.add_flight(1, 2, 100);
flights.add_flight(0, 2, 500);
flights.add_flight(2, 3, 100);
int src = 0, dest = 3, k = 2;
cout << "Cheapest price from " << src << " to " << dest << " within " << k << " stops: "
<< flights.find_cheapest_flight(src, dest, k) << endl;
return 0;
}
Output:
3. Redundant Directed Connection in a Graph
This program identifies a redundant directed edge in a graph using Union-Find. It tracks the parent of each node and performs union operations for edges. If a union operation fails (the nodes are already connected), the current edge is identified as redundant. The Union-Find data structure is used with path compression to optimize the root finding process. The redundant edge is returned as the result.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX_NODES 1000
class Graph {
private:
int parent[MAX_NODES];
// Helper function to find the root of a node
int find_root(int node) {
if (parent[node] == -1) {
return node;
}
return parent[node] = find_root(parent[node]); // Path compression
}
// Helper function to unite two nodes
bool union_nodes(int u, int v) {
int root_u = find_root(u);
int root_v = find_root(v);
if (root_u == root_v) {
return false; // A cycle is detected
}
parent[root_u] = root_v; // Union operation
return true;
}
public:
Graph() {
memset(parent, -1, sizeof(parent)); // Initialize all nodes as their own roots
}
// Function to find the redundant directed connection
pair<int, int> find_redundant_connection(int edges[][2], int edge_count) {
pair<int, int> redundant_edge;
for (int i = 0; i < edge_count; i++) {
int u = edges[i][0];
int v = edges[i][1];
if (!union_nodes(u, v)) {
redundant_edge = {u, v}; // Store the redundant edge
}
}
return redundant_edge;
}
};
int main() {
int edge_count;
cout << "Enter the number of edges: ";
cin >> edge_count;
int edges[MAX_NODES][2];
cout << "Enter the edges (u v):" << endl;
for (int i = 0; i < edge_count; i++) {
cin >> edges[i][0] >> edges[i][1];
}
Graph graph;
pair<int, int> redundant_edge = graph.find_redundant_connection(edges, edge_count);
cout << "Redundant Edge: " << redundant_edge.first << " -> " << redundant_edge.second << endl;
return 0;
}
Output:
4. Critical Edges in a Graph
This program identifies critical edges (bridges) in a graph using Depth First Search (DFS). It maintains discovery times and the lowest point reachable from each vertex. During DFS traversal, if the lowest point reachable from a child vertex is greater than the discovery time of the current vertex, the edge is critical.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 100 // Maximum number of vertices in the graph
class CriticalEdges {
private:
int graph[MAX][MAX]; // Adjacency matrix to represent the graph
bool visited[MAX]; // Array to track visited nodes
int discovery[MAX]; // Discovery times of visited vertices
int low[MAX]; // Earliest visited vertex reachable from subtree
int parent[MAX]; // Parent vertices in DFS tree
int time; // Timer for discovery time
int vertices; // Number of vertices in the graph
void dfs(int u) {
visited[u] = true;
discovery[u] = low[u] = ++time;
for (int v = 0; v < vertices; v++) {
if (graph[u][v]) { // Check adjacency
if (!visited[v]) {
parent[v] = u;
dfs(v);
// Update the low value of the current vertex
low[u] = min(low[u], low[v]);
// If the edge (u, v) is a critical edge
if (low[v] > discovery[u]) {
cout << u << " -> " << v << endl;
}
} else if (v != parent[u]) {
low[u] = min(low[u], discovery[v]);
}
}
}
}
public:
CriticalEdges(int n) {
vertices = n;
memset(graph, 0, sizeof(graph));
memset(visited, false, sizeof(visited));
memset(discovery, -1, sizeof(discovery));
memset(low, -1, sizeof(low));
memset(parent, -1, sizeof(parent));
time = 0;
}
void add_edge(int u, int v) {
graph[u][v] = 1;
graph[v][u] = 1;
}
void find_critical_edges() {
for (int i = 0; i < vertices; i++) {
if (!visited[i]) {
dfs(i);
}
}
}
};
int main() {
int vertices, edges;
cout << "Enter the number of vertices: ";
cin >> vertices;
cout << "Enter the number of edges: ";
cin >> edges;
CriticalEdges graph(vertices);
cout << "Enter the edges (u v):" << endl;
for (int i = 0; i < edges; i++) {
int u, v;
cin >> u >> v;
graph.add_edge(u, v);
}
cout << "Critical edges in the graph are:" << endl;
graph.find_critical_edges();
return 0;
}
Output:
5. Smallest Cycle in a Graph
This program finds the smallest cycle in an undirected graph. It uses a breadth-first search (BFS) from each node, tracking distances and parents to detect cycles. A cycle is found when a visited neighbor is not the parent of the current node. The length of the cycle is computed and updated if it is smaller than the previous cycles found. If no cycles exist, it outputs -1.
Code:
#include <iostream>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;
#define MAX_NODES 1000
class Graph {
private:
int adj_matrix[MAX_NODES][MAX_NODES];
int num_nodes;
public:
// Constructor to initialize the graph
Graph(int nodes) {
num_nodes = nodes;
memset(adj_matrix, 0, sizeof(adj_matrix)); // Initialize adjacency matrix
}
// Function to add an edge to the graph
void add_edge(int u, int v) {
adj_matrix[u][v] = 1;
adj_matrix[v][u] = 1;
}
// Function to find the smallest cycle in the graph
int find_smallest_cycle() {
int smallest_cycle = INT_MAX;
for (int start_node = 0; start_node < num_nodes; start_node++) {
int distance[MAX_NODES];
int parent[MAX_NODES];
memset(distance, -1, sizeof(distance));
memset(parent, -1, sizeof(parent));
queue<int> q;
q.push(start_node);
distance[start_node] = 0;
while (!q.empty()) {
int current_node = q.front();
q.pop();
for (int neighbor = 0; neighbor < num_nodes; neighbor++) {
if (adj_matrix[current_node][neighbor]) {
if (distance[neighbor] == -1) {
// Neighbor not visited
distance[neighbor] = distance[current_node] + 1;
parent[neighbor] = current_node;
q.push(neighbor);
} else if (parent[current_node] != neighbor) {
// Found a cycle
int cycle_length = distance[current_node] + distance[neighbor] + 1;
smallest_cycle = min(smallest_cycle, cycle_length);
}
}
}
}
}
return (smallest_cycle == INT_MAX) ? -1 : smallest_cycle; // Return -1 if no cycle found
}
};
int main() {
int num_nodes, num_edges;
cout << "Enter the number of nodes and edges: ";
cin >> num_nodes >> num_edges;
Graph graph(num_nodes);
cout << "Enter the edges (u v format):" << endl;
for (int i = 0; i < num_edges; i++) {
int u, v;
cin >> u >> v;
graph.add_edge(u, v);
}
int result = graph.find_smallest_cycle();
if (result == -1) {
cout << "No cycle found in the graph." << endl;
} else {
cout << "The smallest cycle length is: " << result << endl;
}
return 0;
}
Output:
Day 32 delved into challenging graph problems that pushed the boundaries of problem-solving and algorithmic thinking. From optimizing paths and detecting cycles to analyzing critical connections, these tasks demonstrated the depth and complexity of graph theory in addressing advanced computational scenarios. 🚀