亚线性的近似最小支撑树

╰半夏微凉° 2023-10-06 21:36 21阅读 0赞

### 问题 ###

![在这里插入图片描述][986cbc9b9e58469386148450ef2e9cdd.png]  
自己给出ϵ的值并带入计算

### 算法过程 ###

![在这里插入图片描述][6c45338f508d4541881373ddab5ee166.png]

### 代码 ###

#include <iostream>
    #include <string>
    #include <fstream>
    #include <vector>
    #include <queue>
    #include <ctime>
    #include <algorithm>
    #include <sstream>
    #include <stdlib.h>
    #include <time.h>
    using namespace std;
    #define QueueSize 1000
    
    class Env
    {
        
    public:
        vector<vector<int>> graph;
        Env()
        {
        
            graph = getGraph("rand2_2.csv"); //rand1_1.csv rand1_2.csv rand1_3.csv rand2_1.csv rand2_2.csv 共5个测试用例
        }
    
        vector<vector<int>> getGraph(string file_path)
        {
        
            vector<vector<int>> user_arr;
            ifstream fp(file_path);
            string line;
            while (getline(fp, line))
            {
        
                vector<int> data_line;
                string number;
                istringstream readstr(line);
                for (int j = 0; j < 33; j++)
                {
        
                    getline(readstr, number, ',');
                    data_line.push_back(atoi(number.c_str()));
                }
                user_arr.push_back(data_line);
            }
            return user_arr;
        }
    };
    
    // 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数
    class Algo
    {
        
    public:
        Algo()
        {
        
            cout << "algo ok" << endl;
        }
    
        typedef struct
        {
        
            int front;
            int rear;
            int count;
            int data[QueueSize];
        } Queue;
    
        void InitQueue(Queue *M)
        {
        
            M->front = M->rear = 0;
            M->count = 0;
        }
    
        int QueueEmpty(Queue *M) 
        {
        
            if (M->count == 0)
                return 1;
            else
                return 0;
        }
    
        void EnQueue(Queue *M, int x) 
        {
        
            M->count++;
            M->data[M->rear] = x;
            M->rear = (M->rear + 1) % QueueSize;
        }
    
        int DeQueue(Queue *M) 
        {
        
            int temp;
            temp = M->data[M->front];
            M->count--;
            M->front = (M->front + 1) % QueueSize;
            return temp;
        }
        double cnum(vector<vector<int>> graph)
        {
        
            Queue M;
            InitQueue(&M);
            double a = 0.1;
            double b[1000];
            double n;
            n = 2 / a;
            srand((unsigned)time(NULL));
            for (int k = 1; k < 61; k++) //取样60个数
            {
        
                InitQueue(&M);
                int visited[33];
                for (int m = 0; m < 33; m++)
                    visited[m] = 0;
                int i = rand() % 33;
                visited[i] = 1;
                EnQueue(&M, i);
                double t = 1;
                while (!QueueEmpty(&M))
                {
        
                    i = DeQueue(&M);
                    for (int j = 0; j < 33; j++)
                    {
        
                        if (double(j) <= double(n))
                        {
        
                            if (graph[i][j] > 0 && visited[j] == 0)
                            {
        
                                t = double(t + 1);
                                visited[j] = 1;
                                EnQueue(&M, j);
                            }
                        }
                    }
                }
    
                if (t != 0)
                {
        
                    b[k] = double(1 / t);
                }
                else
                {
        
                    b[k] = 0;
                }
            }
            double sum;
            for (int k = 1; k < 61; k++)
            {
        
                sum = b[k] + sum;
            }
            sum = sum / 60 * 33;
            cout << "连通分量：" << sum << endl;
            return sum;
        }
        int run(Env env)
        {
        
            //在此写入你的代码  env.graph 为目标矩阵
            int w = 0;
            for (int i = 1; i < 33; i++)
            {
        
                for (int j = 0; j < 33; j++)
                {
        
                    if (w < env.graph[i][j])
                    {
        
                        w = env.graph[i][j];
                    }
                }
            }
            cout << "最大权重:" << w << endl;
            double sums, W;
            double n = 33;
            for (int n = 0; n < w-1; n++)
            {
        
                for (int i = 0; i < 33; i++)
                {
        
                    for (int j = 0; j < 33; j++)
                    {
        
                        if (env.graph[i][j] = w - n)
                        {
        
                            env.graph[i][j] == 0;
                        }
                    }
                }
                sums = double(sums + cnum(env.graph));
            }
            cout <<"连通分量总和"<< sums << endl;
            W = double(n - w + sums);
            cout << "最优解:" << W << endl;
    
            return 0; //修改为返回正确的结果
        }
    };
    
    int main()
    {
        
        Algo algo;
        Env env;
        time_t start = clock();
        algo.run(env);
        time_t end = clock();
        cout << "程序耗时: " << double(end - start) / CLOCKS_PER_SEC << " ms" << endl;
        cout << "占用内存：" << sizeof(algo) << " byte" << endl;
        return 0;
    }

### 结果 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_13_color_FFFFFF_t_70_g_se_x_16]

[986cbc9b9e58469386148450ef2e9cdd.png]: https://img-blog.csdnimg.cn/986cbc9b9e58469386148450ef2e9cdd.png
[6c45338f508d4541881373ddab5ee166.png]: https://img-blog.csdnimg.cn/6c45338f508d4541881373ddab5ee166.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Y-r5oiR6ICB5Lyv_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/18ab03749c964bea802b1184ac18ff92.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Y-r5oiR6ICB5Lyv,size_13,color_FFFFFF,t_70,g_se,x_16