该部分主要包括了网的创建和最小生成树的创建
1.结构体的定义
#define INF 99 #define MAX 20 typedef struct netWork{ //网的结构体 int vexNum; int arcNum; char vexs[MAX]; int arcs[MAX][MAX]; }net,*myNet;
2.网的创建
//网的生成 void createNet(myNet &N) { N=(netWork*)malloc(sizeof(netWork)); //动态声明结构体空间 int i,j,k; char v1,v2;//边的左右顶点 int weight; //权值 printf("请输入顶点的数量:"); scanf("%d",&N->vexNum); printf("请输入边的数量:"); scanf("%d",&N->arcNum); printf("请依次将顶点数据输入进来 "); for(i=0;i<N->vexNum;i++) { getchar(); scanf("%c",&N->vexs[i]); } for(i=0;i<N->vexNum;i++) { for(j=0;j<N->vexNum;j++) { if(i==j) { N->arcs[i][j]=0; //初始化矩阵,全部没有连接 } else { N->arcs[i][j]=INF; //初始化矩阵,全部没有连接 } } } printf("请依次将边和权值输入进来 "); for(i=0;i<N->arcNum;i++) { getchar(); scanf("%c%c",&v1,&v2); //输入边 scanf("%d",&weight); //输入权值 j=getLocate(N,v1); //获取下标 k=getLocate(N,v2); //获取下标 N->arcs[j][k]=weight; //输入权值 N->arcs[k][j]=weight; //输入权值 } }
3.最小生成树的创建(普里姆算法)
void createBiTree(myNet N) { int min,i,j,k; int adjvex[N->vexNum]; //储存顶点相连的上一个坐标 int lowcost[N->vexNum]; //保存相关顶点之间的权值 for(i=0;i<N->vexNum;i++) { adjvex[i]=0; //先所有顶点与第一个顶点相连 lowcost[i]=N->arcs[0][i]; //获取第一个顶点与其他边的所有权值 } for(i=1;i<N->vexNum;i++) //依次查找每个的最小权值 { min=INF; j=1; //除一个顶点之外的遍历所有顶点 k=0; //用来储存每个最小权值边的顶点下标 while(j<N->vexNum) //遍历所有顶点,找到最小权值的顶点 { if(lowcost[j]!=0&&lowcost[j]<min) //出现权值更小的边 0代表该顶点已被连接过 { min=lowcost[j]; //更换最小值 k=j; //最小权值的下标 } j++; } printf("最小权值的边为:%c%c 权值为:%d ",N->vexs[adjvex[k]],N->vexs[k],min); //最小权值的顶点下标为k lowcost[k]=0; //已连接的边,之间的权值就为0 //从两个顶点中找每个位置的最小权值 for(j=1;j<N->vexNum;j++) { if(lowcost[j]!=0&&N->arcs[k][j]<lowcost[j]) { lowcost[j]=N->arcs[k][j]; adjvex[j]=k; //寻找跟k下标有关的最小权值 } } } }
所以的代码如下
#include<stdio.h> #include<stdlib.h> #define INF 99 #define MAX 20 typedef struct netWork{ //网的结构体 int vexNum; int arcNum; char vexs[MAX]; int arcs[MAX][MAX]; }net,*myNet; int getLocate(myNet N,char v) { int i; for(i=0;i<N->vexNum;i++) { if(N->vexs[i]==v) { return i; } } return -1; } //网的生成 void createNet(myNet &N) { N=(netWork*)malloc(sizeof(netWork)); //动态声明结构体空间 int i,j,k; char v1,v2;//边的左右顶点 int weight; //权值 printf("请输入顶点的数量:"); scanf("%d",&N->vexNum); printf("请输入边的数量:"); scanf("%d",&N->arcNum); printf("请依次将顶点数据输入进来 "); for(i=0;i<N->vexNum;i++) { getchar(); scanf("%c",&N->vexs[i]); } for(i=0;i<N->vexNum;i++) { for(j=0;j<N->vexNum;j++) { if(i==j) { N->arcs[i][j]=0; //初始化矩阵,全部没有连接 } else { N->arcs[i][j]=INF; //初始化矩阵,全部没有连接 } } } printf("请依次将边和权值输入进来 "); for(i=0;i<N->arcNum;i++) { getchar(); scanf("%c%c",&v1,&v2); //输入边 scanf("%d",&weight); //输入权值 j=getLocate(N,v1); //获取下标 k=getLocate(N,v2); //获取下标 N->arcs[j][k]=weight; //输入权值 N->arcs[k][j]=weight; //输入权值 } } //网的邻接矩阵打印 void printfNet(myNet N) { int i,j; printf(" "); for(i=0;i<N->vexNum;i++) { printf("%c ",N->vexs[i]); } printf(" "); for(i=0;i<N->vexNum;i++) { printf("%c ",N->vexs[i]); for(int j=0;j<N->vexNum;j++) { printf("%*d ",4,N->arcs[i][j]); //*代表的是输出的宽度,右对齐,左边空着不填 } printf(" "); } } //生成最小生成树 普里姆算法 void createBiTree(myNet N) { int min,i,j,k; int adjvex[N->vexNum]; //储存顶点相连的上一个坐标 int lowcost[N->vexNum]; //保存相关顶点之间的权值 for(i=0;i<N->vexNum;i++) { adjvex[i]=0; //先所有顶点与第一个顶点相连 lowcost[i]=N->arcs[0][i]; //获取第一个顶点与其他边的所有权值 } for(i=1;i<N->vexNum;i++) //依次查找每个的最小权值 { min=INF; j=1; //除一个顶点之外的遍历所有顶点 k=0; //用来储存每个最小权值边的顶点下标 while(j<N->vexNum) //遍历所有顶点,找到最小权值的顶点 { if(lowcost[j]!=0&&lowcost[j]<min) //出现权值更小的边 0代表该顶点已被连接过 { min=lowcost[j]; //更换最小值 k=j; //最小权值的下标 } j++; } printf("最小权值的边为:%c%c 权值为:%d ",N->vexs[adjvex[k]],N->vexs[k],min); //最小权值的顶点下标为k lowcost[k]=0; //已连接的边,之间的权值就为0 //从两个顶点中找每个位置的最小权值 for(j=1;j<N->vexNum;j++) { if(lowcost[j]!=0&&N->arcs[k][j]<lowcost[j]) { lowcost[j]=N->arcs[k][j]; adjvex[j]=k; //寻找跟k下标有关的最小权值 } } } } int main() { myNet N; createNet(N); //网的创建 printfNet(N); //网的邻接矩阵打印 createBiTree(N); //最小生成树 return 0; }