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

最小生成树的目标是把本来一个包含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

 

根据前面的博文我们写过的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