最小生成树——Prim算法与Kruskal算法

简介: 最小生成树——Prim算法与Kruskal算法

最小生成树概念:

连通图: 在一个无向图中,任意两个顶点之间都是可达的(有路径连通),则成该无向图为连通图。

生成树: 一个连通图的生成树是一个极小的连通子图,它含有图中的全部顶点,但只有构成一棵树的n-1条边。也就是说,无向图中连通n个顶点n-1条边就叫做生成树。

最小生成树: 构造连通图的最小代价生成树称为最小生成树,也就是说,所有的边加权后和最小的树。


Prim算法

Prim算法计算最小生成树的方法从一个结点开始使树一点点的成长。在每一步,都增加一个结点作为根,并连接这个结点作为边,也就是说每次增加一个一个结点和一条边,这样也就把相关联的顶点加到增长中的树上了。这个过程主要体现在“加点”,在算法进行的过程中,有一个已经添加到树上的顶点集,这个顶点集实际就是最小生成树的结点集合,其余顶点都作为选择,等待是否被加入集合。每次选择一个顶点,使得它和上一个顶点之间的代价最小,并把这条边加入到最小生成树中,把顶点加入到集合中。

下面通过图示来描述Prim算法的思想:

首先选择一个顶点作为起始,比如A,第一轮发现AC代价最小,那么就把AC边加入最小生成树,把A加入顶点集合;

后面依次寻找最小代价边,直到全部顶点都加入到顶点集合。

在程序中,通过一个最小代价标记,并一行一行的扫描来搜索最小代价边,下面来看具体代码。

首先我们定义一个图的数据类型,该数据类型包含图的顶点集合、邻接矩阵,顶点数和边数。另外宏定义两个常量,通过一个不可能的数比如65535来表示两个顶点之间没有边。

#define MAXVER    6     /*最大顶点个数*/
#define INFINITY  65535   /*代表无穷大*/
typedef struct _graph_type
{
  char  vertex[MAXVER]; /*存放顶点的数组*/
  int   arc[MAXVER][MAXVER]; /*邻接矩阵*/ 
  int   vertex_num; /*顶点数*/
  int   edge_num; /*边数*/
}graph_type;

Prim算法C语言实现

/*普利姆Prim算法求最小生成树*/
void mini_span_tree_prim(graph_type g)
{
  int min = 0; /*保存最小权值*/
  int k = 0; /*存放最小权值的顶点下标*/
  int i = 0;
  int j = 0;
  int vertex_tree[MAXVER]; /*顶点下标 - 最小生成树的结点*/
  int weight[MAXVER]; /*边的权值,置为0表示下标对应的顶点已加入最小生成树*/
  weight[0] = 0; /*假设图标号为0的顶点是最小生成树的第一个结点*/
  vertex_tree[0] = 0; /*加入第一个顶点*/
  for(i = 1; i < g.vertex_num; i++) /*遍历图的所有顶点*/
  {
    weight[i] = g.arc[0][i]; /*把和0号顶点有边的边的权值存入数组*/
    vertex_tree[i] = 0; /*初始化为0号顶点*/
  }
  for(i = 1; i < g.vertex_num; i++)
  {
    min = INFINITY; /*初始化最小权值为无穷大*/
    j = 1;
    k = 0;
    while(j < g.vertex_num) /*遍历所有顶点*/
    {
      if(weight[j] != 0 && weight[j] < min)
      {
        /*如果权值不为0(未加入最小生成树),且权值小于最小权值min*/
        min = weight[j]; /*更新当前最小权值*/
        k = j; /*保存最小权值边所以来的顶点,第一次循环表示 (0, k)为0开始的所有边中权值最小的边*/
      }
      j++;
    }
    weight[k] = 0; /*将k的权值置为0,表示这个结点的最小权值已经找到了,同时顶点k已被加入最小生成树中*/
    for(j = 1; j < vertex_num; j++)
    {
      if(weight[j] != 0 && g.arc[k][j] < weight[j])
      {
        /*如果j没有加入最小生成树,且邻接矩阵第k行相应权值小于weigh记录的最小权值*/
        weight[j] = g.arc[k][j]; /*更新weight*/
        vertex_tree[j] = k; /*把k加入到最小生成树*/
      }
    }
  }
}

Kruskal算法

Prim算法是以某个顶点开始,逐步寻找各个顶点上最小权值的边,这样一步步来构建最小生成树。第二种贪心策略是连续地按照最小的权选择边,并且当所选的边不产生回路时就把它作为取定的边。

在形式上Kruskal算法是在处理一个森林,开始的时候,存在n棵单结点的树,每次添加一条边把两棵树合并成一棵树,当算法终止时剩下的一棵树就是最小生成树。

假设图和上面一样

首先我们得到一张表,每条边按权值从小到大排序

然后开始加边,优先选择权值小的边

加最后一条边,得到最小生成树,和Prim算法得到的一样

Kruskal算法C语言实现

