0

我对代码的解释如下 -

  1. 函数 remove sl 最初删除图中的自循环。
  2. 函数 adjacency_list 以邻接表的形式读取输入文本文件并创建向量映射。地图中的每个键都充当节点，每个向量也是它相邻的节点列表。

该算法在函数 mincut 中实现。

  1. 当节点的数量大于两个时，它会先选择一个节点，然后再选择另一个节点来有效地选择一条随机边。
  2. 如果与节点 2 相邻的所有节点不为零或节点 1 本身，则将它们添加到节点 1 的列表中。
  3. 在 node1 的列表中 node2 的条目为零，因此也有效地消除了自循环。
  4. 任何其他等于 node2 的条目都等于 node1，因为该节点现在连接到 node1。
  5. Node2 从地图中移除。
  6. 在 while 循环之后，计算第一个节点中的所有非零条目以给出最小切割。

我注意到的一个错误是，在 mincut 步骤三中没有反映在图表中。否则我无法找到我出错的地方。

#include <iostream>
#include <vector>
#include <map>
#include <bits/stdc++.h>
#include <fstream>
#include <sstream>

using namespace std;

map <int, vector<int>> adjacency_list (string &file);
map <int, vector <int>> removesl (map <int, vector <int>> &graph);
int mincut (map <int, vector <int>> &graph);

int main ()
{
    string s = "graph.txt";
    int min = 100000000;
    map <int, vector<int>> graph = adjacency_list (s);
    graph = removesl(graph);
    for (int i = 1; i <= 1000; i++)
    {
        int min_cut = mincut (graph);
        if (min_cut < min)
            min = min_cut;
    }
    cout << min;
}


map <int, vector<int>> adjacency_list (string &file)
{
    map <int, vector <int>> graph;
    ifstream ifile (file);
    string line;
    int a,b;
    while(getline (ifile, line))
    {
        istringstream iss (line);
        iss >> a;
        graph [a] = vector<int>();
        while (iss >> b)
        {
            graph [a].push_back(b);
        }
    }
    return graph;
}

map <int, vector <int>> removesl (map <int, vector <int>> &graph)
{
    for (int i = 1; i <= graph.size(); i++)
    {
        for (int j = 0; j < graph[i].size(); j++)
        {
            if(graph[i][j] == i)
                graph[i][j] = 0;
        }
    }
    return graph;
}

int mincut (map <int, vector <int>> &graph)
{
    while (graph.size() > 2)
    {
        int node1 = (rand() % 200) + 1;
        if (graph.find(node1) == graph.end())
            continue;
        int size = graph [node1].size();
        int index = (rand() % size);
        int node2 = graph [node1][index];
        for (int i = 0; i < graph[node2].size(); i++)
        {
            if (graph[node2][i] != node1 && graph[node2][i] != 0)
                graph[node1].push_back(graph[node2][i]);
        }
        for (int i = 0; i < graph[node1].size(); i++)
        {
            if (graph[node1][i] == node2)
                graph[node1][i] = 0;
        }
        graph.erase(node2);
        for (auto i : graph)
        {
            for (int j = 0; j < i.second.size(); j++)
            {
                if (i.second[j] == node2)
                    i.second[j] = node1;
            }
        }
    }
    auto it = graph.begin();
    int count = 0;
    for (int i = 0; i < it -> second.size(); i++)
    {
        if (it -> second[i] != 0)
            count++;
    }
    return count;
}
4

0 回答 0