Joyshree

#25.Journey to DSA in C++

Joy Shree's photo
Joy Shree
·

4 min read

Exploring the Wonders of Graphs with C++:

Hey there, folks! 🌟

I, your friendly neighborhood enthusiast, am here to embark on a journey into the fascinating world of graphs using C++. 🚀 Today, we'll unravel the mysteries of graphs, discuss their importance, and dive into some core concepts such as Minimum Spanning Trees, Depth-First Search (DFS), and Breadth-First Search (BFS).

Let's start with the basics:

🌟 Understanding Graphs

Graphs are a fundamental data structure used in computer science and various applications. A graph is a collection of nodes (vertices) and edges connecting these nodes. They are used to model complex relationships and connections in various real-world scenarios. Whether it's modeling social networks, transportation networks, or even web pages, graphs are incredibly versatile.

🤔 Why Do We Need Graphs?

Graphs help us visualize and analyze complex relationships efficiently. They enable us to find the shortest path between two points, determine network connectivity, and even optimize transportation routes. In short, graphs are essential for solving a wide range of real-world problems.

🌲 Minimum Spanning Tree (MST)

A Minimum Spanning Tree is a subgraph of a graph that includes all the vertices while minimizing the total edge weight. MSTs are commonly used in network design, circuit wiring, and more. In upcoming posts, we'll delve into algorithms like Prim's and Kruskal's to find MSTs.

💡 Graph DFS in C++

Depth-First Search is a graph traversal technique where we explore as far as possible along a branch before backtracking. We'll provide you with a simple C++ program to demonstrate this concept, helping you understand how DFS works.

🚀 BFS Introduction in Graphs

Breadth-First Search, on the other hand, explores all the neighbors of a node before moving on to their children. We'll discuss its significance and show you how to implement it in C++.

👨‍💻 BFS in C++

With a code example, we'll walk you through how to perform a Breadth-First Search in C++. It's a powerful technique used in pathfinding, network analysis, and more.

🌐 Graph BFS & DFS for Disconnected Graphs

Disconnected graphs are those that have multiple components with no paths connecting them. We'll explore how BFS and DFS can be applied to disconnected graphs, demonstrating their versatility.

🤖 Example Programs in C++

Throughout this series, I'll provide you with working C++ programs that illustrate the concepts we discuss. These hands-on examples will help you grasp these techniques more effectively.

  1. Minimum Spanning Tree (Prim's Algorithm):
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Edge {
    int to, weight;
    Edge(int _to, int _weight) : to(_to), weight(_weight) {}
};

int primMST(vector<vector<Edge>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, 0});
    int minCost = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        int w = pq.top().first;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;
        minCost += w;

        for (Edge& e : graph[u]) {
            if (!visited[e.to]) {
                pq.push({e.weight, e.to});
            }
        }
    }

    return minCost;
}

int main() {
    int n = 4;
    vector<vector<Edge>> graph(n);

    // Adding edges
    graph[0].emplace_back(1, 2);
    graph[0].emplace_back(2, 3);
    graph[1].emplace_back(2, 1);
    graph[1].emplace_back(3, 4);

    int minCost = primMST(graph);
    cout << "Minimum Spanning Tree cost: " << minCost << endl;
    return 0;
}
  1. Graph Depth-First Search (DFS):
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";

    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    int n = 7; // Number of nodes
    graph.resize(n);
    visited.assign(n, false);

    // Adding edges
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(4);
    graph[2].push_back(5);
    graph[3].push_back(6);

    cout << "DFS traversal starting from node 0: ";
    dfs(0);

    return 0;
}
  1. Graph Breadth-First Search (BFS):
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";

        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    int n = 7; // Number of nodes
    graph.resize(n);
    visited.assign(n, false);

    // Adding edges
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(4);
    graph[2].push_back(5);
    graph[3].push_back(6);

    cout << "BFS traversal starting from node 0: ";
    bfs(0);

    return 0;
}

In conclusion, I encourage you to stay tuned for our upcoming sessions. We'll be diving deeper into these graph algorithms, providing you with more code examples, practical insights, and a deeper understanding of this fascinating field.

So, buckle up and join me on this exciting journey through the world of graphs in C++. 🌐🚀 It's going to be a fun and enlightening ride, and I promise to make it as simple and enjoyable as possible!

Until next time, happy coding! 🤓👨‍💻📚