问题:
使用Prim算法从以下图中构造最小树。

讯享网
最小生成树:构造连通网的最小代价生成树—无回路,v个顶点一定有v-1条边,边的权重系数最小
算法实现思路:
Prim算法:每次在与树相邻接的点中选择权值最小的边,从一个小树慢慢长大
MST[]数组用来存储各顶点是否被收入,初始化为0,收入为1;dist[]数组用来表示各点到树的距离,树里的点为0,和树邻接的点为E(v,w);parent[]为每一个顶点的前一顶点编号

第一步:初始化,从第u个顶点开始构造最小生成树,MST[u] = 1, 其他为0;dist[u] = 0,其他dist[v]=E(u,v);u的邻接点w的parent[w]为u;其他为-1
第二步:进入主循环:从未收录的顶点中找到dist[]最小的v,将该点收入MST, distv] =0;如果这样的点不存在则退出循环
第三步:对于v的每个邻接点w,更新,如果dist[w]>E(v,w) dist[w]= E(v,w) ;parent[w] = v;
当循环完成后,如果(MST中收的顶点不到v个) 生成树不存在。
Prim算法代码实现
void MiniSpanTree_Prim(MGraph N,int u) /*从u开始构造最小生成树*/ { if (u > N.vexnum - 1) return; int dist[MaxSize]; int parent[MaxSize]; int MST[MaxSize]; int i, w, v; int min; /*初始化*/ for (v = 0; v < N.vexnum; v++) { dist[v] = N.arc[u][v].adj; MST[v] = 0; if (N.arc[u][v].adj < INFINITY)//u的临接点 parent[v] = u; } MST[u] = 1;//u收入MST dist[u] = 0; while (1) { v = u; min = INFINITY; for (w = 0; w < N.vexnum; w++)//从未收录中找到dist最小的 { if (MST[w] == 0 && dist[w]<min) { v = w; min = dist[w]; } } if (v == u)//则没有找到 break; MST[v] = 1;//收录进MST dist[v] = 0; for (w = 0; w < N.vexnum; w++)//对于v的每个未收录的邻接点,更新他们到树的最短距离 { if (N.arc[v][w].adj < INFINITY) { if(N.arc[v][w].adj<dist[w]) { dist[w] = N.arc[v][w].adj; parent[w] = v; } } } } printf("输出最小树的各边:\n"); int cnt = 0;//定义一个计数器,来数MST收录的顶点个数 for (i = 0; i < N.vexnum; i++) { if (MST[i] == 1) cnt++; } if (cnt < N.vexnum) printf("生成树不存在\n"); else//打印生成树的各条边 { for (i = 0; i < N.vexnum; i++) { if (i == u)//根结点 continue; else { printf("%s---%s\n", N.vex[i], N.vex[parent[i]]); } } } }
讯享网
完整测试代码
讯享网 #include "pch.h" #include <iostream> #include<stdio.h> #include<stdlib.h> typedef char VertexType; //相当于VertexType 为char[4] #define INFINITY 65535 //最大值 #define MaxSize 50 //最大顶点个数 typedef enum{DG,DN,UDG,UDN}GrandKind;//有向图,有向网,无向图,无向网 typedef int VRType; //顶点关系类型,无权图用0或1,有权图,则为权值类型 typedef char InfoPtr; typedef struct { VRType adj;//对于无权图用0或1表示,1表示相邻,0表示不相邻;对于带权值得图存储权值 InfoPtr * info;//该弧相关信息指针,与弧或边的相关信息 } ArcNode, AdjMatrix[MaxSize][MaxSize]; typedef struct //图的类型定义 { VertexType vex[MaxSize][4];//相当于char[MaxSize][4],用于储存顶点 AdjMatrix arc; // 邻接矩阵,存储边或弧的信息 int vexnum, arcnum;//顶点数和弧的数目 GrandKind kind;//图的定义 }MGraph; /*Dijkstra算法用*/ typedef int PathMatrix[MaxSize];//保存最短路径的数组 typedef int ShortPathLength[MaxSize];//定义一个保存从顶点到V的最短距离的数组 void CreateGraph(MGraph *N); int LocateVertex(MGraph N, VertexType *v); void DestroyGraph(MGraph *N); void DisplayGraph(MGraph N); void Dijkstra(MGraph N, int v0, PathMatrix path, ShortPathLength dist);//Dijkstra算法 void MiniSpanTree_Prim(MGraph N, int u);//Prim算法 void PrintPath(MGraph N, int v, PathMatrix path)//递归打印路径 { /*if (v != 0) { printf("-%s", N.vex[path[v]]); PrintPath(N, path[v], path); } else return;*/ while (v!=-1) { printf("%s-", N.vex[v]); v = path[v]; } } int main() { MGraph N; int i,u; printf("创建无向网:\n"); CreateGraph(&N); DisplayGraph(N); printf("输入根节点:\n"); scanf_s("%d", &u); MiniSpanTree_Prim(N, u); return 0; } void CreateGraph(MGraph *N) // { int i,j,k,weight; VertexType v1[4], v2[4]; printf("请输入有向网的顶点数和弧数(以逗号分开):\n"); scanf_s("%d,%d", &(N->vexnum), &(N->arcnum)); printf("请输入%d个顶点的值(<%d个字符)\n", N->vexnum, MaxSize); for (i = 0; i < N->vexnum; i++)//存储顶点 { scanf_s("%s", N->vex[i],sizeof(N->vex[0])); } for (i = 0; i < N->vexnum; i++)// 初始化邻接矩阵 { for (j = 0; j < N->vexnum; j++) { N->arc[i][j].adj = INFINITY; N->arc[i][j].info = NULL; } } printf("输入两个顶点和弧的权值(以空格隔开):\n"); for (k = 0; k < N->arcnum; k++) { scanf_s("%s %s %d", v1,sizeof(4), v2,sizeof(4) ,&weight); i = LocateVertex(*N, v1);//找到弧尾顶点的下标 j = LocateVertex(*N, v2);//找到弧顶顶点的下标 N->arc[i][j].adj = weight; } N->kind = DN; //类型为有向网 } int LocateVertex(MGraph N, VertexType *v) //定位 { int i; for (i = 0; i < N.vexnum; i++) { if (strcmp(N.vex[i],v)== 0) return i; } return -1; } void DestroyGraph(MGraph *N) //销毁邻接表 { int i, j; for (i = 0; i < N->vexnum; i++) { for (j = 0; j < N->vexnum; j++) { if (N->arc[i][j].info != NULL) { free(N->arc[i][j].info); N->arc[i][j].info = NULL; } } } N->arcnum = N->vexnum = 0; } void DisplayGraph(MGraph N) //显示邻接表 { int i, j, k; printf("输出网的结点和弧:\n"); printf("该网有%d个顶点,%d条弧\n",N.vexnum,N.arcnum); printf("顶点依次是:"); for (i = 0; i < N.vexnum;i++) { printf("%s ", N.vex[i]); } printf("网:\n"); printf("i= "); for (i = 0; i < N.vexnum; i++) { printf("%8d", i); } printf("\n"); for (i = 0; i < N.vexnum; i++) { printf("%8d", i); for (j = 0; j < N.vexnum; j++) { printf("%8d", N.arc[i][j].adj); } printf("\n"); } } void MiniSpanTree_Prim(MGraph N,int u) /*从u开始构造最小生成树*/ { if (u > N.vexnum - 1) return; int dist[MaxSize]; int parent[MaxSize]; int MST[MaxSize]; int i, w, v; int min; /*初始化*/ for (v = 0; v < N.vexnum; v++) { dist[v] = N.arc[u][v].adj; MST[v] = 0; if (N.arc[u][v].adj < INFINITY)//u的临接点 parent[v] = u; } MST[u] = 1;//u收入MST dist[u] = 0; while (1) { v = u; min = INFINITY; for (w = 0; w < N.vexnum; w++)//从未收录中找到dist最小的 { if (MST[w] == 0 && dist[w]<min) { v = w; min = dist[w]; } } if (v == u)//则没有找到 break; MST[v] = 1;//收录进MST dist[v] = 0; for (w = 0; w < N.vexnum; w++)//对于v的每个未收录的邻接点,更新他们到树的最短距离 { if (N.arc[v][w].adj < INFINITY) { if(N.arc[v][w].adj<dist[w]) { dist[w] = N.arc[v][w].adj; parent[w] = v; } } } } printf("输出最小树的各边:\n"); int cnt = 0;//定义一个计数器,来数MST收录的顶点个数 for (i = 0; i < N.vexnum; i++) { if (MST[i] == 1) cnt++; } if (cnt < N.vexnum) printf("生成树不存在\n"); else//打印生成树的各条边 { for (i = 0; i < N.vexnum; i++) { if (i == u)//根结点 continue; else { printf("%s---%s\n", N.vex[i], N.vex[parent[i]]); } } } }
程序截图:

目标结果:

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/82376.html