test10_3.cpp

该包是数据结构的实验软件,来源于合肥工业大学人工智能与数据挖掘实验室,用来实现数据结构.

//{ test10_3 }
#include"graph2.h"
#include"grary1.h"
const int MMax=999;

struct  MinEdgeType
	{
	int   v,w;
	};
typedef  MinEdgeType    MinEdgeArray[50];

set u;

   void   Init_MinEdges(datagraph& g,MinEdgeArray& MinEdges,int v0)
      {int  i;
       for (i=1;i<=nodes(g);i++)
	      if __________________ //{Blank 4}
	     { MinEdges[i].v=v0;
	       MinEdges[i].w=edge_weight(g,v0,i);
	       }
	     else
		MinEdges[i].w=MMax;
       }

    int   Get_MinEdge(datagraph& g,MinEdgeArray& MinEdges)
      {int  MMin,j,k;
	    MMin=MMax;
	    for (j=1;j<=nodes(g);j++)
	      if  _____________________________________ //{Blank 5}
		 { k=j;
		   MMin=MinEdges[j].w ;
		   }
	  int  Get_MinEdge=k;
	  return Get_MinEdge ;
      }

    void   change_MinEdges_with(datagraph& g,MinEdgeArray& MinEdges,int k)
     {int  j;
	 for (j=1;j<=nodes(g);j++)
	   if (!(u.contain(j) ) )
	     if ( have_edge(g,k,j) && (edge_weight(g,k,j)<MinEdges[j].w ) )
		{ MinEdges[j].w=edge_weight(g,k,j);
		  MinEdges[j].v=k;
		}
     }


   void   prim(datagraph& g,datagraph& gtree,int v0)
  {
    MinEdgeArray MinEdges;
   int    i,j,k;

     u.insert(v0);
     move_graph_to("graph",g,40,100);
     copy_all_vertex(g,gtree,300,0);
     disp_graph("gtree",gtree);
     Init_MinEdges(g,MinEdges,v0);
     for (i=1;i<=nodes(g)-1;i++)
	 {   Wait();
	     k=Get_MinEdge(g,MinEdges);
	     u.insert(k);
	    copy_edge(g, MinEdges[k].v,k,gtree);
	    display_edge(gtree, MinEdges[k].v,k);
	    change_MinEdges_with(g,MinEdges,k);
	 }
     }

     main()
     {datagraph g,gtree;
      load_graph_file(g,"graphs\\grpprim.grp");
      display_graph("graph",g);
      Clear_range(0,0,getmaxx(),getmaxy() );
       prim(g,gtree,1);
    }