unit3.cpp

数据结构作业代码。 最小生成树 Prim实现。 win32 Console界面。

//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Tedge
{
  int x,y,cost;
} edg[10000],           //triplicate table of edges;
  TT[100];              //edges of the mst

int n=100,              //range of the vertexs;
    arr[100][100],      //adjacency matrix of edges;
    status[100],        //status of the vertex i if it's in the U of the Mst;
    t,                  //range of the TT;
    s                   //range of the edg (TriplicateTb)
    ;

void Input()
{
  int i,j;
  for (i=0;i<n;i++)
    for (j=0;j<n;j++)
      scanf("%d",&arr[i][j]);
} //read data formed in adjacency matrix;

int cmp(const void *a,const void *b)
{
  Tedge p1=*(Tedge *)a,p2=*(Tedge *)b;
  if (p1.cost<p2.cost)
    return -1;
  if (p1.cost>p2.cost)
    return 1;
  return 0;
} //comparition of the Qsort in Stdlib.h
  //sort in Cost
  
void Mst_Prim()           //Prim Mst
{
  status[edg[0].x]=1;     //initialization
  status[edg[0].y]=1;     //choose the minimal-cost-edge

  t=0;
  TT[t++]=edg[0];         //record it;

  int i,j;
  for (i=2;i<n;i++)       //search for the left n-2 Vs;
  {
    j=1;
    while (j<=s)
    {
      if (status[edg[j].x]+status[edg[j].y]==1)
      {
        TT[t++]=edg[j];
        status[edg[j].x]=0;
        status[edg[j].y]=0;
        break;            //find it record it and break for next one
      }
      j++;
    }
  }
}

int main(int argc, char* argv[])
{
  int i,j;

  Input();
  s=0;

  for (i=0;i<n;i++)
    for (j=i+1;j<n;j++)
      if (arr[i][j])
      {
        edg[s].x=i;
        edg[s].y=j;
        edg[s++].cost=arr[i][j];
      }
  //transform from adjacency matrix to triplicate table

  qsort(edg,s,sizeof(edg),cmp);
  //sort in Cost...

  memset(status,0,sizeof(status));
  //initialization

  Mst_Prim;

  //Output();
  //in any form you want...

  return 0;
}
//---------------------------------------------------------------------------