最小生成树的目标是把本来一个包含n个节点的二维图结构,用n-1条边连接起来,并且这些边的长度总和最小。
与dijkstra算法有点类似,假设图中有顶点V={A,B,C,D,E,F},我们要生成最小生成树。准备两个集合S_frozeen={},S_inactive={A,B,C,D,E,F},S_frozeen我们称之为源,
最小生成树prim算法流程为:每次提取S_inactive中离源S_frozeen最小的边(这边需要主要dijkstra是离源距离最小的点)对应的顶点,添加到源S_frozeen中,n个顶点,需要添加n次,直到S_inactive为空为止。与dijkstra算法的区别在于dijkstra算法每次比较更新
nodes[j].distance_to_src>graph[min_index][j]+nodes[min_index].distance_to_src;
而最小生成树只需要每次比较更新:
nodes[j].distance_to_src>graph[min_index][j]
其他的都不变。
示例:https://www.jianshu.com/p/efcd21494dff
数据结构最小生成树。根据前面的博文我们写过的dijkstra算法,只需要修改一行代码,就可以实现了。
#include <vector>
#include <limits>using namespace std;
class min_tree{
public:min_tree(){};~min_tree(){};class node{public:node(){S_flag= false;distance_to_src=1e5;pre_node=-1;};~node(){};bool S_flag;int pre_node;int distance_to_src;};//求0号定点到1,2,3,4,5定点的最短路径std::vector<std::vector<int>> example_graph(){float max_number=1e5;int node_number=6;std::vector<std::vector<int>>graph(node_number);for (int i = 0; i <graph.size() ; ++i) {graph[i].resize(node_number,max_number);}graph[0][1]=7;graph[0][2]=4;graph[1][0]=7;graph[1][2]=6;graph[1][3]=2;graph[1][5]=4;graph[2][0]=4;graph[2][1]=6;graph[2][4]=9;graph[2][5]=8;graph[3][1]=2;graph[3][5]=7;graph[4][2]=9;graph[4][5]=1;graph[5][1]=4;graph[5][2]=8;graph[5][3]=7;graph[5][4]=1;return graph;}void main(){std::vector<std::vector<int>>graph=example_graph();int n=graph.size();std::vector<node>nodes(n);nodes[0].distance_to_src=0;for (int step = 0; step <n ; ++step) {//S_inactive中有n个顶点,要每次提取一个点离S_frozeen最近的点扔到源中,直到S_inactive为空,所以需要遍历n次//第一步:寻找S_inactive中离源最近的点id号min_indexint min_dist=1e5;int min_index=-1;for (int j = 0; j <n ; ++j) {if(!nodes[j].S_flag)//S_inactive中的点{if(nodes[j].distance_to_src<min_dist){min_dist=nodes[j].distance_to_src;min_index=j;}}}if(min_index<0)break;//第二步:添加min_index到S_frozeen中,并更新S_inactive到源S_frozeen的距离(只需要更新min_index的邻居顶点就可以了)nodes[min_index].S_flag=true;//添加到S_frozeenfor (int j = 0; j < n; ++j) {//更新S_inactive到源S_frozeen的距离if (!nodes[j].S_flag){int new_idst=graph[min_index][j];if(nodes[j].distance_to_src>new_idst){nodes[j].distance_to_src=new_idst;nodes[j].pre_node=min_index;}}}}char str[]={'a','b','c','d','e','f'};for (int i = 0; i <n ; ++i) {std::cout<<str[i]<<","<<str[nodes[i].pre_node]<<std::endl;}}};
结果最小生成树的边为:a-c、b-c、b-f、b-d、f-e
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态