#include"time.h"
#include"stdlib.h"
#include"stdio.h"
#include <string.h>
#define MAXE 100
int e,array[20];
struct edges
{
int bv;
int tv;
int w;
};
typedef struct edges edgeset;
int seeks(int set[],int v)
{
int i;
i=v;
while(set[i]>0)
i=set[i];
return i;
}
void kruskal(edgeset ge[],int n,int e)//克鲁斯卡尔算法
{
int set[MAXE],v1,v2,i,j;
for(i=1;i<n+1;i++)
set[i]=0;
i=1;
j=1;
while(j<=e&&i<=n-1)
{
v1=seeks(set,ge[j].bv);
v2=seeks(set,ge[j].tv);
if(v1!=v2)
{
printf("(%d,%d):%d\n",ge[j].bv,ge[j].tv,ge[j].w);
set[v1]=v2;
i++;
}
j++;
}
}
//以下是堆排序
void insertsort(edgeset ge[],int e)
{
int i,j;
for(i=2;i<=e;i++)
if(ge[i].w<ge[i-1].w)
{
ge[0]=ge[i];
j=i-1;
while(ge[0].w<ge[j].w)
{
ge[j+1]=ge[j];
j--;
}
ge[j+1]=ge[0];
}
}
void adjustMinHeap(int *a, int pos, int len){
int temp;
int child;
for (temp = a[pos]; 2 * pos + 1 <= len; pos = child){
child = 2 * pos + 1;
if (child < len && a[child] > a[child + 1])
child++;
if (a[child] < temp){ //再这儿把temp写成了a[pos], 显然应该是待调整的节点,因为如果元素不能往下流动,则退出。。。
a[pos] = a[child];
}
else {
break;
}
}
a[pos] = temp;
} void minHeapSort(int *a)
{
int i;
for (i = e/2 - 1; i >= 0; i--)
adjustMinHeap(a, i, e - 1);
for (i = e - 1; i >= 0; i--){
//printf("%d ", a[0]);
int temp = a[0];
a[0] = a[i];
a[i] = temp;
adjustMinHeap(a, 0, i - 1);
}
}
void main()//主函数
{
printf("\n\n\n\n") ;
for(int m=0;m<10;m++)
printf(" ");
printf("************************************\n\n");
for( m=0;m<10;m++)
printf(" ");
printf("* 最小生成树问题 *\n\n");
for( m=0;m<10;m++)
printf(" ");
printf("************************************\n\n");
srand(time(NULL));
edgeset ge[MAXE];
int a,N,i,r;
printf("请输入顶点个数:");
scanf("%d",&N);
printf("请输入边的条数:");
scanf("%d",&e);
printf("请输入边的信息(起点,终点),边的权值将自动生成:\n");
for(i=1;i<=e;i++)
{
scanf("%d,%d",&ge[i].bv,&ge[i].tv);
r=rand()%10000 ;
ge[i].w=r/10;
}
printf("系统随机产生各个边的权值后前后顶点以及他们之间的边的权值如下:(前顶点,后顶点,权值)\n");
for(i=1;i<=e;i++)
printf("%d,%d,%d\n",ge[i].bv,ge[i].tv,ge[i].w);
printf("\n\n");
//进入堆排序
for( i=0;i<e;i++)
array[i]=ge[i+1].w ;
minHeapSort(array);
printf("堆排序后权值从大到小输出如下\n");
for (i = 0; i < e; i++)
printf("%d ", array[i]);
printf("\n\n权值最小的边是:%d \n",array[e-1]);
printf("\n");
printf("克鲁斯卡尔算法求出最佳路径是:(<城市a,城市b>:路程)\n");
insertsort(ge,e);
kruskal(ge,N,e);
}
#include"stdlib.h"
#include"stdio.h"
#include <string.h>
#define MAXE 100
int e,array[20];
struct edges
{
int bv;
int tv;
int w;
};
typedef struct edges edgeset;
int seeks(int set[],int v)
{
int i;
i=v;
while(set[i]>0)
i=set[i];
return i;
}
void kruskal(edgeset ge[],int n,int e)//克鲁斯卡尔算法
{
int set[MAXE],v1,v2,i,j;
for(i=1;i<n+1;i++)
set[i]=0;
i=1;
j=1;
while(j<=e&&i<=n-1)
{
v1=seeks(set,ge[j].bv);
v2=seeks(set,ge[j].tv);
if(v1!=v2)
{
printf("(%d,%d):%d\n",ge[j].bv,ge[j].tv,ge[j].w);
set[v1]=v2;
i++;
}
j++;
}
}
//以下是堆排序
void insertsort(edgeset ge[],int e)
{
int i,j;
for(i=2;i<=e;i++)
if(ge[i].w<ge[i-1].w)
{
ge[0]=ge[i];
j=i-1;
while(ge[0].w<ge[j].w)
{
ge[j+1]=ge[j];
j--;
}
ge[j+1]=ge[0];
}
}
void adjustMinHeap(int *a, int pos, int len){
int temp;
int child;
for (temp = a[pos]; 2 * pos + 1 <= len; pos = child){
child = 2 * pos + 1;
if (child < len && a[child] > a[child + 1])
child++;
if (a[child] < temp){ //再这儿把temp写成了a[pos], 显然应该是待调整的节点,因为如果元素不能往下流动,则退出。。。
a[pos] = a[child];
}
else {
break;
}
}
a[pos] = temp;
} void minHeapSort(int *a)
{
int i;
for (i = e/2 - 1; i >= 0; i--)
adjustMinHeap(a, i, e - 1);
for (i = e - 1; i >= 0; i--){
//printf("%d ", a[0]);
int temp = a[0];
a[0] = a[i];
a[i] = temp;
adjustMinHeap(a, 0, i - 1);
}
}
void main()//主函数
{
printf("\n\n\n\n") ;
for(int m=0;m<10;m++)
printf(" ");
printf("************************************\n\n");
for( m=0;m<10;m++)
printf(" ");
printf("* 最小生成树问题 *\n\n");
for( m=0;m<10;m++)
printf(" ");
printf("************************************\n\n");
srand(time(NULL));
edgeset ge[MAXE];
int a,N,i,r;
printf("请输入顶点个数:");
scanf("%d",&N);
printf("请输入边的条数:");
scanf("%d",&e);
printf("请输入边的信息(起点,终点),边的权值将自动生成:\n");
for(i=1;i<=e;i++)
{
scanf("%d,%d",&ge[i].bv,&ge[i].tv);
r=rand()%10000 ;
ge[i].w=r/10;
}
printf("系统随机产生各个边的权值后前后顶点以及他们之间的边的权值如下:(前顶点,后顶点,权值)\n");
for(i=1;i<=e;i++)
printf("%d,%d,%d\n",ge[i].bv,ge[i].tv,ge[i].w);
printf("\n\n");
//进入堆排序
for( i=0;i<e;i++)
array[i]=ge[i+1].w ;
minHeapSort(array);
printf("堆排序后权值从大到小输出如下\n");
for (i = 0; i < e; i++)
printf("%d ", array[i]);
printf("\n\n权值最小的边是:%d \n",array[e-1]);
printf("\n");
printf("克鲁斯卡尔算法求出最佳路径是:(<城市a,城市b>:路程)\n");
insertsort(ge,e);
kruskal(ge,N,e);
}