魏晓东 发表于 2025-4-12 03:14:33

[数据结构]图krusakl算法实现

Kruskal算法

我们要在连通图中去找生成树
连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。如果图中恣意一对顶点都是连通的，则称此图为连通图。
生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。也就是用最少的边（n-1条边）连通起来。
最小生成树：构成生成树的这些边加起来权值最小，也就是最小的成本让这N个顶点连通，最小生成树不唯一。
连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从此中删去任何一条边，生成树就不在连通；反之，在此中引入任何一条新边，都会形成一条回路。
若连通图由n个顶点构成，则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条：

[*]只能利用图中的权值最小的边来构造最小生成树
[*]只能利用恰恰n-1条边来连接图中的n个顶点
[*]选用的n-1条边不能构成回路
构造最小生成树的方法：Kruskal算法和Prim算法。这两个算法都接纳了逐步求解的贪婪策略。
贪婪算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪婪算法做出的不是团体最优的的选择，而是某种意义上的局部最优解。贪婪算法不是对全部的问题都能得到团体最优解。
Kruskal算法和Prim算法求出来的肯定是最优解吗？——不肯定
https://i-blog.csdnimg.cn/blog_migrate/a9d7c46158ab904efc0766b48abc738f.png
因此要选出最小的边，然后举行连接
在这里判定是否成环的关键是并查集
代码实现：
W Kruskal(Self& minTree)
{
        minTree._vertexs = _vertexs;
        minTree._indexMap = _indexMap;
        minTree._matrix.resize(_vertexs.size());
        for (auto& e : minTree._matrix)
        {
                e.resize(_vertexs.size(), MAX_W);
        }


        // 先根据边的权值进行排序
        priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
        for (size_t i = 0; i < _vertexs.size(); ++i)
        {
                for (size_t j = 0; j < _vertexs.size(); ++j)
                {
                        if (i < j && _matrix != MAX_W)
                        {
                                // pq.push(_matrix); 不是这样
                                pq.push(Edge(i, j, _matrix));
                        }
                }
        }
        W total = W();
        size_t i = 1; // 最初有一个顶点
        // 从最小的边开始进行选择（贪心）
        UnionFindSet ufs(_vertexs.size());
        while (i < _vertexs.size() && !pq.empty())
        {
                Edge min = pq.top();
                pq.pop();

                // 判断是否会构成一个回路，不会则添加到最小生成树中
                if (ufs.FindRoot(min._srci) != ufs.FindRoot(min._dsti))
                {
                        cout << _vertexs << "-" << _vertexs << ":" << _matrix << endl;
                        minTree._AddEdge(min._srci, min._dsti, min._w);
                        total += min._w;
                        ufs.Union(min._srci, min._dsti);
                        ++i;
                }
        }
        if (i == _vertexs.size())
        {
                return total;
        }
        else
        {
                return W();
        }
}
完整代码：
namespace matrix // 领接矩阵存储
{
        template <class V, class W, W MAX_W = INT_MAX, bool Direction = false> // Vertex, Weight, Direction表示有向图还是无向图
        class Graph
        {
                typedef Graph<V, W, MAX_W, Direction> Self; // 表示子图
        public:
                Graph()
                {}

                Graph(const V* vertex, size_t n)
                {
                        _vertexs.reserve(n);
                        for (size_t i = 0; i < n; ++i)
                        {
                                _vertexs.push_back(vertex);
                                _indexMap] = i; // map<V, int>second存的是对应的编号
                        }

                        _matrix.resize(n);
                        for (int i = 0; i < n; ++i)
                        {
                                _matrix.resize(n, MAX_W);
                        }
                }
               
                size_t GetVertexIndex(const V& v)
                {
                        auto ret = _indexMap.find(v);
                        if (ret != _indexMap.end())
                        {
                                return ret->second;
                        }
                        else
                        {
                                assert(false);
                                return -1;
                        }
                }

                void AddEdge(const V& src, const V& dst, const W& w)
                {
                        size_t srci = GetVertexIndex(src);
                        size_t dsti = GetVertexIndex(dst);
                        _AddEdge(srci, dsti, w);
                }
               
                void _AddEdge(size_t srci, size_t dsti, const W& w)
                {
                        _matrix = w;
                        if (Direction == false)
                        {
                                _matrix = w;
                        }
                }

                void Print()
                {
                        // 顶点
                        for (size_t i = 0; i < _vertexs.size(); ++i)
                        {
                                cout << "[" << i << "]" << "->" << _vertexs << endl;
                        }
                        cout << endl;

                        // 矩阵
                        // 横下标
                        cout << "";
                        for (size_t i = 0; i < _vertexs.size(); ++i)
                        {
                                //cout << i << " ";
                                printf("%4d", i);
                        }
                        cout << endl;

                        for (size_t i = 0; i < _matrix.size(); ++i)
                        {
                                cout << i << " "; // 竖下标
                                for (size_t j = 0; j < _matrix.size(); ++j)
                                {
                                        //cout << _matrix << " ";
                                        if (_matrix == MAX_W)
                                        {
                                                //cout << "* ";
                                                printf("%4c", '*');
                                        }
                                        else
                                        {
                                                //cout << _matrix << " ";
                                                printf("%4d", _matrix);
                                        }
                                }
                                cout << endl;
                        }
                        cout << endl;
                }

