main.cpp

最小生成树 MST的四种算法实现。 包括普通的Kruskal算法和Prim算法

#include <iostream>
#include <time.h>
#include <windows.h>
#include "mst.h"

int		n, m;

void	randomlize()
{
	int	i, j, size, choose;
	FILE *fp;

	srand(time(NULL));
	fp = fopen(inputfilename, "w");
	fprintf(fp, "%d %d\n", maxn, maxm);
	choose = maxm; size = maxn*(maxn-1)/2;
	for (i = 0; i < maxn; i++)
		for (j = i+1; j < maxn; j++) {
			if (rand() % size < choose) {
				fprintf(fp, "%d %d %d\n", i, j, rand()%maxLen+1);
				choose --;
			}
			size --;
		}
	fclose(fp);
}

int	main()
{
	int	i, start;

	randomlize();
	
	/*
	printf("Running Normal Prim Algorithm ...\n");
	prim_normal_read(n, m);
	start = GetTickCount();
	for (i = 1; i < TestTime; i++) prim_normal(n, m);
	printf("Prim get MST : %d\n", prim_normal(n, m));
	start = GetTickCount()-start;
	printf("Prim cost %d[ms] per case for runtimes of %d \n", start/TestTime, TestTime);

	printf("\n");
	
	printf("Running Heap Prim Algorithm ...\n");
	prim_heap_read(n, m);
	start = GetTickCount();
	for (i = 1; i < TestTime; i++) prim_heap(n, m);
	printf("Prim get MST : %d\n", prim_heap(n, m));
	start = GetTickCount()-start;
	printf("Prim cost %d[ms] per case for runtimes of %d \n", start/TestTime, TestTime);

	printf("\n");
	
	printf("Running Disjoint Set Kruskal Algorithm ...\n");
	kruskal_disjoint_set_read(n, m);
	start = GetTickCount();
	for (i = 1; i < TestTime; i++) kruskal_disjoint_set(n, m);
	printf("Kruskal get MST : %d\n", kruskal_disjoint_set(n, m));
	start = GetTickCount()-start;
	printf("Kruskal cost %d[ms] per case for runtimes of %d \n", start/TestTime, TestTime);

	printf("\n");
	*/
	printf("Running Normal Kruskal Algorithm ...\n");
	kruskal_normal_read(n, m);
	start = GetTickCount();
	for (i = 1; i < TestTime; i++) kruskal_normal(n, m);
	printf("Kruskal get MST : %d\n", kruskal_normal(n, m));
	start = GetTickCount()-start;
	printf("Kruskal cost %d[ms] per case for runtimes of %d \n", start/TestTime, TestTime);

	return 0;
}