[原创]无向图转换&遍历&MST(页 1) - 数据结构与算法 - 编程论坛

haroldi 发表于 2007-4-6 15:51

[原创]无向图转换&遍历&MST

请不吝赐教,多多指点...多谢了! //"有向图"参见<a href="http://bbs.bc-cn.net/viewthread.php?tid=130955&extra=&page=1#130955" target="_blank" >http://bbs.bc-cn.net/viewthread.php?tid=130955&extra=&page=1#130955</A> //<a href="http://blog.bc-cn.net/user15/82588/index.shtml" target="_blank" >http://blog.bc-cn.net/user15/82588/index.shtml</A> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #define MaxSize 250 #define MaxLine 20 typedef int Status; typedef int ElemType; typedef struct{ ElemType VNode; }VexType; typedef struct Arcs{ ElemType Adj; unsigned int Weight; struct Arcs *NextArc; }ArcType; typedef struct{ VexType Vex[MaxSize]; ArcType *FirstArc[MaxSize]; int VexNums; }ALGraph; //定义图的无向邻接表; typedef struct{ VexType Vex[MaxSize]; unsigned int Weight[MaxSize][MaxSize]; int VexNums; }AMGraph; //定义图的邻接矩阵; typedef struct{ ElemType head,tail; unsigned int Weight; }MST; //最小生成树辅助结构; //================================================================================= Status CreateALGraph(ALGraph *ALG,FILE *fp); //创立无向图的邻接表; Status AL2AM(ALGraph ALG,AMGraph *AMG); //转换为图的邻接矩阵; Status ALG_Travers(ALGraph ALG); //图的遍历; Status ALG_DFS(ALGraph ALG,int v,int *Visited); //深度遍历(递归); Status ALG_DFS_Uni(ALGraph ALG,int v,int *Visited); //深度遍历(非递归); Status ALG_BFS(ALGraph ALG,int v,int *Visited); //广度遍历; Status CreateMST(ALGraph ALG,AMGraph AMG); //构造最小生成树; Status AMG_Prim(AMGraph AMG,MST *MST_P); //(邻接矩阵)Prim; Status ALG_Prim(ALGraph ALG,MST *MST_P); //(邻接表)Prim; Status ALG_Kruskal(ALGraph ALG,MST *MST_K); //(邻接表)Kruskal; Status AMG_Kruskal(AMGraph AMG,MST *MST_K); //(邻接矩阵)Kruskal; Status FindVex(int *Vex,int v); //(Kruskal)查找顶点所在树的根结点在数组Vex中的序号; Status Prn_ALGraph(ALGraph ALG); //输出邻接表; Status Prn_AMGraph(AMGraph AMG); //输出邻接矩阵; Status PrintMST(MST *MT); //输出最小生成树; //================================================================================= int main(void) { ALGraph ALG; AMGraph AMG; FILE *fp; char FileName[MaxLine]; printf("\t\t<<<<<< 无向图的应用演示 >>>>>>\n创立无向图：\n"); printf("==============================================================\n"); printf(" 包含图信息的文本文件的格式为：\n第一行： 12\t<--- 顶点总数；\n"); printf("第二行： 1 6 16\n"); printf("\t ↑ ↑ ↑\n"); printf("\t │ │ └─── AB边的权值Weight；\n"); printf("\t │ └──── A边所依附的另一顶点B；\n"); printf("\t └────── 某顶点A。\n第m行：以后各行与第二行类似。\n"); printf("==============================================================\n"); printf("输入文本文件名(输入quit退出)。\n"); do{ printf(" 输入文件名："); gets(FileName); if(!strcmp(FileName,"quit")) exit (1); }while(FileName[0] == '\0' || !(fp = fopen(FileName,"r")));
 printf("\n\n 一、创立无向图的邻接表(Adjacency List)：\n"); CreateALGraph(&ALG,fp); fclose(fp); Prn_ALGraph(ALG); printf("\n\n 二、邻接表的图的遍历(Traversing graph)：\n"); ALG_Travers(ALG); printf("\n\n 三、图的邻接表转换为邻接矩阵(Adjacency Matrix)：\n"); AL2AM(ALG,&AMG); Prn_AMGraph(AMG); printf("\n\n 四、构建最小生成树MST(mininum cost spaning tree)：\n"); CreateMST(ALG,AMG); printf("\n");system("pause"); return 0; }
