亚线性时间算法求连通分量

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

### 要求 ###

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

### 简述算法过程 ###

先用一个队列，建立一个广度搜索树，取样，则n/(取样倒数和)  
同一个连通分量中的每一个点的 1 /n v是一样的，都是分量中点的个数的倒数  
就是一个小型的搜索，如果搜索到的点的个数小于 2/ ϵ 就继续搜索，否则直接返回 2/ ϵ

### 代码 ###

#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 50
    
    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 < 20; 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;
        }
    
        int run(Env env)
        {
        
            //在此写入你的代码  env.graph 为目标矩阵
            Queue M;
            InitQueue(&M);
            double p = 0.1;
            double q[11];
            double a;
            a = 2 / p;
            srand((unsigned)time(NULL));
            for (int k = 1; k < 11; k++) 
            {
        
                InitQueue(&M);
                int visited[20];
                for (int m = 0; m < 20; m++)
                    visited[m] = 0;
                int i = rand() % 20;
                visited[i] = 1;
                EnQueue(&M, i);
                double t = 1;
                while (!QueueEmpty(&M))
                {
        
                    i = DeQueue(&M);
                    for (int j = 0; j < 20; j++)
                    {
        
                        if (double(j) <= double(a))
                        {
        
                            if (env.graph[i][j] != 0 && visited[j] == 0)
                            {
        
                                t = double(t + 1);
                                visited[j] = 1;
                                EnQueue(&M, j);
                            }
                        }
                    }
                }
    
                if (t != 0)
                {
        
                    q[k] = double(1 / t);
                }
                else
                {
        
                    q[k] = 0;
                }
            }
            double sum;
            for (int k = 1; k < 11; k++)
            {
        
                sum = q[k] + sum;
            }
            sum = sum / 10 * 20;
            cout << sum << 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;
    }

### 结果 ###

![在这里插入图片描述][f375111d4b954fe6bbcdfb1719d3c924.png]  
![在这里插入图片描述][95c77ce3b47f48e6a58226c8f1748b80.png]

[dd0ccf27d8874022b9aab3a6a96f7c07.png]: https://img-blog.csdnimg.cn/dd0ccf27d8874022b9aab3a6a96f7c07.png
[f375111d4b954fe6bbcdfb1719d3c924.png]: https://img-blog.csdnimg.cn/f375111d4b954fe6bbcdfb1719d3c924.png
[95c77ce3b47f48e6a58226c8f1748b80.png]: https://img-blog.csdnimg.cn/95c77ce3b47f48e6a58226c8f1748b80.png