👋 Hello everyone! Welcome to another exciting blog post, where I, your friendly guide, will delve into the world of algorithms and data structures. In today's session, I'm going to introduce you to the fascinating world of graph algorithms, specifically, the BFS (Breadth-First Search) and Kruskal's algorithms. We'll also touch upon detecting cycles in Minimum Spanning Trees (MST), the Union-Find algorithm, and a brief glimpse of Prim's algorithm. So, fasten your seatbelts and let's embark on this learning journey together!
Let's Begin with BFS - The Pathfinder 🌍
BFS is like the Sherlock Holmes of graph algorithms. It explores a graph layer by layer, starting from a chosen source vertex. The technique here is simple: I maintain a queue and keep track of visited vertices to ensure that I don't revisit them. This way, I can find the shortest path from the source to any other vertex in the graph.
Example:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void BFS(vector<vector<int>>& graph, int source) {
vector<bool> visited(graph.size(), false);
queue<int> q;
visited[source] = true;
q.push(source);
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current << " ";
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
vector<vector<int>> graph = {{1, 2}, {0, 3, 4}, {0, 4}, {1, 5}, {1, 2, 5}, {3, 4}};
int source = 0;
cout << "BFS traversal starting from vertex " << source << ": ";
BFS(graph, source);
return 0;
}
Now, Let's Dive into Kruskal's Algorithm 🌲
Kruskal's algorithm is like a gardener pruning a tree. It helps us find the Minimum Spanning Tree (MST) of a graph. The technique involves sorting the edges by weight and adding them to the MST while ensuring no cycles are formed.
Example:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int u, v, weight;
};
bool compare(Edge a, Edge b) {
return a.weight < b.weight;
}
int find(int parent[], int vertex) {
if (parent[vertex] == -1)
return vertex;
return find(parent, parent[vertex]);
}
void unionVertices(int parent[], int u, int v) {
parent[u] = v;
}
void kruskalMST(vector<Edge>& edges, int V) {
vector<Edge> result;
sort(edges.begin(), edges.end(), compare);
int parent[V];
fill(parent, parent + V, -1);
for (Edge edge : edges) {
int u = find(parent, edge.u);
int v = find(parent, edge.v);
if (u != v) {
result.push_back(edge);
unionVertices(parent, u, v);
}
}
cout << "Edges in the Minimum Spanning Tree:\n";
for (Edge edge : result) {
cout << edge.u << " - " << edge.v << " (Weight: " << edge.weight << ")\n";
}
}
int main() {
int V = 4;
vector<Edge> edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};
kruskalMST(edges, V);
return 0;
}
Detecting Cycles in MST and the Union-Find Algorithm 🔄
Detecting cycles in a Minimum Spanning Tree is crucial, as any cycle would mean that the tree is no longer minimal. In our Kruskal's algorithm example, we ensured that no cycles were formed by checking if the vertices at both ends of an edge were part of the same disjoint set. If they were, adding the edge would create a cycle, so we skipped it.The Union-Find algorithm, also known as Disjoint-Set data structure, plays a vital role in this. It helps us keep track of which vertices are connected and detect cycles efficiently.
An alternative approach for cycle detection in an undirected graph is to use the Depth-First Search (DFS) algorithm. By carefully tracking back edges during traversal, we can identify cycles. Here's how you can do it:
#include <iostream>
#include <vector>
using namespace std;
bool hasCycle(vector<vector<int>>& graph, int current, int parent, vector<bool>& visited) {
visited[current] = true;
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
if (hasCycle(graph, neighbor, current, visited)) {
return true;
}
} else if (neighbor != parent) {
return true;
}
}
return false;
}
bool isCyclic(vector<vector<int>>& graph) {
int V = graph.size();
vector<bool> visited(V, false);
for (int i = 0; i < V; i++) {
if (!visited[i] && hasCycle(graph, i, -1, visited)) {
return true;
}
}
return false;
}
Prim's Algorithm 🌳
Just like Kruskal's algorithm, Prim's algorithm helps you find the Minimum Spanning Tree of a graph. Instead of focusing on edges, Prim's algorithm selects vertices and builds the tree incrementally. It starts with an arbitrary vertex and adds the nearest unvisited vertex to the MST in each step.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int findMinKey(vector<int>& key, vector<bool>& mstSet) {
int minKey = INT_MAX;
int minIndex;
for (int i = 0; i < key.size(); i++) {
if (!mstSet[i] && key[i] < minKey) {
minKey = key[i];
minIndex = i;
}
}
return minIndex;
}
void primMST(vector<vector<int>>& graph) {
int V = graph.size();
vector<int> parent(V, -1);
vector<int> key(V, INT_MAX);
vector<bool> mstSet(V, false);
key[0] = 0;
for (int count = 0; count < V - 1; count++) {
int u = findMinKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++) {
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
cout << "Edges in the Minimum Spanning Tree (Prim's algorithm):\n";
for (int i = 1; i < V; i++) {
cout << parent[i] << " - " << i << " (Weight: " << graph[i][parent[i]] << ")\n";
}
}
Wrapping it Up 🎉
We've covered quite a bit today, from BFS and Kruskal's algorithm to cycle detection and Prim's algorithm. I hope this session has been enlightening, and I encourage you to explore these concepts further and practice your coding skills.
Stay tuned for the next session, where we'll dive into more advanced topics and algorithms. Keep learning and keep coding! 🚀📚