ch6_3.c

本内容为清华大学严蔚敏版数据结构部分算法实现代码

#include <stdio.h>
#define SIZE 11
void main( )
{
  /* 变量声明及定义
  graph数组存放原始图，span数组存放生成树
  vertex代表结点个数(最多10)，choose数组代表结点的选取与否 */
  int graph[SIZE][SIZE], span[SIZE][SIZE], vertex, i, j;
  int edge, choose[SIZE], min, p, q;
  printf("How many vertex:(<=10) ");       /* 读入原始图 */
  scanf("%d", &vertex);
  for(i=1; i<=vertex; i++)
  {
    choose[i]=0;
    for(j=i+1; j<=vertex; j++)    /* 初始化，1表示读过，0表示未读过 */
    {
      span[i][j]=0;
      printf("Input the cost between vertex %d and vertex %d: ", i, j);
      scanf("%d", &graph[i][j]);
      graph[j][i]=graph[i][j];     /* 对称矩阵 */
    }
  }
  edge=0;                  /* 根据Prim算法来找出最小成本生成树 */ 
  choose[1]=1;
  while(edge < vertex)
  {
    min=999;
    for(i=1; i<=vertex; i++)
    {
      if(choose[i] == 0)
        continue;
      for(j=1; j<=vertex; j++)
      {
        if(i == j)
          continue;
        if(choose[j] == 1)
          continue;
        if(graph[i][j]<=min && graph[i][j]!=0)
        {
          min=graph[i][j];
          p=i;
          q=j;
        }
      }
    }
    choose[q]=1;
    edge++;
    span[p][q]=graph[p][q];
    span[q][p]=graph[p][q];
  }
  printf("The minimal cost spanning tree is as follows:\n");     /* 输出结果 */
  for(i=1; i<=vertex; i++)
  {
    for(j=i+1; j<=vertex; j++)
    {
      if(span[i][j] != 0)
      {
        printf("Between vertex %d and %d cost %d\n", i, j, span[i][j]);
      }
    }
  }
}