本文共 2299 字，大约阅读时间需要 7 分钟。

为了解决这个问题，我们需要验证“六度空间”理论，即在给定的社交网络图中，对于每个节点，计算其在六度空间内的节点占总节点数的百分比。六度空间理论指出，在一个社交网络中，任意两个陌生人之间最多有六个人相连，即最多通过五个人可以认识对方。

方法思路

解决代码

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#define MAXN 10005
typedef struct VNode {
    struct VNode* Next;
    int V;
} Vertex;
typedef struct LNode {
    struct VNode* FirstEdge;
} List;
typedef struct GNode {
    int Nv, Ne;
    List Head;
} Graph;
void Insert(int u, int v, Graph* G) {
    Vertex* newU = (Vertex*)malloc(sizeof(Vertex));
    newU->V = u;
    newU->Next = G->Head[u].FirstEdge;
    G->Head[u].FirstEdge = newU;
    Vertex* newV = (Vertex*)malloc(sizeof(Vertex));
    newV->V = v;
    newV->Next = G->Head[v].FirstEdge;
    G->Head[v].FirstEdge = newV;
}
void BFS(int s, int Nv, Graph* G, FILE* output) {
    int visited[Nv + 1] = {0};
    int cnt = 0;
    std::queue
       
        
         > q; visited[s] = 1; cnt = 1; q.push({s, 0}); while (!q.empty()) { auto current = q.front(); q.pop(); int v = current.first; int d = current.second; if (d >= 5) { continue; } for (Vertex* neighbor = G->Head[v].FirstEdge; neighbor != NULL; neighbor = neighbor->Next) { int w = neighbor->V; if (!visited[w]) { visited[w] = 1; cnt++; q.push({w, d + 1}); } } } double perc = (double)cnt / (double)Nv * 100.0; perc = round(perc * 100) / 100.0; // 保留两位小数 fprintf(output, "%d: %.2f%%\n", s, perc); } int main() { char* input = NULL; size_t n = 0; FILE* input_file = fopen("input.txt", "r"); if (input_file == NULL) { printf("无法打开输入文件\n"); return 1; } Graph* G = (Graph*)malloc(sizeof(struct GNode)); G->Nv = 0; G->Ne = 0; while (fgets(input, sizeof(input), input_file) != NULL) { n = strlen(input); if (n < 2) { continue; } int u, v; sscanf(input, "%d %d", &u, &v); Insert(u, v, G); G->Ne++; } G->Nv = n; FILE* output = fopen("output.txt", "w"); for (int i = 1; i <= G->Nv; ++i) { BFS(i, G->Nv, G, output); } fclose(input_file); fclose(output); free(G); return 0; }
        
       
      
     
    
   

代码解释

通过这种方法，我们可以高效地计算每个节点在六度空间内的节点覆盖率，验证“六度空间”理论。

转载地址：http://pcrd.baihongyu.com/