shu2.cpp

演示Kruskal算法和Prim算法 集合的并,元素查找的操作及应用 说明: 代码均在vc++6.0环境下编译均通过 在非VC++6.0环境下编译请去掉头文件 windows.h 和函

#include<stdio.h>
#include<stdlib.h>
#define M 30
#define MAX 30
typedef struct
{
	int begin;
    int end;
    int weight;
}edge;
typedef struct
{
    int adj;
    int weight;
}AdjMatrix[MAX][MAX];
typedef struct
{
    AdjMatrix arc;
    int vexnum, arcnum;
}MGraph;
//******函数申明******//
void CreatGraph(MGraph *);//构建图
void sort(edge* ,MGraph *);//对权值进行排序
void MiniSpanTree(MGraph *);//生成最小生成树
int  Find(int *, int );//找尾
void Swapn(edge *, int, int);//交换权值 以及头和尾
//******函数构造******//
void CreatGraph(MGraph *G)//构建图
{
    int i, j,n, m;
	printf("******************欢迎使用本系统!******************\n\n");
    printf("请输入你所要创建的图的边数和顶点数(用空格隔开):");
    scanf("%d %d",&G->arcnum,&G->vexnum);
    for (i = 1; i <= G->vexnum; i++)//初始化图
	{
        for ( j = 1; j <= G->vexnum; j++)
		{
            G->arc[i][j].adj = G->arc[j][i].adj = 0;
		}
	}
    for ( i = 1; i <= G->arcnum; i++)//输入边和权值
	{
        printf("\n请输入有边的2个顶点(用阿拉伯数字表示 用空格隔开)");
        scanf("%d %d",&n,&m);
        while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum)
		{
            printf("输入的数字不符合要求,请重新输入(用空格隔开):");
            scanf("%d %d",&n,&m);
		}
        G->arc[n][m].adj = G->arc[m][n].adj = 1;
        getchar();
        printf("\n请输入%d与%d之间的权值:", n, m);
        scanf("%d",&G->arc[n][m].weight);
	}
    printf("邻接矩阵为:\n");
    for ( i = 1; i <= G->vexnum; i++)
	{
        for ( j = 1; j <= G->vexnum; j++)
		{
            printf("%d ",G->arc[i][j].adj);
		}
        printf("\n");
	}
}
void sort(edge edges[],MGraph *G)//对权值进行排序
{
    int i, j;
    for ( i = 1; i <= G->arcnum; i++)
	{
        for ( j = i + 1; j <= G->arcnum; j++)
		{
            if (edges[i].weight > edges[j].weight)
			{
                Swapn(edges, i, j);
			}
		}
	}
    printf("权排序之后的权值顺序为:\n");
    for (i = 1; i <= G->arcnum; i++)
	{
        printf("<< %d, %d >>   %d\n", edges[i].begin, edges[i].end, edges[i].weight);
	}
}
void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾
{
    int temp;
    temp = edges[i].begin;
    edges[i].begin = edges[j].begin;
    edges[j].begin = temp;
    temp = edges[i].end;
    edges[i].end = edges[j].end;
    edges[j].end = temp;
    temp = edges[i].weight;
    edges[i].weight = edges[j].weight;
    edges[j].weight = temp;
}
void MiniSpanTree(MGraph *G)//生成最小生成树
{
    int i, j, n, m;
    int k = 1;
    int parent[M];
    edge edges[M];
    for ( i = 1; i < G->vexnum; i++)
	{
        for (j = i + 1; j <= G->vexnum; j++)
		{
            if (G->arc[i][j].adj == 1)
			{
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G->arc[i][j].weight;
                k++;
			}
		}
	}
    sort(edges, G);
    for (i = 1; i <= G->arcnum; i++)
	{
        parent[i] = 0;
	}
    printf("最小生成树为:\n");
    for (i = 1; i <= G->arcnum; i++)//核心部分
	{
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if (n != m)
		{
            parent[n] = m;
            printf("<< %d, %d >>   %d\n", edges[i].begin, edges[i].end, edges[i].weight);
		}
	}
}
int Find(int *parent, int f)//找尾
{
	while ( parent[f] > 0)
	{
        f = parent[f];
	}
    return f;
}
//******主函数******//
int main(void)//主函数
{
    MGraph *G;
    G = (MGraph*)malloc(sizeof(MGraph));
    if (G == NULL)
	{
        printf("memory allcation failed,goodbye");
        exit(1);
	}
    CreatGraph(G);//构建图
    MiniSpanTree(G);//生成最小生成树
    system("pause");//程序结束
    return 0;
}