优先队列+prim（待完善）

我会带着你远行 2022-02-26 03:38 253阅读 0赞

#include <iostream>
    using namespace std;
    
    #define max 999;
    void prim(int verge[9][9],int heapsize);
    int extractmin(int V[],int &heapsize);
    void heapify(int V[],int k,int heapsize);
    void buildheap(int V[],int heapsize);
    void main()
    {
    	int verge[9][9]={
       {999,4,999,999,999,999,999,8,999},{4,999,8,999,999,999,999,11,999},{999,8,999,7,999,4,999,999,2},{999,999,7,999,9,14,999,999,999},
    	{999,999,999,9,999,1999,999,999,999},{999,999,4,14,1999,999,2,999,999},{999,999,999,999,999,2,999,1999,6},{8,11,999,999,999,999,1,999,7},{999,999,2,999,999,999,6,7,999}};
    	prim(verge,8);
    }
    void prim(int verge[9][9],int heapsize)
    {
    	int T[9],V[9];
    	for(int i=0;i<9;i++)
    	{
    		T[i]=0;
    		V[i]=max;
    	}
    	V[0]=0;
    	for(int i=0;i<9;i++)
    	{
    		int u=extractmin(V,heapsize);
    		cout<<u;
    		T[u]=1;
    
    		for(int i=0;i<9;i++)
    		{
    			if(T[i]==0&&verge[u][i]<V[i])
    				V[i]=verge[u][i];
    		}
    
    	}
    
    }
    /*void main()
    {
    	int i=0,k=0,V[9]={8,1,9,13,2,4,6,5,22};
    	int heapsize=8;
    	while(i<9)
    	{
    		k=extractmin(V,heapsize);
    		i++;
    		cout<<k;
    	}
    }*/
    int extractmin(int V[],int &heapsize)
    {
    	buildheap(V,heapsize);
    	int min=V[0];
    	swap(V[heapsize],V[0]);
    	heapsize=heapsize-1;
    	heapify(V,0,heapsize);
    	return min;
    }
    void buildheap(int V[],int heapsize)
    {
    	for(int i=heapsize/2;i>=0;i--)
    	{
    		heapify(V,i,heapsize);
    	}
    }
    void heapify(int V[],int k,int heapsize)
    {
    	int l=2*k+1;
    	int r=2*k+2;
    	int least=0;
    	if(l<=heapsize&&V[l]<V[least])
    	least=l;
    	else least=k;
    	if(r<=heapsize&&V[r]<V[least])
        least=r;
    	if(least!=k)
    	{
    		swap(V[k],V[least]);
    		heapify(V,least,heapsize);
    	}
    		
    }