ในปัญหานี้ เราได้รับอาร์เรย์ arr ของตัวเลข N โดยที่ arr[i] แทนโหนด (i+1)th นอกจากนี้ยังมีขอบคู่ M โดยที่ u และ v เป็นตัวแทนของโหนดที่เชื่อมต่อโดยขอบ งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมขององค์ประกอบขั้นต่ำในองค์ประกอบที่เชื่อมต่อทั้งหมดของกราฟที่ไม่มีทิศทาง หากโหนดไม่มีการเชื่อมต่อกับโหนดอื่น ให้นับเป็นส่วนประกอบที่มีโหนดเดียว
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
arr[] = {2, 7, 5, 1, 2} m = 2
1 2
4 5 ผลผลิต
8
คำอธิบาย
ด้านล่างเป็นกราฟที่แสดงด้านบน -
เรามีโหนดที่เชื่อมต่ออยู่สองโหนดและโหนดเดียว
ดังนั้น มาดูส่วนประกอบที่เชื่อมต่อขั้นต่ำกัน
ต่ำสุด (node1 และ node2) =นาที (2, 7) =2
ต่ำสุด (node4 และ node5) =นาที (1, 3) =1
ต่ำสุด (node3) =ต่ำสุด (5) =5
ผลรวม =1 + 2 + 5 =8
เพื่อแก้ปัญหานี้ เราจะค้นหาโหนดที่เชื่อมต่อทั้งหมดของกราฟที่ไม่มีทิศทางโดยใช้เทคนิคการข้ามผ่าน (BFS หรือ DFS) จากนั้นสร้างอาร์เรย์ที่เข้าชมสำหรับโหนดทั้งหมดที่เข้าชมโดยที่ไม่มีการเข้าชมซ้ำ ในการเยี่ยมชมโหนดที่เชื่อมต่อที่เชื่อมต่อโดยตรงหรือโดยอ้อม เราจะค้นหาการเชื่อมต่อขั้นต่ำทั้งหมด และเพิ่มค่าต่ำสุดของตัวแปร thesum หลังจากที่เราไปเยี่ยมโหนดทั้งหมดแล้ว เราจะพิมพ์ผลรวมออกมา
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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
