C++ में दिए गए सेट में मौजूद हर नोड से पहुंच योग्य सभी नोड्स खोजें

मान लीजिए हमारे पास एक अनडायरेक्टेड ग्राफ और वर्टेक्स का एक सेट है; हमें दिए गए सेट में मौजूद हर वर्टेक्स से सभी पहुंच योग्य नोड्स खोजने हैं।

यदि इनपुट ऐसा है:

तो आउटपुट होगा [1,2,3] और [4,5] क्योंकि ये दो कनेक्टेड कंपोनेंट्स हैं।

समाधान दृष्टिकोण

1. nodes := ग्राफ में नोड्स की संख्या।
2. आकार nodes+1 का एक visited ऐरे परिभाषित करें और 0 से भरें।
3. एक मैप m परिभाषित करें।
4. comp_sum := 0।
5. i := 0 से n-1 तक लूप करें:
   • u := arr[i]।
   • यदि visited[u] गलत है:
     • comp_sum बढ़ाएं।
     • m[visited[u]] := BFS ट्रैवर्सल ग्राफ g का नोड u से, comp_sum भी कैलकुलेट करें।
   • m[visited[u]] का ट्रैवर्सल प्रिंट करें।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Graph {
public:
    int nodes;
    list<int> *adj_list;
    Graph(int);
    void insert_edge(int, int);
    vector<int> BFS(int, int, int []);
};

Graph::Graph(int nodes) {
    this->nodes = nodes;
    adj_list = new list<int>[nodes + 1];
}

void Graph::insert_edge(int u, int v) {
    adj_list[u].push_back(v);
    adj_list[v].push_back(u);
}

vector<int> Graph::BFS(int comp_sum, int src, int visited[]) {
    queue<int> q;
    q.push(src);
    visited[src] = comp_sum;
    vector<int> reachableNodes;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        reachableNodes.push_back(u);
        for (auto itr = adj_list[u].begin(); itr != adj_list[u].end(); itr++) {
            if (!visited[*itr]) {
                visited[*itr] = comp_sum;
                q.push(*itr);
            }
        }
    }
    return reachableNodes;
}

void displayReachableNodes(int n, unordered_map<int, vector<int>> m) {
    vector<int> temp = m[n];
    for (int i = 0; i < temp.size(); i++)
        cout << temp[i] << " ";
    cout << endl;
}

void get_all_reachable(Graph g, int arr[], int n) {
    int nodes = g.nodes;
    int visited[nodes + 1];
    memset(visited, 0, sizeof(visited));
    unordered_map<int, vector<int>> m;
    int comp_sum = 0;
    for (int i = 0; i < n; i++) {
        int u = arr[i];
        if (!visited[u]) {
            comp_sum++;
            m[visited[u]] = g.BFS(comp_sum, u, visited);
        }
        cout << "Reachable Nodes from " << u << " are\n";
        displayReachableNodes(visited[u], m);
    }
}

int main() {
    int nodes = 5;
    Graph g(nodes);
    g.insert_edge(1, 2);
    g.insert_edge(2, 3);
    g.insert_edge(4, 5);
    int arr[] = {2, 4, 1};
    int n = sizeof(arr) / sizeof(int);
    get_all_reachable(g, arr, n);
    return 0;
}

इनपुट

g.insert_edge(1, 2); 
g.insert_edge(2, 3); 
g.insert_edge(4, 5);

आउटपुट

Reachable Nodes from 2 are: 2 1 3
Reachable Nodes from 4 are: 4 5
Reachable Nodes from 1 are: 2 1 3