                void BFS(const V& src)
                {
                        size_t srci = GetVertexIndex(src);

                        // 队列和标记数组
                        queue<int> q;
                        vector<bool> visited(_vertexs.size(), false); // 标记数组
                        int levelSize = 1; // 保证一层 一层的打印
                        q.push(srci);
                        visited = true;

                        size_t n = _vertexs.size();
                        while (!q.empty())
                        {
                                for (int i = 0; i < levelSize; ++i)
                                {
                                        int front = q.front();
                                        q.pop();
                                        cout << front << ":" << _vertexs << " ";
                                        // 把front顶点的邻接顶点入队列
                                        for (size_t i = 0; i < n; ++i)
                                        {
                                                if (_matrix != MAX_W) // 不是无穷大就是相连的
                                                {
                                                        if (visited == false)
                                                        {
                                                                q.push(i);
                                                                visited = true;
                                                        }
                                                }
                                        }
                                }
                                cout << endl;
                                levelSize = q.size(); // 下一层的数据个数
                        }
                        cout << endl;
                }

                void _DFS(size_t srci, vector<bool> visited)
                {
                        cout << srci << ":" << _vertexs << endl;
                        visited = true;
                        // 找srci相邻的没有访问过的点，深度遍历
                        for (size_t i = 0; i < _vertexs.size(); ++i)
                        {
                                if (_matrix != MAX_W && visited = false)
                                {
                                        _DFS(i, visited);
                                }
                        }
                }

                void DFS(const V& src)
                {
                        size_t srci = GetVertexIndex(src);
                        vector<bool> visited(_vertexs.size(), false);
                        _DFS(srci, visited);
                }

                struct Edge
                {
                        size_t _srci;
                        size_t _dsti;
                        W _w;

                        Edge(size_t srci, size_t dsti, const W& w)
                                : _srci(srci)
                                , _dsti(dsti)
                                , _w(w)
                        {}

                        bool operator>(const Edge& e) const
                        {
                                return _w > e._w;
                        }
                };

                W Kruskal(Self& minTree)
                {
                        minTree._vertexs = _vertexs;
                        minTree._indexMap = _indexMap;
                        minTree._matrix.resize(_vertexs.size());
                        for (auto& e : minTree._matrix)
                        {
                                e.resize(_vertexs.size(), MAX_W);
                        }


                        // 先根据边的权值进行排序
                        priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
                        for (size_t i = 0; i < _vertexs.size(); ++i)
                        {
                                for (size_t j = 0; j < _vertexs.size(); ++j)
                                {
                                        if (i < j && _matrix != MAX_W)
                                        {
                                                // pq.push(_matrix); 不是这样
                                                pq.push(Edge(i, j, _matrix));
                                        }
                                }
                        }
                        W total = W();
                        size_t i = 1; // 最初有一个顶点
                        // 从最小的边开始进行选择（贪心）
                        UnionFindSet ufs(_vertexs.size());
                        while (i < _vertexs.size() && !pq.empty())
                        {
                                Edge min = pq.top();
                                pq.pop();

                                // 判断是否会构成一个回路，不会则添加到最小生成树中
                                if (ufs.FindRoot(min._srci) != ufs.FindRoot(min._dsti))
                                {
                                        cout << _vertexs << "-" << _vertexs << ":" << _matrix << endl;
                                        minTree._AddEdge(min._srci, min._dsti, min._w);
                                        total += min._w;
                                        ufs.Union(min._srci, min._dsti);
                                        ++i;
                                }
                        }
                        if (i == _vertexs.size())
                        {
                                return total;
                        }
                        else
                        {
                                return W();
                        }
                }

        private:
                vector<V> _vertexs; // 顶点集合
                map<V, int> _indexMap; // 顶点映射下标
                vector<vector<W>> _matrix;// 存储边的关系
        };

        void TestGraph()
        {
                Graph<char, int, INT_MAX, true> g("0123", 4);
                g.AddEdge('0', '1', 1);
                g.AddEdge('0', '3', 4);
                g.AddEdge('1', '3', 2);
                g.AddEdge('1', '2', 9);
                g.AddEdge('2', '3', 8);
                g.AddEdge('2', '1', 5);
                g.AddEdge('2', '0', 3);
                g.AddEdge('3', '2', 6);
                g.Print();
        }

        void TestBDFS()
        {
                string a[] = { "张三", "李四", "王五", "赵六", "周七" };
                Graph<string, int> g1(a, sizeof(a) / sizeof(string));
                g1.AddEdge("张三", "李四", 100);
                g1.AddEdge("张三", "王五", 200);
                g1.AddEdge("王五", "赵六", 30);
                g1.AddEdge("王五", "周七", 30);
                g1.Print();

                g1.BFS("张三");
        }

        void TestGraphMinTree()
        {
                const char* str = "abcdefghi";
                Graph<char, int> g(str, strlen(str));
                g.AddEdge('a', 'b', 4);
                g.AddEdge('a', 'h', 8);
                //g.AddEdge('a', 'h', 9);
                g.AddEdge('b', 'c', 8);
                g.AddEdge('b', 'h', 11);
                g.AddEdge('c', 'i', 2);
                g.AddEdge('c', 'f', 4);
                g.AddEdge('c', 'd', 7);
                g.AddEdge('d', 'f', 14);
                g.AddEdge('d', 'e', 9);
                g.AddEdge('e', 'f', 10);
                g.AddEdge('f', 'g', 2);
                g.AddEdge('g', 'h', 1);
                g.AddEdge('g', 'i', 6);
                g.AddEdge('h', 'i', 7);

                Graph<char, int> kminTree;
                cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
                //kminTree.Print();

                /*Graph<char, int> pminTree;
                cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
                pminTree.Print();*/
        }
}

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页: [1]
查看完整版本: [数据结构]图krusakl算法实现