[align=right][color=#000066][此贴子已经被作者于2007-4-21 21:35:26编辑过][/color][/align]

haroldi 发表于 2007-4-6 15:51

回复：（haroldi）无向图转换&遍历&MST

Status CreateALGraph(ALGraph *ALG,FILE *fp)//创立无向图的邻接表; { ArcType *p = NULL; int i,j,w; fscanf(fp,"%d",&ALG->VexNums); for(i = 1;i <= ALG->VexNums;i++) //初始化; { ALG->Vex[i].VNode = i; ALG->FirstArc[i] = NULL; } while(fscanf(fp,"%d%d%d",&i,&j,&w) == 3) { if(!(p = (ArcType *)malloc(sizeof(ArcType)))) {printf("\n内存溢出。");return 1;} p->Adj = j; p->Weight = w; p->NextArc = ALG->FirstArc[i]; ALG->FirstArc[i] = p; if(!(p = (ArcType *)malloc(sizeof(ArcType)))) {printf("\n内存溢出。");return 1;} p->Adj = i; //无向邻接表,反向赋值...:-( p->Weight = w; p->NextArc = ALG->FirstArc[j]; ALG->FirstArc[j] = p; } return 0; } //================================================================================= Status AL2AM(ALGraph ALG,AMGraph *AMG) //转换为图的邻接矩阵; { int i,j; ArcType *p = NULL; AMG->VexNums = ALG.VexNums; for(i = 1;i <= AMG->VexNums;i++) //初始化; for(j = 1;j <= AMG->VexNums;j++) AMG->Weight[i][j] = INT_MAX; for(i = 1;i <= ALG.VexNums;i++) { AMG->Vex[i] = ALG.Vex[i]; p = ALG.FirstArc[i]; while(p != NULL) { AMG->Weight[i][p->Adj] = p->Weight; p = p->NextArc; } } return 0; } //================================================================================= Status ALG_Travers(ALGraph ALG) //图的遍历; { int i,Visited[MaxSize]; printf("\n 1. 图的深度遍历："); printf("\n递 归："); for(i = 1;i <= ALG.VexNums;i++) Visited[i] = 0; for(i = 1;i <= ALG.VexNums;i++) if(Visited[i] == 0) ALG_DFS(ALG,i,Visited); printf("\n非递归："); for(i = 1;i <= ALG.VexNums;i++) Visited[i] = 0; for(i = 1;i <= ALG.VexNums;i++) if(Visited[i] == 0) ALG_DFS_Uni(ALG,i,Visited); printf("\n\n 2. 图的广度遍历：\n\t"); for(i = 1;i <= ALG.VexNums;i++) Visited[i] = 0; for(i = 1;i <= ALG.VexNums;i++) if(Visited[i] == 0) ALG_BFS(ALG,i,Visited); return 0; } //================================================================================= Status ALG_DFS(ALGraph ALG,int v,int *Visited) //图的深度遍历(递 归); { ArcType *p = NULL; Visited[v] = 1; printf("%2d ->",v); p = ALG.FirstArc[v]; while(p != NULL) { if(Visited[p->Adj] == 0) ALG_DFS(ALG,p->Adj,Visited); p = p->NextArc; } return 0; } //================================================================================= Status ALG_DFS_Uni(ALGraph ALG,int v,int *Visited)//图的深度遍历(非递归); { ElemType Stack[MaxSize]; ArcType *p = NULL; int top = -1; Visited[v] = 1; printf("%2d ->",v); Stack[++top] = v; while(top != -1) { p = ALG.FirstArc[Stack[top]]; while(p != NULL) { if(Visited[p->Adj] == 0) { Visited[p->Adj] = 1; printf("%2d ->",p->Adj); Stack[++top] = p->Adj; break; } p = p->NextArc; } if(p == NULL) --top; } return 0; } //================================================================================= Status ALG_BFS(ALGraph ALG,int v,int *Visited) //图的广度遍历; { int rear,front; ElemType Queue[MaxSize]; ArcType *p = NULL; rear = front = 0; Visited[v] = 1; printf("%2d ->",v); rear =(rear + 1)%MaxSize; Queue[rear] = v; while(rear != front) { front = (front + 1)%MaxSize; p = ALG.FirstArc[Queue[front]]; while(p != NULL) { if(Visited[p->Adj] == 0) { Visited[p->Adj] = 1; printf("%2d ->",p->Adj); rear =(rear + 1)%MaxSize; Queue[rear] = p->Adj; } p = p->NextArc; } } return 0; } //================================================================================= Status CreateMST(ALGraph ALG,AMGraph AMG)//构造最小生成树; { MST MST_MP[MaxSize],MST_LP[MaxSize],MST_MK[MaxSize],MST_LK[MaxSize]; printf("\n\n 1. Prim普里姆(图的邻接矩阵)：\n"); AMG_Prim(AMG,MST_MP); PrintMST(MST_MP); printf("\n\n 2. Kruskal克鲁斯卡尔(图的邻接表)：\n"); ALG_Kruskal(ALG,MST_LK); PrintMST(MST_LK); printf("\n\n 3. Prim普里姆(图的邻接表)：\n"); ALG_Prim(ALG,MST_LP); PrintMST(MST_LP); printf("\n\n 4. Kruskal克鲁斯卡尔(图的邻接矩阵)：\n"); AMG_Kruskal(AMG,MST_MK); PrintMST(MST_MK); return 0; } //================================================================================= Status AMG_Prim(AMGraph AMG,MST *MST_P) //Prim普里姆(邻接矩阵)，适于稠密网; { int i,j,k,Vex[MaxSize]; //最小生成树结点; unsigned int min,lowcost[MaxSize]; //(由Vex[i]到i)权值; for(i = 2;i <= AMG.VexNums;i++) { Vex[i] = 1; //表示V-U中各点与U(当前仅含顶点1)的关系; lowcost[i] = AMG.Weight[1][i]; //各点对U的权值(1到各点的权值); } // Vex[1] = 1; //从顶点1开始遍历; lowcost[1] = 0; //U中仅包含顶点1; for(i = 1;i <= AMG.VexNums;i++) { k = i; min = INT_MAX; for(j = 1;j <= AMG.VexNums;j++)//得到与当前点i相临且权值最小min的顶点k; { if(lowcost[j] < min && lowcost[j] != 0)//找(V-U)各点对U中权值最小的; { min = lowcost[j]; k = j; } } if(min == INT_MAX) break; //若U与V-U再没有边(不连通或V==U),退出循环; printf("[%2d,%2d]；",Vex[k],k); MST_P[i].head = Vex[k]; //将得到的MST各点送入MST_P; MST_P[i].tail = k; MST_P[i].Weight = lowcost[k]; // vex[k] = 0; lowcost[k] = 0; //顶点k并入U;
 for(j = 1;j <= AMG.VexNums;j++) //重新计算U与V-U间各个权值; { if(AMG.Weight[k][j] < lowcost[j]) { Vex[j] = k; lowcost[j] = AMG.Weight[k][j]; } } } if(i == AMG.VexNums) MST_P[0].Weight = i - 1; else MST_P[0].Weight = 0;//MST结点数如与图中总数不等,则不能生成MST或有误; return 0; } //================================================================================= Status ALG_Prim(ALGraph ALG,MST *MST_P) //(图的邻接表)Prim普里姆，适于稠密网; { // struct {ElemType Vex; unsigned int lowcost;}closedge[MaxSize]; int i,j,k,Vex[MaxSize]; unsigned int min,lowcost[MaxSize]; ArcType *p = NULL; for(i = 1;i <= ALG.VexNums;i++) { Vex[i] = 1; p = ALG.FirstArc[1]; //从[1]开始遍历; while(p != NULL) { if(p->Adj == i) lowcost[i] = p->Weight; p = p->NextArc; } } // Vex[1] = 1; lowcost[1] = 0; for(i = 1;i <= ALG.VexNums;i++) { k = i; min = INT_MAX; for(j = 1;j <= ALG.VexNums;j++) { if(lowcost[j] < min && lowcost[j] != 0) { min = lowcost[j]; k = j; } } if(min == INT_MAX) break; //若U与V-U再没有边(不连通或V==U),退出循环; printf("[%2d,%2d]；",Vex[k],k); MST_P[i].head = Vex[k]; //将得到的MST各点送入MST_P; MST_P[i].tail = k; MST_P[i].Weight = lowcost[k]; // vex[k] = 0; lowcost[k] = 0; //顶点k并入U;
 for(j = 1;j <= ALG.VexNums;j++) { p = ALG.FirstArc[k]; while(p != NULL) { if(p->Adj == j && p->Weight < lowcost[j]) { lowcost[j] = p->Weight; Vex[j] = k; } p = p->NextArc; } } } if(i == ALG.VexNums) MST_P[0].Weight = i - 1; else MST_P[0].Weight = 0;//MST结点数如与图中总数不等,则不能生成MST或有误; return 0; } //================================================================================= Status FindVex(int *Vex,int v)//(Kruskal)找顶点所在树的根结点在数组Vex中的序号; { int t; t = v; while(Vex[t] > 0) t = Vex[t]; return t; } //================================================================================= Status AMG_Kruskal(AMGraph AMG,MST *MST_K)//Kruskal(邻接矩阵),适于稀疏网; { typedef struct{ ElemType v1,v2; unsigned int cost; }EdgeType; EdgeType Edgs[MaxSize]; int i,j,k,vex1,vex2,Vex[MaxSize]; ElemType tv; unsigned int tc; k = 1; Edgs[0].cost = 0; //记录总边数到Edgs[0].cost中; for(i = 1;i <= AMG.VexNums;i++) //将所有两点间关系初始化到Edgs中; { for(j = 1;j < i;j++) { Edgs[k].v1 = AMG.Vex[j].VNode; //j变化快,赋予v1(较小的坐标在前); Edgs[k].v2 = AMG.Vex[i].VNode; Edgs[k].cost = AMG.Weight[i][j]; if(AMG.Weight[i][j] < INT_MAX) ++Edgs[0].cost; ++k; } } for(i = 1;i < AMG.VexNums*AMG.VexNums;i++) //Edgs按cost值,非递减排序; { k = i; for(j = i+1;j <= AMG.VexNums*AMG.VexNums;j++) if(Edgs[k].cost > Edgs[j].cost) k = j; if(k != i) { tv = Edgs[i].v1; Edgs[i].v1 = Edgs[k].v1; Edgs[k].v1 = tv; tv = Edgs[i].v2; Edgs[i].v2 = Edgs[k].v2; Edgs[k].v2 = tv; tc = Edgs[i].cost; Edgs[i].cost = Edgs[k].cost; Edgs[k].cost = tc; } }
 for(i = 1;i <= AMG.VexNums;i++) Vex[i] = 0; //各点初始均独立; i = k = 1; while(k < AMG.VexNums) { vex1 = FindVex(Vex,Edgs[i].v1); vex2 = FindVex(Vex,Edgs[i].v2); if(vex1 != vex2) { Vex[vex2] = vex1; printf("[%2d,%2d]；",Edgs[i].v1,Edgs[i].v2); MST_K[k].head = Edgs[i].v1; //将得到的MST各点送入MST_K; MST_K[k].tail = Edgs[i].v2; MST_K[k].Weight = Edgs[i].cost; if(++k >= (int)Edgs[0].cost - 1) break; } ++i; } if(k - 1 == AMG.VexNums - 1) MST_K[0].Weight = AMG.VexNums - 1; else MST_K[0].Weight = 0; return 0; } //================================================================================= Status ALG_Kruskal(ALGraph ALG,MST *MST_K)//Kruskal(邻接表),适于稀疏网; { typedef struct{ElemType v1,v2;unsigned int cost;} EdgeType; int i,j,k; ElemType Vex[MaxSize],v1,v2,tv; unsigned int tc; ArcType *p = NULL; EdgeType Edge[MaxSize]; for(j = 1,i = 1;i <= ALG.VexNums;i++) //将所有两点间关系初始化到Edgs中; { Edge[j].v1 = ALG.Vex[i].VNode; p = ALG.FirstArc[i]; while(p != NULL) { Edge[j].v2 = p->Adj; Edge[j].cost = p->Weight; p = p->NextArc; Edge[j].v1 = ALG.Vex[i].VNode; if(Edge[j].v1 < Edge[j].v2) ++j; } } if(Edge[j].v1 > Edge[j].v2) Edge[0].cost = j - 1; else Edge[0].cost = j; //记录总边数到Edgs[0].cost中; for(i = 1;i < (int)Edge[0].cost;i++) //Edgs按cost值,非递减排序; { k = i; for(j = i + 1;j <= (int)Edge[0].cost;j++) if(Edge[k].cost > Edge[j].cost) k = j; if(k != i) { tv = Edge[i].v1; Edge[i].v1 = Edge[k].v1; Edge[k].v1 = tv; tv = Edge[i].v2; Edge[i].v2 = Edge[k].v2; Edge[k].v2 = tv; tc = Edge[i].cost; Edge[i].cost = Edge[k].cost; Edge[k].cost = tc; } } for(i = 1;i <= (int)Edge[0].cost;i++) Vex[i] = 0; for(k = 1,i = 1;i <= (int)Edge[0].cost;i++) { v1 = FindVex(Vex,Edge[i].v1); v2 = FindVex(Vex,Edge[i].v2); if(v1 != v2) { Vex[v2] = v1; printf("[%2d,%2d]；",Edge[i].v1,Edge[i].v2); MST_K[k].head = Edge[i].v1; MST_K[k].tail = Edge[i].v2; MST_K[k].Weight = Edge[i].cost; ++k; } } if(k - 1 == ALG.VexNums - 1) MST_K[0].Weight = ALG.VexNums - 1; else MST_K[0].Weight = 0; return 0; } //================================================================================ Status Prn_ALGraph(ALGraph ALG) //输出邻接表; { int i; ArcType *p = NULL; for(i = 1;i <= ALG.VexNums;i++) { printf("\n %2d ==> ",i); p = ALG.FirstArc[i]; while(p != NULL) { printf("%2d(%3d) ->",p->Adj,p->Weight); p = p->NextArc; } } printf("\n"); return 0; } //================================================================================= Status Prn_AMGraph(AMGraph AMG) //输出邻接矩阵; { int i,j; for(i = 1;i <= AMG.VexNums;i++) { printf("\n\t"); for(j = 1;j <= AMG.VexNums;j++) { if(AMG.Weight[i][j] < INT_MAX) printf(" %3d ",AMG.Weight[i][j]); else printf(" ∞ "); } printf("\n"); } return 0; } //================================================================================= Status PrintMST(MST *MT) //输出最小生成树; { unsigned int i = 1; if(MT[0].Weight == 0) {printf("\n\t不能生成最小生成树。\n");return 1;} printf("\n\t边信息\t权 值"); for(i = 1;i <= MT[0].Weight;i++) printf("\n\t(%2d,%2d)\t\t[%4d]",MT[i].head,MT[i].tail,MT[i].Weight); return 0; }

mayue 发表于 2008-6-10 09:41

[tk01]

haroldi 发表于 2008-7-11 23:35

[tk02]

页: [1]

编程论坛's Archiver

[原创]无向图转换&遍历&MST

回复：（haroldi）无向图转换&遍历&MST