#define MAXedge_type 20 /*最大边数*/
#define MAXVEX 20  /*最大顶点数*/
#define INFINITY 65535 /*无穷大*/
typedef struct
{
  int arc[MAXVEX][MAXVEX];
  int vertex_num;
  int edge_type_num;
}graph_type;
typedef struct
{
  int begin;
  int end;
  int weight;
}edge_type;   /* 对边集数组edge_type结构的定义 */
/* 交换权值 以及头和尾 */
void Swapn(edge_type *edge_types,int i, int j)
{
  int temp;
  temp = edge_types[i].begin;
  edge_types[i].begin = edge_types[j].begin;
  edge_types[j].begin = temp;
  temp = edge_types[i].end;
  edge_types[i].end = edge_types[j].end;
  edge_types[j].end = temp;
  temp = edge_types[i].weight;
  edge_types[i].weight = edge_types[j].weight;
  edge_types[j].weight = temp;
}
/* 对权值进行排序 */
void sort(edge_type edge_types[], graph_type *G)
{
  int i, j;
  for ( i = 0; i < G->edge_type_num; i++)
  {
    for ( j = i + 1; j < G->edge_type_num; j++)
    {
      if (edge_types[i].weight > edge_types[j].weight)
      {
        Swapn(edge_types, i, j);
      }
    }
  }
  printf("权排序之后的为:\n");
  for (i = 0; i < G->edge_type_num; i++)
  {
    printf("(%d, %d) %d\n", edge_types[i].begin, edge_types[i].end, edge_types[i].weight);
  }
}
/* 查找连线顶点的尾部下标 */
int Find(int *parent, int f)
{
  while ( parent[f] > 0)
  {
    f = parent[f];
  }
  return f;
}
/* 生成最小生成树 */
void MiniSpanTree_Kruskal(graph_type G)
{
  int i, j, n, m;
  int k = 0;
  int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */
  edge_type edge_types[MAXedge_type];/* 定义边集数组,edge_type的结构为begin,end,weight,均为整型 */
  /* 用来构建边集数组并排序 */
  for ( i = 0; i < G.vertex_num-1; i++)
  {
    for (j = i + 1; j < G.vertex_num; j++)
    {
      if (G.arc[i][j]<INFINITY)
      {
        edge_types[k].begin = i;
        edge_types[k].end = j;
        edge_types[k].weight = G.arc[i][j];
        k++;
      }
    }
  }
  sort(edge_types, &G);
  for (i = 0; i < G.vertex_num; i++)
    parent[i] = 0;  /* 初始化数组值为0 */
  for (i = 0; i < G.edge_type_num; i++) /* 遍历每一条边 */
  {
    n = Find(parent,edge_types[i].begin);
    m = Find(parent,edge_types[i].end);
    if (n != m) /* 假如n与m不等,说明此边没有与现有的生成树形成环路 */
    {
      parent[n] = m;  /* 将此边的结尾顶点放入下标为起点的parent中。 */
              /* 表示此顶点已经在生成树集合中 */
      printf("(%d, %d) %d\n", edge_types[i].begin, edge_types[i].end, edge_types[i].weight);
    }
  }
}


目录
打赏
0
0
0
0
13
分享
相关文章
使用贪心算法解决最小生成树问题
大家好,我是V哥。今天聊聊贪心算法解决最小生成树问题。面试中遇到此类题目,需掌握Prim和Kruskal算法。Prim适合稠密图,Kruskal适合稀疏图。两者时间复杂度分别为O(m log n)和O(m log m),各有优缺点。应用场景广泛,包括图像处理、传感器网络、社交网络分析等。关注V哥,全栈之路一起走。
基于prim算法求出网络最小生成树实现网络社团划分和规划
该程序使用MATLAB 2022a版实现路线规划,通过排序节点权值并运用Prim算法生成最小生成树完成网络规划。程序基于TSP问题,采用遗传算法与粒子群优化算法进行路径优化。遗传算法通过编码、选择、交叉及变异操作迭代寻优;粒子群优化算法则通过模拟鸟群觅食行为,更新粒子速度和位置以寻找最优解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
基于遗传优化算法的风力机位置布局matlab仿真
本项目基于遗传优化算法(GA)进行风力机位置布局的MATLAB仿真,旨在最大化风场发电效率。使用MATLAB2022A版本运行,核心代码通过迭代选择、交叉、变异等操作优化风力机布局。输出包括优化收敛曲线和最佳布局图。遗传算法模拟生物进化机制,通过初始化、选择、交叉、变异和精英保留等步骤,在复杂约束条件下找到最优布局方案,提升风场整体能源产出效率。
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
151 68
基于包围盒的机械臂防碰撞算法matlab仿真
基于包围盒的机械臂防碰撞算法通过构建包围盒来近似表示机械臂及其环境中各实体的空间占用,检测包围盒是否相交以预判并规避潜在碰撞风险。该算法适用于复杂结构对象,通过细分目标对象并逐级检测,确保操作安全。系统采用MATLAB2022a开发,仿真结果显示其有效性。此技术广泛应用于机器人运动规划与控制领域,确保机器人在复杂环境中的安全作业。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等