सी++ में एक अप्रत्यक्ष ग्राफ के सभी जुड़े घटकों में न्यूनतम तत्वों का योग

इस समस्या में, हमें N संख्याओं का एक सरणी arr दिया जाता है जहाँ arr[i] (i+1)वें नोड का प्रतिनिधित्व करता है। इसके अलावा, किनारों के एम जोड़े हैं जहां यू और वी किनारे से जुड़े नोड का प्रतिनिधित्व करते हैं। हमारा काम एक अप्रत्यक्ष ग्राफ के सभी जुड़े घटकों में न्यूनतम तत्वों का योग खोजने के लिए एक कार्यक्रम बनाना है। यदि किसी नोड का किसी अन्य नोड से कोई जुड़ाव नहीं है, तो इसे एक नोड वाले घटक के रूप में गिनें।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

arr[] = {2, 7, 5, 1, 2} m = 2
1 2
4 5

आउटपुट

8

स्पष्टीकरण

नीचे दिया गया ग्राफ ऊपर दिखाया गया है -

हमारे पास दो कनेक्टेड नोड और एक सिंगल नोड है

तो, आइए सभी जुड़े हुए घटकों को कम से कम लें

न्यूनतम (नोड1 और नोड2) =मिनट (2, 7) =2

न्यूनतम (नोड4 और नोड5) =मिनट (1, 3) =1

न्यूनतम (नोड3) =मिनट (5) =5

योग =1 + 2 + 5 =8

इस समस्या को हल करने के लिए, हम किसी भी ट्रैवर्सल तकनीक (बीएफएस या डीएफएस) का उपयोग करके अप्रत्यक्ष ग्राफ के सभी जुड़े हुए नोड्स को ढूंढेंगे और फिर उन सभी नोड्स के लिए एक विज़िट किया गया सरणी बनाएं जो कि कोई डबल विज़िट नहीं है। प्रत्यक्ष या अप्रत्यक्ष रूप से जुड़े हुए कनेक्टेड नोड्स पर जाने पर, हम सभी कनेक्शनों में से न्यूनतम पाएंगे। और योग चर के इस न्यूनतम मान को जोड़ें। सभी नोड्स का दौरा करने के बाद, हम राशि प्रिंट करेंगे।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
vector<int> graph[N];
bool visited[N];
void dfs(int node, int arr[], int minimum){
   minimum = min(minimum, arr[node]);
   visited[node] = true;
   for (int i : graph[node]) {
      if (!visited[i])
         dfs(i, arr, minimum);
   }
}
void createEdge(int u, int v){
   graph[u - 1].push_back(v - 1);
   graph[v - 1].push_back(u - 1);
}
int minSum(int arr[], int n){
   int sum = 0;
   for (int i = 0; i < n; i++) {
      if (!visited[i]) {
         int minimum = arr[i];
         dfs(i, arr, minimum);
         sum += minimum;
      }
   }
   return sum;
}
int main(){
   int arr[] = {2, 7, 5, 1, 3};
   createEdge(1, 2);
   createEdge(4, 5);
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The sum of minimum elements in all connected components of an undirected graph is ";
   cout<<minSum(arr, n);
   return 0;
}

आउटपुट

The sum of minimum elements in all connected components of an undirected graph is 8