fork download
copy 
  1. // Nguyễn Trọng Khởi _ B22DCCN471
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <queue>
  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 dest, weight;
  12. };
  13.  
  14. // Định nghĩa cấu trúc biểu diễn một đồ thị
  15. class Graph {
  16. private:
  17.     int V; // Số đỉnh
  18.     vector<vector<Edge>> adjList; // Danh sách kề của đồ thị
  19.  
  20. public:
  21.     // Constructor
  22.     Graph(int V) {
  23.         this->V = V;
  24.         adjList.resize(V);
  25.     }
  26.  
  27.     // Thêm một cạnh vào đồ thị (với trọng số)
  28.     void addEdge(int src, int dest, int weight) {
  29.         Edge edge = {dest, weight};
  30.         adjList[src].push_back(edge);
  31.         // Với đồ thị vô hướng, hãy thêm cạnh ngược lại
  32.         edge.dest = src;
  33.         adjList[dest].push_back(edge);
  34.     }
  35.  
  36.     // Thuật toán Prim để tìm cây bao trùm nhỏ nhất
  37.     void PrimMST() {
  38.         // Đánh dấu các đỉnh đã được thăm
  39.         vector<bool> visited(V, false);
  40.         // Priority queue để chọn cạnh có trọng số nhỏ nhất
  41.         priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  42.  
  43.         // Bắt đầu từ đỉnh 0
  44.         int src = 0;
  45.         pq.push({0, src}); // Cạnh với trọng số 0 và đỉnh xuất phát src
  46.  
  47.         while (!pq.empty()) {
  48.             int u = pq.top().second; // Lấy đỉnh với trọng số nhỏ nhất
  49.             pq.pop();
  50.  
  51.             // Đánh dấu đỉnh hiện tại là đã thăm
  52.             visited[u] = true;
  53.  
  54.             // In kết quả, lưu ý rằng đỉnh 0 không có đỉnh cha
  55.             if (u != src)
  56.                 cout << "Canh: " << u << " - " << pq.top().second << " Trong so: " << pq.top().first << endl;
  57.  
  58.             // Duyệt qua tất cả các đỉnh kề của đỉnh hiện tại
  59.             for (auto edge : adjList[u]) {
  60.                 int v = edge.dest;
  61.                 int weight = edge.weight;
  62.  
  63.                 // Nếu đỉnh v chưa được thăm và có trọng số nhỏ hơn
  64.                 if (!visited[v])
  65.                     pq.push({weight, v});
  66.             }
  67.         }
  68.     }
  69. };
  70.  
  71. int main() {
  72.     int V = 5; // Số đỉnh
  73.  
  74.     // Khởi tạo một đồ thị với 5 đỉnh
  75.     Graph graph(V);
  76.  
  77.     // Thêm các cạnh vào đồ thị
  78.     graph.addEdge(0, 1, 2);
  79.     graph.addEdge(0, 3, 6);
  80.     graph.addEdge(1, 2, 3);
  81.     graph.addEdge(1, 3, 8);
  82.     graph.addEdge(1, 4, 5);
  83.     graph.addEdge(2, 4, 7);
  84.     graph.addEdge(3, 4, 9);
  85.  
  86.     // Tìm cây bao trùm nhỏ nhất và in kết quả
  87.     graph.PrimMST();
  88.  
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Canh: 1 - 3 Trong so: 6
Canh: 2 - 4 Trong so: 5
Canh: 4 - 3 Trong so: 6
Canh: 3 - 4 Trong so: 7
Canh: 4 - 3 Trong so: 8
Canh: 3 - 3 Trong so: 9
Canh: 3 - 3 Trong so: 9
https://ideone.com/4UFly9
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!