zuoye4_prim.cpp

图论课程设计的左右

// zuoye5_prim.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#define max 999

//********************************************************
int ** creat_blank(int n)
{
	int **p;
	for(int i=0;i<n;i++)
		p=new int * [n];
	for(i=0;i<n;i++)
		p[i]=new int [n];
	return p;
}
//********************************************************
void prim(int **a,int v,int n)
{
    int dot[10],e[10];
	int i,j,k,min;
	for(i=0;i<n;i++)
	{
		dot[i]=v;
		e[i]=a[v][i];
	}
	for(i=0;i<n-1;i++)
	{
		min = max;
		for(j=0;j<n;j++)
			if(e[j]!=0 && e[j]<min)
			{
				min=e[j];
				k=j;
			}
		cout<<"边为："<<dot[k]+1<<","<<k+1<<",权为："<<min<<endl;
		e[k]=0;
		for(j=0;j<n;j++)
			if(e[j]!=0 && e[j]>a[k][j])
			{
				dot[j]=k;
				e[j]=a[k][j];
			}
	}
}
//********************************************************

int main(int argc, char* argv[])
{
	int **a,n,v;
	cout<<"请输入结点个数（小于等于10）：";
	cin>>n;
	a=creat_blank(n);
	cout<<"\n请输入开始结点：";
	cin>>v;
	cout<<"请输入邻接矩阵:"<<endl;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>a[i][j];
	prim(a,v-1,n);
	return 0;
}