sjjg.rar_C++最小生成树_数据结构 图_最小生成树

[数据结构]第六次作业：图的建立、遍历、最小生成树、最短路径收藏 新一篇: [数据结构]第七次作业：二叉排序树 /* 程序区分无向图和右向图的代码可以继续完善 */ /* ============== Program Description ============= */ /* Freshare's 6th of dswork */ /* ================================================== */ #include "stdlib.h" #include "stdio.h" #define INFINITY 32767 //无穷大 #define MAX 255 #define TRUE 1 #define FALSE 0 #define QUEUE_SIZE 255 //队列长度 #define ElemType int //队列数据类型 int visited[MAX]; int P[MAX][MAX]; int D[MAX]; int flag;//0无向，1有向 typedef struct //邻接矩阵的类型定义 { char vexs[MAX]; int arcs[MAX][MAX]; int vexnum, arcnum; } MGraph; typedef struct node //邻接表的类型定义 { int adjvex; struct ArcNode *next; } ArcNode; typedef struct { char data; ArcNode *firstarc; } vexnode, AdjList[MAX]; typedef struct{ AdjList AdjList; int vexnum, arcnum; }AlGraph; AlGraph GA; struct //minispantree定义 { int adjvex; int lowcost; } closedge[MAX]; typedef struct{ ElemType data[MAX]; int front,rear; int flag; } SqQueue; //以下是队列的相关操作,默认操作队列是Q SqQueue Q; void IniQueue() //初始化 { Q.front=Q.rear=0; Q.flag=0; } int Empty() //是否为空 { if(Q.front==Q.rear && Q.flag==0) return(1); return(0); } int Full() //是否已满 { if(Q.front==Q.rear && Q.flag==1) return(1); return(0); } int EnQueue(ElemType e) { if(Full(Q)) return(0); else { Q.rear=(Q.rear+1)%MAX; Q.data[Q.rear]=e; Q.flag=1; } return(1); } int DeQueue() { int e; if(Empty(Q)) return(0); else { Q.front=(Q.front+1)%MAX; e=Q.data[Q.front]; Q.flag=0; } return(e); } MGraph CreateUDN(MGraph G) { int i,j,w,k,a,b; char ch1,ch2; printf("输入顶点和边数(用空格分隔):"); scanf("%d %d",&G.vexnum, &G.arcnum);getchar(); printf("输入顶点所用符号:"); for (i=0;i<G.vexnum;i++) G.vexs[i]=getchar();getchar(); for (i=0;i<G.vexnum;i++) for (j=0;j<G.vexnum;j++) G.arcs[i][j]=INFINITY; printf("输入连接每条边的顶点和权数:\n(如:ab2代表a到b的权是2)\n"); for (k=0;k<G.arcnum;k++) { scanf("%c%c%d",&ch1,&ch2,&w);getchar(); for (i=0;i<G.vexnum;i++) {if (G.vexs[i]==ch1) break;} for (j=0;j<G.vexnum;j++) {if (G.vexs[j]==ch2) break;} G.arcs[i][j]=w; if (flag==0) G.arcs[j][i]=w; //无向的 } return(G); } AlGraph CreateAdjlist(AlGraph G,MGraph GM) { int i,j,k,a[MAX],b[MAX],i1=0,j1=0; ArcNode *s; G.vexnum=GM.vexnum; G.arcnum=GM.arcnum; for (i=0;i<G.vexnum;i++) { G.AdjList[i].data=GM.vexs[i]; G.AdjList[i].firstarc=NULL;} for (i=GM.vexnum-1;i>=0;i--) if (flag==0) { for (j=(GM.vexnum-1);j>=i;j--) if(GM.arcs[i][j]!=INFINITY) { s=malloc(sizeof(ArcNode)); s->adjvex=j; s->next=G.AdjList[i].firstarc ; G.AdjList[i].firstarc=s; s=malloc(sizeof(ArcNode)); s->adjvex=i; s->next=G.AdjList[j].firstarc ; G.AdjList[j].firstarc=s; } } else { for (j=(GM.vexnum-1);j>=0;j--) if(GM.arcs[i][j]!=INFINITY) { s=malloc(sizeof(ArcNode)); s->adjvex=j; s->next=G.AdjList[i].firstarc ; G.AdjList[i].firstarc=s; } } return(G); } void DFS (AlGraph G,int v) /*图用邻接表表示*/ { ArcNode *p; int w; visited[v]=1; printf("%c", G.AdjList[v].data ); p=G.AdjList[v].firstarc; while (p!=NULL) { w=p->adjvex; if (visited[w]==0) DFS(G,w); p=p->next; } } void BFS (AlGraph G) /*用邻接表表示*/ { int v,u,w; ArcNode *p; for ( v=0; v<G.vexnum; v++) visited[v]=FALSE; IniQueue(); for ( v=0; v<G.vexnum; v++) if ( !visited[v]) { visited[v]=TRUE; printf("%c", G.AdjList[v].data); EnQueue(v); while (!Empty()) { u=DeQueue(); p=G.AdjList[u].firstarc; while (p!=NULL) { w=p->adjvex; if (!visited[w]) { visited[w]=TRUE; printf("%c", G.AdjList[w].data ); EnQueue(w); } //if p=p->next; } //while } //while } // if } int minimum(int g) { int i=0,min; while(closedge[i].lowcost==0) i++; min=i; for(i=1;i<g;i++) if ((closedge[i].lowcost!=0)&&(closedge[i].lowcost<closedge[min].lowcost)) min=i; return min; } void MiniSpanTree_PRIM(MGraph G, int u) { int i,j,k; k = u; for (j=0; j<G.vexnum; ++j ) { if (j!=k) { closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j]; } } closedge[k].lowcost = 0; for (i=1; i<G.vexnum; ++i) { k = minimum(G.vexnum); printf("%c %c\n",G.vexs[closedge[k].adjvex],G.vexs[k]); closedge[k].lowcost = 0; for (j=0; j<G.vexnum; ++j) if (G.arcs[k][j]<closedge[j].lowcost) { closedge[j].adjvex=k; closedge[j].lowcost=G.arcs[k][j]; } } } void ShortestPath_DIJ(MGraph G,int v0) { int i=0,j,v,w,min; int final[MAX]; for (v=0; v<G.vexnum; ++v) { final[v] = FALSE; D[v] = G.arcs[v0][v]; for (w=0; w<G.vexnum; ++w) P[v][w] = FALSE; // 设空路径 if (D[v] < INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; } } D[v0] = 0; final[v0] = TRUE; for (i=1; i<G.vexnum; ++i) { min = INFINITY; for (w=0; w<G.vexnum; ++w) if (!final[w]) if (D[w]<min) { v = w; min = D[w]; } final[v] = TRUE; for (w=0; w<G.vexnum; ++w) if (!final[w] && (min+G.arcs[v][w]<D[w])) { D[w] = min + G.arcs[v][w]; for(j=0;j<G.vexnum;j++) P[w][j] = P[v][j]; P[w][w] = TRUE; }//if }//for } // ShortestPath_DIJ void main() { MGraph G; int i=0,j=0,k,v; ArcNode *pointer; printf("清选择， 0 - 无向图 ， 1 - 有向图:"); scanf("%d",&flag);getchar(); G=CreateUDN(G);// 邻接矩阵 GA=CreateAdjlist(GA,G);//邻接表，根据G自动生成 printf("邻接表:\n"); for (k=0;k<GA.vexnum;k++) { printf("%c",GA.AdjList[k].data); pointer=GA.AdjList[k].firstarc; while (pointer!=NULL) { printf(" -> %d",pointer->adjvex); pointer=pointer->next; } printf("\n"); } printf("邻接矩阵:\n"); for (i=0;i<G.vexnum;i++) for (j=0;j<G.vexnum;j++) {printf("%d\t",G.arcs[i][j]); if (j==(G.vexnum-1)) printf("\n");} printf("\n输入遍历的起点:"); scanf("%d",&v); printf("DFS遍历:\n"); DFS(GA,v); printf("\nBFS遍历:\n"); BFS(GA); printf("\n最小生成树如下:\n"); MiniSpanTree_PRIM(G,0); printf("\n输入一个顶点的编号，求它到其他顶点的最短路径:"); scanf("%d",&v); ShortestPath_DIJ(G,0); for (i=0;i<G.vexnum;i++) { if (D[i]!=0||D[i]!=INFINITY) printf("到%c的最短路径是: ",G.vexs[i]); for (j=0;j<G.vexnum;j++) if (P[i][j]!=0) printf("-->%c",G.vexs[j]); printf("\n"); } }