fork download
copy 
  1. // Nguyễn Trọng Khởi _ B22DCCN471
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. // Định nghĩa cấu trúc biểu diễn một cạnh trong đồ thị
  10. struct Edge {
  11.     int src, dest, weight;
  12. };
  13.  
  14. // Định nghĩa cấu trúc biểu diễn một đồ thị
  15. struct Graph {
  16.     int V, E; // V: số đỉnh, E: số cạnh
  17.     vector<Edge> edges; // Danh sách các cạnh
  18.  
  19.     // Constructor
  20.     Graph(int V, int E) {
  21.         this->V = V;
  22.         this->E = E;
  23.     }
  24.  
  25.     // Thêm một cạnh vào đồ thị
  26.     void addEdge(int src, int dest, int weight) {
  27.         Edge edge = {src, dest, weight};
  28.         edges.push_back(edge);
  29.     }
  30.  
  31.     // Tìm phần tử cha của một đỉnh
  32.     int findParent(vector<int>& parent, int i) {
  33.         if (parent[i] == -1)
  34.             return i;
  35.         return findParent(parent, parent[i]);
  36.     }
  37.  
  38.     // Hợp nhất hai tập hợp con thành một tập hợp
  39.     void unionSets(vector<int>& parent, int x, int y) {
  40.         int xset = findParent(parent, x);
  41.         int yset = findParent(parent, y);
  42.         parent[xset] = yset;
  43.     }
  44.  
  45.     // Thuật toán Kruskal để tìm cây bao trùm nhỏ nhất
  46.     void KruskalMST() {
  47.         vector<Edge> result; // Lưu trữ các cạnh của cây bao trùm nhỏ nhất
  48.  
  49.         // Sắp xếp các cạnh theo trọng số tăng dần
  50.         sort(edges.begin(), edges.end(), [](Edge& a, Edge& b) {
  51.             return a.weight < b.weight;
  52.         });
  53.  
  54.         vector<int> parent(V, -1); // Mảng lưu trữ phần tử cha của các đỉnh
  55.  
  56.         int i = 0, e = 0;
  57.         while (e < V - 1 && i < E) {
  58.             Edge next_edge = edges[i++];
  59.             int x = findParent(parent, next_edge.src);
  60.             int y = findParent(parent, next_edge.dest);
  61.  
  62.             // Nếu thêm cạnh này không tạo ra chu trình
  63.             if (x != y) {
  64.                 result.push_back(next_edge);
  65.                 unionSets(parent, x, y);
  66.                 e++;
  67.             }
  68.         }
  69.  
  70.         // In kết quả
  71.         cout << "Cac canh cua cay bao trum nho nhat:\n";
  72.         for (i = 0; i < result.size(); i++)
  73.             cout << result[i].src << " -- " << result[i].dest << " : " << result[i].weight << endl;
  74.     }
  75. };
  76.  
  77. int main() {
  78.     int V = 4; // Số đỉnh
  79.     int E = 5; // Số cạnh
  80.  
  81.     // Khởi tạo một đồ thị với 4 đỉnh và 5 cạnh
  82.     Graph graph(V, E);
  83.  
  84.     // Thêm các cạnh vào đồ thị
  85.     graph.addEdge(0, 1, 10);
  86.     graph.addEdge(0, 2, 6);
  87.     graph.addEdge(0, 3, 5);
  88.     graph.addEdge(1, 3, 15);
  89.     graph.addEdge(2, 3, 4);
  90.  
  91.     // Tìm cây bao trùm nhỏ nhất và in kết quả
  92.     graph.KruskalMST();
  93.  
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Cac canh cua cay bao trum nho nhat:
2 -- 3 : 4
0 -- 3 : 5
0 -- 1 : 10
https://ideone.com/grSIAx
language:
C++ (gcc 8.3)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!