Welcome to Day 31 of my 100 Days of DSA challenge! Today’s focus was on advanced graph algorithms, delving into topics like shortest paths in DAGs, handling negative weights with Bellman-Ford, and exploring critical graph structures with Tarjan’s and Kosaraju's algorithms. These problems showcased the depth of graph theory and its applications in solving complex network-related challenges.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Take a look the challenges solved and the techniques applied! 🚀
1. Shortest Path in a Directed Acyclic Graph (DAG)
Code:
#include <iostream>
#include <cstring>
#include <stack>
#include <climits>
using namespace std;
#define MAX_NODES 100
class Graph {
private:
int adj_matrix[MAX_NODES][MAX_NODES]; // Adjacency matrix for the graph
int num_nodes;
// Function to perform topological sort
void topological_sort_util(int node, bool visited[], stack<int> &stack) {
visited[node] = true;
for (int i = 0; i < num_nodes; i++) {
if (adj_matrix[node][i] != 0 && !visited[i]) {
topological_sort_util(i, visited, stack);
}
}
stack.push(node);
}
public:
// Constructor
Graph(int nodes) {
num_nodes = nodes;
memset(adj_matrix, 0, sizeof(adj_matrix));
}
// Function to add a directed edge with weight
void add_edge(int u, int v, int weight) {
adj_matrix[u][v] = weight;
}
// Function to find shortest path from the source node
void shortest_path(int source) {
stack<int> stack;
bool visited[MAX_NODES] = {false};
// Perform topological sort
for (int i = 0; i < num_nodes; i++) {
if (!visited[i]) {
topological_sort_util(i, visited, stack);
}
}
// Initialize distances
int distance[MAX_NODES];
for (int i = 0; i < num_nodes; i++) {
distance[i] = INT_MAX;
}
distance[source] = 0;
// Process nodes in topological order
while (!stack.empty()) {
int u = stack.top();
stack.pop();
if (distance[u] != INT_MAX) {
for (int v = 0; v < num_nodes; v++) {
if (adj_matrix[u][v] != 0) {
if (distance[v] > distance[u] + adj_matrix[u][v]) {
distance[v] = distance[u] + adj_matrix[u][v];
}
}
}
}
}
// Print distances
cout << "Shortest distances from node " << source << ":" << endl;
for (int i = 0; i < num_nodes; i++) {
if (distance[i] == INT_MAX) {
cout << "Node " << i << ": INF" << endl;
} else {
cout << "Node " << i << ": " << distance[i] << endl;
}
}
}
};
int main() {
int nodes = 6;
Graph graph(nodes);
graph.add_edge(0, 1, 2);
graph.add_edge(0, 4, 1);
graph.add_edge(1, 2, 3);
graph.add_edge(4, 2, 2);
graph.add_edge(4, 5, 4);
graph.add_edge(2, 3, 6);
graph.add_edge(5, 3, 1);
int source = 0;
graph.shortest_path(source);
return 0;
}
Output:
2. Bellman-Ford Algorithm
This program implements the Bellman-Ford algorithm to calculate the shortest path from a source vertex to all other vertices in a weighted graph that may contain negative weight edges. It relaxes each edge (num_vertices - 1) times to find shortest distances and checks for negative weight cycles. If a cycle is detected, it halts and reports it. Otherwise, it prints the shortest distances from the source to each vertex.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX_EDGES 1000
#define INF 1e9
struct Edge {
int src;
int dest;
int weight;
};
class BellmanFord {
private:
int num_vertices, num_edges;
Edge edges[MAX_EDGES];
public:
BellmanFord(int vertices, int edges_count) {
num_vertices = vertices;
num_edges = edges_count;
}
void add_edge(int index, int src, int dest, int weight) {
edges[index].src = src;
edges[index].dest = dest;
edges[index].weight = weight;
}
void find_shortest_path(int start_vertex) {
int distance[num_vertices];
for (int i = 0; i < num_vertices; i++) {
distance[i] = INF; // Initialize distances as infinite
}
distance[start_vertex] = 0;
// Relax all edges (num_vertices - 1) times
for (int i = 1; i <= num_vertices - 1; i++) {
for (int j = 0; j < num_edges; j++) {
int u = edges[j].src;
int v = edges[j].dest;
int weight = edges[j].weight;
if (distance[u] != INF && distance[u] + weight < distance[v]) {
distance[v] = distance[u] + weight;
}
}
}
// Check for negative-weight cycles
for (int j = 0; j < num_edges; j++) {
int u = edges[j].src;
int v = edges[j].dest;
int weight = edges[j].weight;
if (distance[u] != INF && distance[u] + weight < distance[v]) {
cout << "Graph contains negative weight cycle." << endl;
return;
}
}
// Print distances from the source vertex
cout << "Vertex Distance from Source" << endl;
for (int i = 0; i < num_vertices; i++) {
cout << i << " \t\t " << (distance[i] == INF ? "INF" : to_string(distance[i])) << endl;
}
}
};
int main() {
int num_vertices = 5;
int num_edges = 8;
BellmanFord graph(num_vertices, num_edges);
graph.add_edge(0, 0, 1, -1);
graph.add_edge(1, 0, 2, 4);
graph.add_edge(2, 1, 2, 3);
graph.add_edge(3, 1, 3, 2);
graph.add_edge(4, 1, 4, 2);
graph.add_edge(5, 3, 2, 5);
graph.add_edge(6, 3, 1, 1);
graph.add_edge(7, 4, 3, -3);
graph.find_shortest_path(0);
return 0;
}
Output:
3. Find All Bridges in a Graph
This program finds all bridges in an undirected graph using Tarjan’s algorithm. It uses an adjacency matrix to represent the graph. During DFS traversal, each node is assigned a discovery time and a low value. A bridge is identified if the low value of a child node is greater than the discovery time of its parent. The dfs function explores edges and updates low values to detect bridges.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX_NODES 1000 // Maximum number of nodes in the graph
class TarjansBridges {
private:
int time_stamp;
int adj_matrix[MAX_NODES][MAX_NODES]; // Adjacency matrix for the graph
bool visited[MAX_NODES]; // Visited nodes
int discovery_time[MAX_NODES]; // Discovery time of each node
int low[MAX_NODES]; // Lowest discovery time reachable
int parent[MAX_NODES]; // Parent of each node
int num_nodes;
// Recursive function to find bridges
void dfs(int u) {
visited[u] = true;
discovery_time[u] = low[u] = ++time_stamp;
for (int v = 0; v < num_nodes; v++) {
if (adj_matrix[u][v] == 0) continue; // Skip if no edge exists
if (!visited[v]) {
parent[v] = u;
dfs(v);
// Update low value of u for child v
low[u] = min(low[u], low[v]);
// Bridge condition
if (low[v] > discovery_time[u]) {
cout << "Bridge: " << u << " - " << v << endl;
}
} else if (v != parent[u]) {
// Update low value for back edge
low[u] = min(low[u], discovery_time[v]);
}
}
}
public:
TarjansBridges(int n) {
num_nodes = n;
memset(adj_matrix, 0, sizeof(adj_matrix));
memset(visited, false, sizeof(visited));
memset(discovery_time, -1, sizeof(discovery_time));
memset(low, -1, sizeof(low));
memset(parent, -1, sizeof(parent));
time_stamp = 0;
}
// Function to add an edge between two nodes
void add_edge(int u, int v) {
adj_matrix[u][v] = 1;
adj_matrix[v][u] = 1;
}
// Function to find all bridges in the graph
void find_bridges() {
for (int i = 0; i < num_nodes; i++) {
if (!visited[i]) {
dfs(i);
}
}
}
};
int main() {
int num_nodes = 5;
TarjansBridges graph(num_nodes);
graph.add_edge(0, 1);
graph.add_edge(0, 2);
graph.add_edge(1, 2);
graph.add_edge(1, 3);
graph.add_edge(3, 4);
cout << "Bridges in the graph are:" << endl;
graph.find_bridges();
return 0;
}
Output:
4. Find Articulation Points in a Graph
This program identifies articulation points using Tarjan's algorithm. It calculates discovery and low times for each node during a DFS traversal. Articulation points are determined based on conditions for root nodes and non-root nodes. Input edges are converted to 0-based indexing for easier matrix manipulation. The result outputs all articulation points or "None" if no articulation points exist.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000
class Graph {
private:
int adj_matrix[MAX][MAX]; // Adjacency matrix to represent the graph
int num_nodes; // Number of nodes in the graph
int visited[MAX]; // Visited array
int discovery[MAX]; // Discovery time of each node
int low[MAX]; // Lowest discovery time reachable
int parent[MAX]; // Parent of each node in the DFS tree
bool articulation_point[MAX]; // Boolean array to store articulation points
int timer; // Timer for discovery time
void dfs(int node) {
visited[node] = true;
discovery[node] = low[node] = ++timer;
int children = 0;
for (int neighbor = 0; neighbor < num_nodes; neighbor++) {
if (adj_matrix[node][neighbor]) {
if (!visited[neighbor]) {
children++;
parent[neighbor] = node;
dfs(neighbor);
// Update the low value of the current node
low[node] = min(low[node], low[neighbor]);
// Check if the current node is an articulation point
if (parent[node] == -1 && children > 1) {
articulation_point[node] = true;
}
if (parent[node] != -1 && low[neighbor] >= discovery[node]) {
articulation_point[node] = true;
}
} else if (neighbor != parent[node]) {
// Update the low value if the neighbor is already visited
low[node] = min(low[node], discovery[neighbor]);
}
}
}
}
public:
Graph(int nodes) {
num_nodes = nodes;
memset(adj_matrix, 0, sizeof(adj_matrix));
memset(visited, 0, sizeof(visited));
memset(discovery, -1, sizeof(discovery));
memset(low, -1, sizeof(low));
memset(parent, -1, sizeof(parent));
memset(articulation_point, false, sizeof(articulation_point));
timer = 0;
}
void add_edge(int u, int v) {
adj_matrix[u][v] = 1;
adj_matrix[v][u] = 1;
}
void find_articulation_points() {
for (int i = 0; i < num_nodes; i++) {
if (!visited[i]) {
dfs(i);
}
}
cout << "Articulation Points: ";
bool found = false;
for (int i = 0; i < num_nodes; i++) {
if (articulation_point[i]) {
cout << i << " ";
found = true;
}
}
if (!found) {
cout << "None";
}
cout << endl;
}
};
int main() {
int nodes, edges;
cout << "Enter number of nodes and edges: ";
cin >> nodes >> edges;
Graph graph(nodes);
cout << "Enter edges (u v):" << endl;
for (int i = 0; i < edges; i++) {
int u, v;
cin >> u >> v;
u--; // Convert to 0-based index
v--;
graph.add_edge(u, v);
}
graph.find_articulation_points();
return 0;
}
Output:
5. Strongly Connected Components (SCC)
This program finds all strongly connected components (SCCs) in a directed graph using Kosaraju's algorithm. It creates an adjacency matrix for the graph and its transpose. First, a DFS is performed on the original graph to calculate finish times of nodes. Then the graph is transposed, and DFS is performed in the order of decreasing finish times to find SCCs. Each SCC is printed as a group of nodes.
Code:
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
#define MAX 1000
class Kosaraju {
private:
int num_vertices;
int graph[MAX][MAX];
int reverse_graph[MAX][MAX];
bool visited[MAX];
// Helper function to perform DFS on the original graph
void dfs_original(int node, stack<int>& finish_stack) {
visited[node] = true;
for (int i = 0; i < num_vertices; i++) {
if (graph[node][i] && !visited[i]) {
dfs_original(i, finish_stack);
}
}
finish_stack.push(node);
}
// Helper function to perform DFS on the transposed graph
void dfs_transpose(int node) {
cout << node << " ";
visited[node] = true;
for (int i = 0; i < num_vertices; i++) {
if (reverse_graph[node][i] && !visited[i]) {
dfs_transpose(i);
}
}
}
public:
Kosaraju(int vertices) {
num_vertices = vertices;
memset(graph, 0, sizeof(graph));
memset(reverse_graph, 0, sizeof(reverse_graph));
memset(visited, false, sizeof(visited));
}
// Add a directed edge from 'u' to 'v'
void add_edge(int u, int v) {
graph[u][v] = 1;
}
// Transpose the graph
void transpose_graph() {
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
reverse_graph[j][i] = graph[i][j];
}
}
}
// Find and print all SCCs
void find_scc() {
stack<int> finish_stack;
// Step 1: Perform DFS on the original graph and store finish times
memset(visited, false, sizeof(visited));
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {
dfs_original(i, finish_stack);
}
}
// Step 2: Transpose the graph
transpose_graph();
// Step 3: Perform DFS on the transposed graph in the order of finish times
memset(visited, false, sizeof(visited));
cout << "Strongly Connected Components are:" << endl;
while (!finish_stack.empty()) {
int node = finish_stack.top();
finish_stack.pop();
if (!visited[node]) {
dfs_transpose(node);
cout << endl;
}
}
}
};
int main() {
int vertices, edges;
cout << "Enter the number of vertices: ";
cin >> vertices;
cout << "Enter the number of edges: ";
cin >> edges;
Kosaraju kosaraju(vertices);
cout << "Enter the edges (u v):" << endl;
for (int i = 0; i < edges; i++) {
int u, v;
cin >> u >> v;
kosaraju.add_edge(u, v);
}
kosaraju.find_scc();
return 0;
}
Output:
Day 31 emphasized the power of advanced graph algorithms in solving intricate problems involving network optimization and connectivity. From shortest paths in DAGs to identifying critical components with Tarjan’s and Kosaraju’s algorithms, these challenges underscored the importance of understanding graph theory for tackling real-world computational tasks efficiently. 🚀