数据结构课程设计源码 图子系统

#include<stdio.h> #define MAXLEN 100 #define MAXE 100 #define MAXV 100 typedef struct{//求MST的数据结构 int vex1; //边的起始顶点 int vex2; //边的终止顶点 int weight; //边的权值 }Edge; typedef struct{ int vexs[MAXLEN]; //图的结点标志 int edges[MAXLEN][MAXLEN]; //稀疏矩阵存储边的信息 int n,e; //结点数目和边的数目 }MGraph; //--------------------------------------头文件和结构体类型的定义 void Creatgraph(MGraph *G); //建立图 void Showgraph(MGraph *G); //显示图的稀疏矩阵 void MST(MGraph *G); //求最小生成树 void quick_sort(Edge arr[],int start,int end);//快速排序 int fun(Edge arr[],int low,int high);//交换 void kruskal(Edge E[],int n,int e); //克鲁斯卡尔算法 //-----------------------------------函数的声明 int main(){ MGraph *G,a; int i,j; char ch1; G=&a; G->e=G->n=0; char choice;//注意类型为字符型 int e; while(1){ printf("\n"); printf("\t\t| 图子系统 |\n"); printf("\t\t|*********************************************|\n"); printf("\t\t|1.-------------创建或更新邻接矩阵 |\n"); printf("\t\t|2.-------------显 示 邻 接 矩 阵 |\n"); printf("\t\t|3.-------------求 最 小 生 成 树 |\n"); printf("\t\t|0.-------------退 出 |\n"); printf("\t\t|*********************************************|\n"); printf("\t\t请输入菜单前的选项:"); fflush(stdin); choice=getchar(); getchar(); switch(choice){ case'1': Creatgraph(G); printf("\n\t\t图的邻接矩阵存储建立完毕。"); break; case'2': Showgraph(G); break; case'3': MST(G); break; case'0': return 0; default: printf("输入数据错误！！！请重新输入:\n") ; } } } void Creatgraph(MGraph *G){ int i,j,k; int ch1,ch2; printf("请输入顶点数和边数（输入格式为：顶点数,边数）\n"); scanf("%d,%d",&(G->n),&(G->e)); printf("请输入顶点标志（信息）每个顶点以回车作为结束：\n"); for(i=0;i<G->n;i++){ fflush(stdin); scanf("%d",&(G->vexs[i])); } for(i=0;i<G->n;i++){//邻接矩阵初始化 for(j=0;j<G->n;j++){ G->edges[i][j]=0; } } printf("请输入每条边对应的两个顶点（先输入弧尾后输入弧头）！\n"); for(k=0;k<G->e;k++){ fflush(stdin); printf("请输入第%d条边的两个顶点标志（用逗号隔开）：",k+1); scanf("%d,%d",&ch1,&ch2); for(i=0;ch1!=G->vexs[i];i++); for(j=0;ch2!=G->vexs[j];j++); printf("请输入该边的权值大小："); scanf("%d",&G->edges[i][j]);//将输入边对应元素设为1 } } void Showgraph(MGraph *G){ int i,j; if(G->e==0&&G->n==0) printf("\n\t\t请先建立一个无向图的邻接矩阵！！！\n"); else{ printf("\n\t\t显示已经建立的一个有向图的邻接矩阵存储\n"); for(i=0;i<G->n;i++){ for(j=0;j<G->n;j++) printf("%5d",G->edges[i][j]); printf("\n"); } } } void MST(MGraph *G){ Edge E[MAXE]; int nume,numn; int i,j,k=0; numn=G->n; nume=G->e; for(i=0;i<numn;i++) for(j=0;j<nume;j++){ if(G->edges[i][j]!=0){ E[k].vex1=G->vexs[i]; E[k].vex2=G->vexs[j]; E[k].weight=G->edges[i][j]; k++; } } quick_sort(E,0,nume-1); kruskal(E,numn,nume); } void quick_sort(Edge arr[],int start,int end){ int pos; if(start<end) { pos=fun(arr,start,end); quick_sort(arr,start,pos-1); quick_sort(arr,pos+1,end); } } int fun(Edge arr[],int low,int high){ int key; Edge lowx; lowx=arr[low]; key=arr[low].weight; while(low<high) { while(low<high && arr[high].weight>=key) high--; if(low<high) arr[low++]=arr[high]; while(low<high && arr[low].weight<=key) low++; if(low<high) arr[high--]=arr[low]; } arr[low]=lowx; return low; } void kruskal(Edge E[],int n,int e){ int i,j,m1,m2,sn1,sn2,k,sum=0; int vset[n+1]; for(i=1;i<=n;i++) //初始化辅助数组 vset[i]=i; k=1;//表示当前构造最小生成树的第k条边，初值为1 j=0;//E中边的下标，初值为0 while(k<e)//生成的边数小于e时继续循环 { m1=E[j].vex1; m2=E[j].vex2;//取一条边的两个邻接点 sn1=vset[m1]; sn2=vset[m2]; //分别得到两个顶点所属的集合编号 if(sn1!=sn2)//两顶点分属于不同的集合，该边是最小生成树的一条边 {//防止出现闭合回路 printf("起点V%d---终点V%d 权值%d\n",m1,m2,E[j].weight); sum+=E[j].weight; k++; //生成边数增加 if(k>=n) break; for(i=1;i<=n;i++) //两个集合统一编号 if (vset[i]==sn2) //集合编号为sn2的改为sn1 vset[i]=sn1; } j++; //扫描下一条边 } printf("最小权值之和=%d\n",sum); }