r1411

Прим мин. остов

Jun 16th, 2021
686
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 u[100];         //Помечаем тут вершины, входящие в U
  8.  
  9.  
  10. void main() {
  11.     setlocale(LC_ALL, "Russian");
  12.  
  13.     int n;
  14.     cout << "Кол-во вершин: ";
  15.     cin >> n;
  16.  
  17.     for (int i = 1; i <= n; i++)
  18.         for (int j = 1; j <= n; j++)
  19.             a[i][j] = 1000;
  20.  
  21.     int v1, v2, c;
  22.     cin >> v1 >> v2 >> c;
  23.     while (v1 != 0 && v2 != 0) {
  24.         a[v1][v2] = c;
  25.         a[v2][v1] = c;
  26.         cin >> v1 >> v2 >> c;
  27.     }
  28.  
  29.     //-------------------------------
  30.  
  31.     for (int i = 2; i <= n; i++)
  32.         u[i] = 0;
  33.     u[1] = 1;   // В начале алгоритма вершина 1 уже принадлежит U.
  34.  
  35.     int w1, w2, min;
  36.     do {
  37.         min = 1000;
  38.         for (int i = 1; i <= n; i++) {
  39.             for (int j = 1; j <= n; j++) {
  40.                 if (u[i] == 1 && u[j] == 0 && a[i][j] < min) {
  41.  
  42.                     min = a[i][j];
  43.                     w1 = i; w2 = j;
  44.                 }
  45.             }
  46.         }
  47.  
  48.         if (min < 1000) {
  49.             cout << "Добавляем в дерево ребро " << w1 << "-" << w2 << " стоимости " << min << endl;
  50.             u[w2] = 1;
  51.             t[ti][0] = w1;
  52.             t[ti][1] = w2;
  53.             ti += 1;
  54.         }
  55.     } while (min < 1000);
  56.  
  57.     for (int i = 0; i < ti; i++) {
  58.         cout << "Ребро " << (i + 1) << ": " << t[i][0] << "-" << t[i][1] << endl;
  59.     }
  60. }
RAW Paste Data