C.

  • Figure of BFS

In social networks, individuals or units (nodes) are connected by relationships (edges). They are influenced by these relationships, which can be understood as a spreading interaction between connected nodes in the network, which can be enhanced or weakened. The importance of nodes in the network varies according to their different positions. “Closeness centrality” is used to measure the “speed” of a node reaching other nodes, that is, a node with a higher centrality can reach other nodes in the network faster (in the average sense) than a node with a lower centrality, so it has more important value in the transmission process of the network. In a network with N nodes, Cc(vi) of node vi is mathematically defined as the reciprocal of the mean value of the shortest distance D (vi,vj) between vi and all other nodes vj (j≠ I) : For an unconnected graph, the centrality of compactness of all nodes is 0. Given an undirected graph with no authority and a set of nodes in it, calculate the centrality of compactness of each node in this set of nodes.

Flyod algorithm can not be used because there are 104 points in the path given by the question. In addition, when saving the graph, the adjacency list should be used, and the adjacency matrix should not be used, because the memory will exceed.

Then we use BFS for traversal. Since the length of all paths is 1, the calculation using BFS can be directly regarded as different layers, and the length of each layer increases by 1. If the points traversed in the end are not enough n-1, it means that some points cannot be reached, which is an unconnected graph.

The complete code is as follows:

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

#define maxn 10010

vector<int> G[maxn]; // Graph G, 1 indicates connected, 0 indicates disconnected
bool vis[maxn];

double BFS(int start, int N)
{
    fill(vis, vis + maxn, false);
    queue<int> Q;
    int dis[N + 1], visit = 0; // Distance, number of points accessed
    double sumDis = 0.0;
    vis[start] = true;
    Q.push(start);
    dis[start] = 0;
    while (Q.size(a) >0)
    {
        int cur = Q.front(a); Q.pop(a);int nextId;
        for (int i = 0; i < G[cur].size(a); i++) { nextId = G[cur][i];if(vis[nextId] == false)
            {
                Q.push(nextId);
                dis[nextId] = dis[cur] + 1;
                sumDis += dis[nextId];
                visit++;
                vis[nextId] = true; }}}double result = (double)(N - 1) / sumDis;
    if(visit ! = N -1)
        return 0;
    else
        return result;
}

int main(a)
{
    int N, M;
    scanf("%d%d", &N, &M);
    int u, v;
    for (int i = 0; i < M; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int calNum;
    scanf("%d", &calNum);
    bool flag = false;
    while (calNum--)
    {
        int k;
        double cc;
        scanf("%d", &k);
        if (flag == false)
        {
            cc = BFS(k, N);
            printf("Cc(%d)=%.2f\n", k, cc);
        }
        else
        {
            printf("Cc(%d)=%.2f\n", k, 0.0);
        }
        if (cc == 0)
            flag = true;
    }
    return 0;
}
Copy the code