数据结构(十七)最小生成树

￡神魔★判官ぃ 2022-05-31 14:16 172阅读 0赞

最小生成树的目标是把本来一个包含n个节点的二维图结构，用n-1条边连接起来，并且这些边的长度总和最小。

### **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\]

其他的都不变。

### **2 代码实现** ###

示例：[https://www.jianshu.com/p/efcd21494dff][https_www.jianshu.com_p_efcd21494dff]

![20180227111723505][]

根据前面的博文我们写过的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_index
                int 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_frozeen
                for (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

![20180227111736404][]

[https_www.jianshu.com_p_efcd21494dff]: https://www.jianshu.com/p/efcd21494dff
[20180227111723505]: /images/20220531/de12101c05d04e269eaa2d5ed7cca171.png
[20180227111736404]: /images/20220531/89cfbba96b024c0bafd2882d9c38d197.png