r1411

Мин. остов Крускал

Jun 16th, 2021
854
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int a[100][100];    //Матр. смеж.
  5. int t[100][2];      //Итоговое дерево
  6. int ti = 0;         //Сколько ребер в дереве уже есть.
  7. int sv[100];        //Отмечаем, какой компоненте связности принадлежат вершины
  8. int w1, w2, n;
  9.  
  10. // Записывает в w1 и w2 ребро наим. стоимости, соединяющее разные компоненты связности.
  11. void minimum() {
  12.     int min = 1000;
  13.     w1 = -1;
  14.     w2 = -1;
  15.     for (int i = 1; i <= n; i++) {
  16.         for (int j = 1; j <= n; j++) {
  17.             if (a[i][j] < min && sv[i] != sv[j]) {
  18.                 min = a[i][j];
  19.                 w1 = i;
  20.                 w2 = j;
  21.             }
  22.         }
  23.     }
  24.  
  25.     if (min < 1000)
  26.         a[w1][w2] = 1000; // Удаляем ребро, чтобы больше к нему не возвращаться.
  27. }
  28.  
  29. void main() {
  30.     setlocale(LC_ALL, "Russian");
  31.  
  32.     cout << "Кол-во вершин: ";
  33.     cin >> n;
  34.  
  35.     for (int i = 1; i <= n; i++)
  36.         for (int j = 1; j <= n; j++)
  37.             a[i][j] = 1000;
  38.  
  39.     int v1, v2, c;
  40.     cin >> v1 >> v2 >> c;
  41.     while (v1 != 0 && v2 != 0) {
  42.         a[v1][v2] = c;
  43.         a[v2][v1] = c;
  44.         cin >> v1 >> v2 >> c;
  45.     }
  46.  
  47.     //-------------------------------
  48.  
  49.     for (int i = 1; i <= n; i++)
  50.         sv[i] = i;
  51.  
  52.     do {
  53.         minimum();
  54.         if (w1 > 0) {
  55.             t[ti][0] = w1;
  56.             t[ti][1] = w2;
  57.             ti += 1;
  58.             //Объединяем компоненты связности
  59.             int temp = sv[w2];
  60.             for (int i = 1; i <= n; i++)
  61.                 if (sv[i] == temp)
  62.                     sv[i] = sv[w1];
  63.         }
  64.     } while (w1 > 0);
  65.  
  66.  
  67.     for (int i = 0; i < ti; i++) {
  68.         cout << "Ребро " << (i + 1) << ": " << t[i][0] << "-" << t[i][1] << endl;
  69.     }
  70. }
RAW Paste Data