使用 C++ 和 Boost 库计算图的节点度和模块 - 贪心算法示例

以下是一个使用 C++ 和 Boost 库的示例代码，用于读取邻接矩阵并计算每个节点的度、使用贪心算法计算每个节点所属的模块，并将结果输出。

#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/connected_components.hpp>

using namespace std;

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph;

// 读取邻接矩阵，构建图
void buildGraph(Graph& g, const vector<vector<int>>& adjacencyMatrix) {
    int numNodes = adjacencyMatrix.size();
    for (int i = 0; i < numNodes; i++) {
        for (int j = i + 1; j < numNodes; j++) {
            if (adjacencyMatrix[i][j] == 1) {
                boost::add_edge(i, j, g);
            }
        }
    }
}

// 计算每个节点的度
vector<int> calculateDegrees(const Graph& g) {
    int numNodes = boost::num_vertices(g);
    vector<int> degrees(numNodes);
    for (int i = 0; i < numNodes; i++) {
        degrees[i] = boost::degree(i, g);
    }
    return degrees;
}

// 使用贪心算法计算每个节点所属的模块
vector<int> calculateModules(const Graph& g) {
    int numNodes = boost::num_vertices(g);
    vector<int> modules(numNodes);
    vector<int> component(numNodes);
    int numComponents = boost::connected_components(g, &component[0]);
    for (int i = 0; i < numNodes; i++) {
        modules[i] = component[i];
    }
    return modules;
}

// 输出结果
void printResult(const vector<int>& degrees, const vector<int>& modules) {
    int numNodes = degrees.size();
    cout << "Node\tDegree\tModule" << endl;
    for (int i = 0; i < numNodes; i++) {
        cout << i << "\t" << degrees[i] << "\t" << modules[i] << endl;
    }
}

int main() {
    // 读取邻接矩阵
    vector<vector<int>> adjacencyMatrix = {
        {0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 0, 0, 1},
        {0, 1, 0, 0, 1},
        {0, 0, 1, 1, 0}
    };

    // 构建图
    Graph g;
    buildGraph(g, adjacencyMatrix);

    // 计算每个节点的度
    vector<int> degrees = calculateDegrees(g);

    // 使用贪心算法计算每个节点所属的模块
    vector<int> modules = calculateModules(g);

    // 输出结果
    printResult(degrees, modules);

    return 0;
}

这个示例代码假设邻接矩阵已经给定，以一个无向图为例。通过buildGraph函数将邻接矩阵转换为图的形式。然后使用calculateDegrees函数计算每个节点的度，使用calculateModules函数使用贪心算法计算每个节点所属的模块。最后，通过printResult函数将结果输出。