D 的个人博客   Java/Go/Linux/开源

小而美的 Java 博客系统 Solo
Golang 在线 IDE Wide
黑客与画家的社区 Sym

最小生成树Kruskal

    /**********************************************************************

       文件名: Arc.h
       功能: 图中边类型的声明与实现
       开发平台: Win Xp SP2
       编译环境: CL.exe 8.0 (in Visual Studio 2005 SDK)
       作者: 88250
       完成日期: 2006-11-17    版本: 1.0
       Blog: http://DL88250.ynutx.net
       E-mail: DL88250@gmail.com
       QQ: 845765 or 316281008
                                                                          
     **********************************************************************/

    #ifndef ARC_H
    #define ARC_h

    struct Arc
    {// 边的声明
            // 构造器
            Arc(int vertex1 = 0, int vertex2 = 0, int weight = 0);
            int m_vertex1;          // 顶点1
            int m_vertex2;          // 顶点2
            int m_weight;           // 权值
    };


    Arc::Arc(int vertex1, int vertex2, int weight)
    {// 边结构缺省的构造器
            m_vertex1 = vertex1;
            m_vertex2 = vertex2;
            m_weight = weight;

            return;
    }

    #endif
    /**********************************************************************

       文件名: MFSet.h
       功能: 并查集的声明与实现文件。该并查集使用双亲树作为数据的存储
       开发平台: Win Xp SP2
       编译环境: CL.exe 8.0 (in Visual Studio 2005 SDK)
       作者: 88250
       完成日期: 2006-11-17    版本: 1.0
       Blog: http://DL88250.ynutx.net
       E-mail: DL88250@gmail.com
       QQ: 845765 or 316281008
                                                                          
     **********************************************************************/


    #ifndef MFS_H
    #define MFS_H

    const int maxVerNum = 255;      // 可以计算的最大顶点数
    const int maxArcNum = maxVerNum * (maxVerNum - 1) / 2;// 可以计算的最大边数

    struct PTNode
    {// 节点结构
            PTNode(void){ m_data = 0; m_parent = -1; }
            int m_data;     // 数据域
            int m_parent;   // 双亲位置域,即双亲下标
    };

    struct PTree
    {// 树的双亲表存储表示
            // 插入一个节点item,其双亲是pr指向位置的节点
            void Insert(int item, int pr);
            // 构造器
            PTree(void){ m_num = 0; }
           
            PTNode m_nodes[maxVerNum];      // 存储节点的数组
            int m_num;      // 节点总数
    };

    // 函数名:Insert
    // 功能:插入一个新节点到树中
    // 输入参数:int item:要插入的数据
    //           int pr:该插入数据在树中的双亲位置
    // 输出参数:void
    void PTree::Insert(int item, int pr)
    {
            m_nodes[m_num].m_data = item;
            m_nodes[m_num].m_parent = pr;
            m_num++;

            return;
    }

    class MFSet:public PTree
    {// 并查集声明
            public:
                    // 查找函数。确定item所属子集的下标,
                    // 即item在数组中祖先的下标
                    int Find(int item);
                    // 归并操作。将root2归并到root1中
                    void Merge(int root1, int root2);
    };

    // 函数名:Find
    // 功能:查找item所属子集的下标
    // 输入参数:int item:待查找元素
    // 输出参数:int:item在数组中祖先的下标
    int MFSet::Find(int item)
    {
            int j;

            for (j = item; m_nodes[j].m_parent >= 0;
                 j = m_nodes[j].m_parent)
            {
                    ;
            }

            return j;
    }

    // 函数名:Merge
    // 功能:归并操作,将root1指向元素归并到root2下
    // 输入参数:int root1:指向待归并的元素
    //           int root2:指向归并到元素下标
    // 输出参数:void
    void MFSet::Merge(int root1, int root2)
    {
            m_nodes[root2].m_parent = root1;

            return;
    }

    #endif
    /**********************************************************************

       文件名: Graph.h
       功能: 图类的声明与实现文件
       开发平台: Win Xp SP2
       编译环境: CL.exe 8.0 (in Visual Studio 2005 SDK)
       作者: 88250
       完成日期: 2006-11-17    版本: 1.0
       Blog: http://DL88250.ynutx.net
       E-mail: DL88250@gmail.com
       QQ: 845765 or 316281008
                                                                          
     **********************************************************************/

    #ifndef GRAPH_H
    #define GRAPH_H

    #include "Arc.h"
    #include "MFSet.h"      // 在Kruskal中使用并查集优化
    #include <algorithm>    // Kruskal中的快排,在Prim中使用最小堆优化
    #include <string>
    #include <cstdlib>
    #include <vector>
    #include <fstream>
    #include <iostream>

    using namespace std;

    class Graph
    {// 图类的声明
            public:
                    // 构造器
                    Graph(void);
                    // 从文件中读入图的信息
                    void CreateByFile(const std::string &fileName);
                    // 保存产生的最小生成树到文件
                    void SaveMST(const std::string &fileName);
                    // 显示从文件里读入的图
                    void Display(void)      const;
                    // 利用Kruskal算法产生最小生成树
                    void Kruskal(void);
                    // 利用Prim算法产生最小生成树
                    void Prim(void);
            private:
                    int m_arcNum;                   // 总边数
                    int m_verNum;                   // 总顶点数
                    std::vector<int> m_vertex;      // 保存顶点
                    std::vector<Arc> m_arc;         // 保存边
                    std::vector<Arc> m_MST;         // 保存最小生成树
    };

    Graph::Graph(void)
    {
            m_arcNum = 0;
            m_verNum = 0;

            return;
    }

    // 函数名:SaveMST
    // 功能:将生成的MST存储到文本文件中
    // 输入参数:string fileName:待存的文件名
    // 输出参数:void
    void Graph::SaveMST(const std::string &fileName)
    {
            ofstream fOutput(fileName.c_str());
            if (!fOutput)
            {// 文件打开失败的话退出当前过程
                    cerr << "Error opening output stream" << endl;

                    return;
            }
           
            // 开始存储
            for (vector<Arc>::iterator i = m_MST.begin();
                 i != m_MST.end();
                 i++)
            {
                    fOutput << i->m_vertex1 << ' '
                            << i->m_vertex2 << ' '
                            << i->m_weight << endl;
            }
            fOutput.close();

            return;
    }

    // 函数名:CreateByFile
    // 功能:根据文本文件中的信息建立图
    // 先决条件:文本文件中的信息必须如下存储:
    // 1 2 3
    // 4 5 6
    // 7 8 9
    // 其中第一列为vertex1,第二列为vertex2,第三列为相应的权值
    // 输入参数:string fileName:存储图的文本文件名
    // 输出参数:void
    void Graph::CreateByFile(const string &fileName)
    {
            ifstream fInput(fileName.c_str());

            if (!fInput)
            {
                    cerr << "Error opening input stream" << endl;

                    return;
            }

            int tmpVer = 0;         // 记录一个顶点
            Arc tmpArc;             // 记录一条边
            char aLineInfo[20];     // 从文本里读取一行的信息
            char v1[7];             // 读取边的顶点1
            char v2[7];             // 读取边的顶点2
            char w[5];              // 读取该边的权值
            int i, j;
           
            // 开始读取信息
            while (fInput.getline(aLineInfo, '\r'))
            {
                    // 初始化
                    memset(v1, 0, sizeof(v1));
                    memset(v2, 0, sizeof(v2));
                    memset(w, 0, sizeof(w));
                   
                    // 每行的信息进行分割
                    // 分别取出vertex1, vertex2, weight
                    for (i = 0; ' ' != aLineInfo[i]; i++)
                    {
                            v1[i] = aLineInfo[i];
                    }
                    i++;
                    for (j = 0; ' ' != aLineInfo[i]; j++, i++)
                    {
                            v2[j] = aLineInfo[i];
                    }
                    i++;
                    for (j = 0; aLineInfo[i]; j++, i++)
                    {
                            w[j] = aLineInfo[i];
                    }
                    tmpArc.m_vertex1 = atoi(v1);
                    tmpArc.m_vertex2 = atoi(v2);
                    tmpArc.m_weight = atoi(w);

                    // 插入到边向量中
                    m_arc.push_back(tmpArc);
                   
                    tmpVer = tmpArc.m_vertex1;
                    if (m_vertex.end() == find(m_vertex.begin(),
                                               m_vertex.end(),
                                               tmpVer))
                    {// 不在顶点向量里
                            m_vertex.push_back(tmpVer);
                    }

                    tmpVer = tmpArc.m_vertex2;
                    if (m_vertex.end() == find(m_vertex.begin(),
                                               m_vertex.end(),
                                               tmpVer))
                    {// 不在顶点向量里
                            m_vertex.push_back(tmpVer);
                    }
            }

            fInput.close();

            m_verNum = m_vertex.size();     // 统计顶点数
            m_arcNum = m_arc.size();        // 统计边数

            return;
    }

    // 函数名:Display
    // 功能:显示图在console
    // 格式如下:
    // 1 2 3
    // 4 5 6
    // 7 8 9
    // 其中第一列为vertex1,第二列为vertex2,第三列为相应的权值
    // 输入参数:void
    // 输出参数:void
    void Graph::Display(void)       const
    {
            if (20 > m_arc.size())
            {// 顶点少的时候全部显示出来
                    for (vector<Arc>::const_iterator i = m_arc.begin();
                         i != m_arc.end();
                         i++)
                    {
                            cout << i->m_vertex1 << ' '
                                 << i->m_vertex2 << ' '
                                 << i->m_weight << endl;
                    }
                    cout << endl;
            }
           
            cout << "这个图有" << m_verNum << "个顶点。" << endl;

            return;
    }

    bool MaxWeight(Arc a1, Arc a2)
    {
            return a1.m_weight < a2.m_weight;
    }

    // 函数名:Kruskal
    // 功能:利用Kruskal算法生成MST
    // 输入参数:void
    // 输出参数:void
    void Graph::Kruskal(void)
    {
            vector<Arc> arcVector; // 存放图中的所有根据权升序排列的边
            Arc arc;        // 存入arcVector其中的一条边
            MFSet MFS;      // 定义并查集结构,用于表示当前连通情况
           
            m_MST.clear();  // 清空以前的生成的最小生成树

            // 初始化并查集
            for (int k = 0; k < m_verNum; k++)
            {
                    MFS.Insert(m_vertex[k], -1);    // 每个顶点都初始为一个连通分量
            }

            // 初始化arcVector
            arcVector = m_arc;
           
            // The average of a sort complexity is O(N log N),
            // where N = _Last – _First.
            sort(arcVector.begin(), arcVector.end(), MaxWeight);

            cout << "下面是利用Kruskal算法产生的最小生成树:" << endl;
            int i = 0, v, u;

            while (i < m_arcNum)
            {      
                    // 从vector中退出一条边
                    arc = arcVector[i];
                    // 取两个顶点所在的等价类的根
                    u = MFS.Find(arc.m_vertex1);
                    v = MFS.Find(arc.m_vertex2);

                    if (u != v)
                    {// 说明该边不连通
                            cout << arc.m_vertex1 << " " << arc.m_vertex2
                                 << " " << arc.m_weight << endl;
                            m_MST.push_back(arc);   // 插入到MST中
                            MFS.Merge(u, v);        // 合并等价类
                    }
            i++;    // 处理下一条边
            }
    }

    void Graph::Prim(void)
    {
            Arc arc;

            m_MST.clear();  // 清空以前的生成的最小生成树
           

          

            return;
    }

    #endif
    /**********************************************************************

       文件名: GenGraphTXT.cpp
       功能: 生成一个完全无向网的文本表示文件
       开发平台: Win Xp SP2
       编译环境: CL.exe 8.0 (in Visual Studio 2005 SDK)
       作者: 88250
       完成日期: 2006-11-17    版本: 1.0
       Blog: http://DL88250.ynutx.net
       E-mail: DL88250@gmail.com
       QQ: 845765 or 316281008
                                                                          
     **********************************************************************/

    #include "Graph.h"
    #include <iostream>
    #include <fstream>
    #include <cstdlib>
    #include <ctime>
    #include <vector>

    using namespace std;

    int main(int argc, char *argv[])
    {
            int vertexNum = 0;
            vector<Arc> arc;

            cout << "Please input the number of the vertex: ";
            cin >> vertexNum;
           
            srand(time(NULL));

            for (int i = 1; i <= vertexNum; i++)
            {
                    for (int j = i + 1; j <= vertexNum; j++)
                    {
                            arc.push_back(Arc(i, j,
                                    ((double)rand() / (double)RAND_MAX)
                                      * 20 + 1));
                    }
            }

           
            for (vector<Arc>::iterator i = arc.begin();
                 i != arc.end();
                 i++)
            {
                    cout << i->m_vertex1 << ' '
                         << i->m_vertex2 << ' '
                         << i->m_weight << endl;
            }

            ofstream fOutput("MST_Test1.txt");
            if (!fOutput)
            {
                    cerr << "Error opening output stream" << endl;

                    return 0;
            }

            for (vector<Arc>::iterator i = arc.begin();
                 i != arc.end();
                 i++)
            {
                    fOutput << i->m_vertex1 << ' '
                            << i->m_vertex2 << ' '
                            << i->m_weight << endl;
            }
            fOutput.close();

            return 0;
    }

    /**********************************************************************

       文件名: TestGraph.cpp
       功能: 图的测试文件,重点是测试Kruskal算法
       开发平台: Win Xp SP2
       编译环境: CL.exe 8.0 (in Visual Studio 2005 SDK)
       作者: 88250
       完成日期: 2006-11-17    版本: 1.0
       Blog: http://DL88250.ynutx.net
       E-mail: DL88250@gmail.com
       QQ: 845765 or 316281008

     **********************************************************************/

    #include "Graph.h"

    int main(void)
    {
            Graph myGraph;

            myGraph.CreateByFile("MST_Test1.txt");
            myGraph.Display();
            myGraph.Kruskal();
            myGraph.SaveMST("MST.txt");

            return 0;
    }

    嗯。。。。就这些了。。。。

    validate