fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #define V 11        // кількість вершин у графі
  4. #define INF 999999  // "нескінченність"
  5.  
  6. int minKey(int key[], int mstSet[]) {
  7.     int min = INF, min_index;
  8.  
  9.     for (int v = 0; v < V; v++)
  10.         if (mstSet[v] == 0 && key[v] < min)
  11.             min = key[v], min_index = v;
  12.  
  13.     return min_index;
  14. }
  15.  
  16. void printMST(int parent[], int graph[V][V]) {
  17.     int total = 0;
  18.  
  19.     printf("\nОстовне дерево (метод Прима):\n");
  20.     printf("Ребро    Вага\n");
  21.  
  22.     for (int i = 1; i < V; i++) {
  23.         printf("%d - %d    %d\n", parent[i] + 1, i + 1, graph[i][parent[i]]);
  24.         total += graph[i][parent[i]];
  25.     }
  26.  
  27.     printf("\nМінімальна вага остового дерева = %d\n", total);
  28. }
  29.  
  30. void primMST(int graph[V][V]) {
  31.     int parent[V];   // масив результату
  32.     int key[V];      // мінімальна вага ребра для кожної вершини
  33.     int mstSet[V];   // чи входить вершина в МОД
  34.  
  35.     // ініціалізація
  36.     for (int i = 0; i < V; i++)
  37.         key[i] = INF, mstSet[i] = 0;
  38.  
  39.     key[0] = 0;        // починаємо з вершини 1
  40.     parent[0] = -1;    // корінь
  41.  
  42.     printf("ЕТАПИ РОБОТИ АЛГОРИТМУ ПРИМА:\n");
  43.  
  44.     for (int count = 0; count < V - 1; count++) {
  45.         int u = minKey(key, mstSet);
  46.         mstSet[u] = 1;
  47.  
  48.         printf("\nДодаємо вершину %d у дерево\n", u + 1);
  49.  
  50.         for (int v = 0; v < V; v++) {
  51.             if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
  52.                 parent[v] = u;
  53.                 key[v] = graph[u][v];
  54.  
  55.                 printf("Оновлено: ребро %d — %d (вага %d)\n",
  56.                        u + 1, v + 1, graph[u][v]);
  57.             }
  58.         }
  59.     }
  60.  
  61.     printMST(parent, graph);
  62. }
  63.  
  64. int main() {
  65.  
  66.     // Матриця суміжності для графа з твого фото
  67.     int graph[V][V] = {
  68.  
  69.         //1 2 3 4 5 6 7 8 9 10 11
  70.         {0,5,2,3,0,0,0,0,0,0,0},  // 1
  71.         {5,0,5,0,5,7,0,0,0,0,0},  // 2
  72.         {2,5,0,4,7,4,7,0,1,0,0},  // 3
  73.         {3,0,4,0,0,7,7,0,0,0,0},  // 4
  74.         {0,5,7,0,0,4,0,2,0,0,0},  // 5
  75.         {0,7,4,7,4,0,1,0,2,0,0},  // 6
  76.         {0,0,7,7,0,1,0,0,3,3,0},  // 7
  77.         {0,0,0,0,2,0,0,0,0,0,4},  // 8
  78.         {0,0,1,0,0,2,3,0,0,6,6},  // 9
  79.         {0,0,0,0,0,0,3,0,6,0,4},  // 10
  80.         {0,0,0,0,0,0,0,4,6,4,0}   // 11
  81.     };
  82.  
  83.     primMST(graph);
  84.  
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ЕТАПИ РОБОТИ АЛГОРИТМУ ПРИМА:

Додаємо вершину 1 у дерево
Оновлено: ребро 1 — 2 (вага 5)
Оновлено: ребро 1 — 3 (вага 2)
Оновлено: ребро 1 — 4 (вага 3)

Додаємо вершину 3 у дерево
Оновлено: ребро 3 — 5 (вага 7)
Оновлено: ребро 3 — 6 (вага 4)
Оновлено: ребро 3 — 7 (вага 7)
Оновлено: ребро 3 — 9 (вага 1)

Додаємо вершину 9 у дерево
Оновлено: ребро 9 — 6 (вага 2)
Оновлено: ребро 9 — 7 (вага 3)
Оновлено: ребро 9 — 10 (вага 6)
Оновлено: ребро 9 — 11 (вага 6)

Додаємо вершину 6 у дерево
Оновлено: ребро 6 — 5 (вага 4)
Оновлено: ребро 6 — 7 (вага 1)

Додаємо вершину 7 у дерево
Оновлено: ребро 7 — 10 (вага 3)

Додаємо вершину 4 у дерево

Додаємо вершину 10 у дерево
Оновлено: ребро 10 — 11 (вага 4)

Додаємо вершину 5 у дерево
Оновлено: ребро 5 — 8 (вага 2)

Додаємо вершину 8 у дерево

Додаємо вершину 11 у дерево

Остовне дерево (метод Прима):
Ребро    Вага
1 - 2    5
1 - 3    2
1 - 4    3
6 - 5    4
9 - 6    2
6 - 7    1
5 - 8    2
3 - 9    1
7 - 10    3
10 - 11    4

Мінімальна вага остового дерева = 27
https://ideone.com/4q6qog
language:
C (gcc 8.3)
created:
1 day 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!