C语言（关于图最小生成树方法）

Question

五、实验目的：
本实验通过实现最小生成树的算法，使学生理解图的数据结构存储表示，并能理解最小生成树Kruskal 算法。通过练习，加强对算法的理解，提高编程能力。
六、实验内容：
（1）假定每对顶点表示图的一条边，每条边对应一个权值；
（2）输入每条边的顶点和权值；
（3）输入每条边后，计算出最小生成树；
（4）打印最小生成树边的顶点及权值。

Answer 1

/*
邻接矩阵存储图
测试数据
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
*/

#include <stdio.h>
#include <limits.h>
#define N 100

int p[N], key[N], tb[N][N];

void prim(int v, int n)
{
   int i, j;
   int min;

   for (i = 1; i <= n; i++)
   {
       p[i] = v;
       key[i] = tb[v][i];
   }
   key[v] = 0;
   for (i = 2; i <= n; i++)
   {
       min = INT_MAX;
       for (j = 1; j <= n; j++)
           if (key[j] > 0 && key[j] < min)
           {
                v = j;
                min = key[j];
           }
       printf("%d%d ", p[v], v);
       key[v] = 0;
       for (j = 1; j <= n; j++)
           if (tb[v][j] < key[j])
              p[j] = v, key[j] = tb[v][j];
   }
}

int main()
{
   int n, m;
   int i, j;
   int u, v, w;
   while (scanf("%d%d", &n, &m))
   {
       for(i = 1; i <= n; i++)
       {
           for (j = 1; j <= n; j++)
               tb[i][j] = INT_MAX;
       }

       while (m--)
       {
           scanf("%d%d%d", &u, &v, &w);
           tb[u][v] = tb[v][u] = w;
       }
       prim(1, n);
       printf("\n");
   }
   return 0;
}