求分布式最大独立集贪心算法C++实现及编译问题求助

编译报错解决 #

从你提供的报错信息来看，问题源于C++版本不兼容：

• nullptr 和 to_string 是C++11引入的特性，旧版本编译器默认不支持
• 编译时添加C++标准参数即可修复：

  g++ -std=c++11 你的源文件.cpp -o 可执行文件名
  

  也可以用更高版本标准（如C++17），参数替换为-std=c++17

分布式最大独立集贪心算法简化实现 #

以下是基于本地决策的分布式最大独立集贪心算法实现，模拟节点间通信逻辑：

#include <iostream>
#include <vector>
#include <unordered_set>

// 分布式节点类
class Node {
private:
    int id;
    std::vector<int> neighbors;
    bool in_independent_set = false;
    bool is_active = true;

public:
    Node(int node_id, const std::vector<int>& neighs) : id(node_id), neighbors(neighs) {}

    // 本地决策：和活跃邻居比较ID，最大ID节点加入独立集
    void make_decision(const std::unordered_set<int>& active_neighbors) {
        if (!is_active) return;

        int max_id = id;
        for (int neigh_id : active_neighbors) {
            if (neigh_id > max_id) max_id = neigh_id;
        }

        if (max_id == id) {
            in_independent_set = true;
            is_active = false;
        } else {
            // 若有更大ID的邻居活跃，当前节点被排除
            for (int neigh_id : neighbors) {
                if (neigh_id == max_id) {
                    is_active = false;
                    break;
                }
            }
        }
    }

    bool is_in_independent_set() const { return in_independent_set; }
    int get_id() const { return id; }
    bool get_active_status() const { return is_active; }
    const std::vector<int>& get_neighbors() const { return neighbors; }
};

int main() {
    // 构建示例图：节点0连1、2；节点1连0、3；节点2连0、3；节点3连1、2
    std::vector<Node> nodes = {
        Node(0, {1, 2}),
        Node(1, {0, 3}),
        Node(2, {0, 3}),
        Node(3, {1, 2})
    };

    bool has_active_nodes = true;
    while (has_active_nodes) {
        has_active_nodes = false;
        std::unordered_set<int> active_node_ids;

        // 收集当前活跃节点ID
        for (const auto& node : nodes) {
            if (node.get_active_status()) {
                active_node_ids.insert(node.get_id());
                has_active_nodes = true;
            }
        }

        if (!has_active_nodes) break;

        // 模拟分布式并行决策
        std::vector<Node> new_nodes = nodes;
        for (size_t i = 0; i < nodes.size(); ++i) {
            const Node& current_node = nodes[i];
            if (!current_node.get_active_status()) continue;

            std::unordered_set<int> active_neighbors;
            for (int neigh_id : current_node.get_neighbors()) {
                if (active_node_ids.count(neigh_id)) {
                    active_neighbors.insert(neigh_id);
                }
            }

            new_nodes[i].make_decision(active_neighbors);
        }

        nodes = std::move(new_nodes);
    }

    // 输出结果
    std::cout << "最大独立集包含的节点ID：";
    for (const auto& node : nodes) {
        if (node.is_in_independent_set()) {
            std::cout << node.get_id() << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}

其他分布式图算法实现思路 #

若需要其他分布式图算法（如分布式BFS、分布式最小生成树），核心逻辑一致：

• 每个节点维护本地状态
• 通过与邻居交换信息完成本地决策
• 迭代至全局状态收敛

编译上述代码时，同样需指定C++11及以上标准：

g++ -std=c++11 mis_distributed.cpp -o mis_distributed

内容的提问来源于stack exchange，提问作者Subhra Mazumdar