sdf.cpp

废话少说

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

#define MAXN 30

typedef struct  
{
	int v1,v2;
	int weight;
}EDGE;
typedef struct
{
	int vnum;
	EDGE e[MAXN*(MAXN-1)/2];
}Graph;
typedef struct node
{
	int v ;
	struct node *next;
}Alist;

void heapadjust(EDGE data[] , int s ,int m)
{
	int j ;
	EDGE t;
	t = data[s];
	for (j = 2*s+1 ; j<=m; j=j*2+1)
	{
		if (j<m && data[j].weight>data[j+1].weight)
		{
			j++;
		}
		if(!(t.weight>data[j].weight))
			break;
		data[s] = data[j];
		s=j;
	}
	data[s]=t;
}

int create_graph(Graph *p)
{
	int k = 0;
	int n;
	int v1,v2;
	int w ;
	cout<<"vertex number of the graph:"<<endl;
	cin>>n;
	if(n<1)
		return 0;
	p->vnum = n;
	do 
	{
		cout<<"edge(vertex1,vertex2,weight):"<<endl;
		cin>>v1>>v2>>w;
		if(v1>=0 && v1<n && v2>=0 && v2<n)
		{
			p->e[k].v1 = v1;
			p->e[k].v2 = v2;
			p->e[k].weight = w;
			k++;
		}
	} while (!(v1==-1 && v2==-1));
	return k;
}

int kruskal(Graph G, int enumber, int tree[][3])
{
	int i, k, m, c = 0;
	int v1, v2;
	Alist *p, *q, *a[MAXN];
	for (i=0; i<G.vnum; i++)
	{
		a[i] = new Alist;
		if (!a[i])
		{
			cout<<"memory allocation error!"<<endl;
			exit(0);
		}
		a[i]->v = i; a[i]->next = NULL;
	}
	for(i=enumber-1; i>=0; i--)
		heapadjust(G.e,i,enumber-1);
	k = G.vnum;
	m = enumber-1;
	i = 0;
	do 
	{
		v1 = G.e[0].v1; 
		v2 = G.e[0].v2;
		p = a[v1];
		while (p && p->v!=v2)
		{
			q = p;
			p = p->next;
		}
		if(!p)
		{
			p = q;
			p->next = a[G.e[0].v2];
			p = a[G.e[0].v1];
			while(p)
			{
				a[p->v] = a[G.e[0].v1];
				p = p->next;
			}
			k--;
			tree[i][0] = v1;
			tree[i][1] = v2;
			tree[i][2] = G.e[0].weight;
			c += G.e[0].weight;
			i++;
		}
		G.e[0] = G.e[m];
		m--;
		heapadjust(G.e,0,m);
	} while (k>1);
	return c;
}

void main()
{
	int i , enumber;
	int tree[MAXN][3];
	int cost = 0 ;
	Graph G;
	enumber = create_graph(&G);
	cost = kruskal(G,enumber,tree);
	cout<<"Minimum-Cost spanning tree(kruskal):"<<endl;
	cout<<"edge\t weight\t"<<endl;
	for (i=0; i<G.vnum-1; i++)
	{
		cout<<tree[i][0]<<"\t"<<tree[i][1]<<"\t"<<tree[i][2]<<endl;
	}
	cout<<"Cost: "<<cost<<endl;

	system("pause");
}