欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標題: C語言程序 克魯斯卡爾算法求最小生成樹 [打印本頁]
作者: Anza    時間: 2024-1-15 21:23
標題: C語言程序 克魯斯卡爾算法求最小生成樹
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<stdio.h>

  4. typedef struct Edge
  5. {
  6.         int v1, v2;
  7.         int wight;
  8. }Edge;

  10. int main()
  11. {
  12.         int n, m;//結點數和邊數
  13.         int i, j, k = 0;
  14.         int count = 0;
  15.         Edge edge[100];//邊集
  16.         int vest[30];//判斷是否成環的編號數組
  17.         scanf("%d %d", &n, &m);
  18.         for (i = 0; i < m; i++)
  19.         {
  20.                 scanf("%d %d %d", &edge[i].v1, &edge[i].v2, &edge[i].wight);
  21.                 if(edge[i].v1 > edge[i].v2)
  22.                 {
  23.                         int t = edge[i].v1;
  24.                         edge[i].v1 = edge[i].v2;
  25.                         edge[i].v2 = t;
  26.                 }
  27.         }
  28.         for (i = 1; i <= n; i++)//初始化編號數組
  29.                 vest[i] = i;
  30.         for (i = 0; i < m - 1; i++)//排序
  31.         {
  32.                 for (j = 0; j < m - i - 1; j++)
  33.                 {
  34.                         if (edge[j].wight > edge[j + 1].wight)
  35.                         {
  36.                                 Edge t = edge[j];
  37.                                 edge[j] = edge[j + 1];
  38.                                 edge[j + 1] = t;
  39.                         }
  40.                 }
  41.         }
  42.         for (i = 0; i < m && count < n - 1; i++)
  43.         {
  44.                 if (vest[edge[i].v1] != vest[edge[i].v2])//說明不構成環,打印
  45.                 {
  46.                         printf("%d %d %d\n", edge[i].v1, edge[i].v2, edge[i].wight);
  47.                         count++;
  48.                         int flag1 = vest[edge[i].v1];
  49.                         int flag2 = vest[edge[i].v2];
  50.                         for (j = 1; j <= n; j++)
  51.                         {
  52.                                 if (vest[j] == flag2)//把全部編號為flag2的結點改為flag1
  53.                                         vest[j] = flag1;
  54.                         }
  55.                 }
  56.         }
  57.         return 0;
  58. }
復制代碼





歡迎光臨 (http://www.raoushi.com/bbs/) Powered by Discuz! X3.1