#include <stdio.h> #include <stdlib.h> #include <string.h>

define max_dis 100000

typedef char vextype[20];

typedef struct { int N, E;//N是顶点数，E是边数 int** matrix;//储存邻接矩阵 vextype* vertex;//存储节点的名字 } Graph;

Graph createGraph(int n); void nodeDegree(Graph g, int* node_degree); double clusteringCoefficient(Graph g);

/**

• 创建一个节点数为n的图
• @param n 节点个数
• @return 返回这个图 / Graph createGraph(int n) { int i, j; Graph g; g.N = n; g.matrix = (int*)malloc(sizeof(int*) * g.N); for (i = 0; i < n; i++) { g.matrix[i] = (int*)malloc(sizeof(int) * g.N); } for (i = 0; i < g.N; i++) { for (j = 0; j < g.N; j++) { g.matrix[i][j] = max_dis; } } for (i = 0; i < g.N; i++) { g.matrix[i][i] = 0; } g.vertex = (vextype*)malloc(sizeof(vextype) * g.N); return g; }

/**

• 计算每个点的度
• @param g 图
• @param node_degree 将每个点的度写到这个数组中 */ void nodeDegree(Graph g, int *node_degree) { int i,j; for(i=0;i<g.N;i++) { node_degree[i]=0; for(j=0;j<g.N;j++) { if(g.matrix[i][j]!=0&&g.matrix[i][j]!=max_dis) node_degree[i]++; } } }

/**

• 计算图的聚类系数
• @param g 图
• @return 返回聚类系数 */ double clusteringCoefficient(Graph g) { int *degree = (int *)malloc(sizeof(int) * g.N); nodeDegree(g, degree); double *clu = (double )malloc(sizeof(double) * g.N); int i; for(i=0;i<g.N;i++) { if(degree[i]==0||degree[i]==1) clu[i]=0; else { int j; int val=0; int value=0; int count=0; val=(degree[i](degree[i]-1))/2; int *index = (int )malloc(sizeof(int) * degree[i]); for(j=0;j<g.N;j++) { if(g.matrix[i][j]!=0&&g.matrix[i][j]!=max_dis) { index[count]=j; count++; } } int k,l; for(k=0;k<degree[i];k++) { for(l=k+1;l<degree[i];l++) // 注意这里要从k+1开始循环 { if(g.matrix[index[k]][index[l]]!=0&&g.matrix[index[k]][index[l]]!=max_dis) value++; } } clu[i]=2value/val; // 注意这里要乘以2 } } int m; double cluc = 0; // 初始化为0 for(m=0;m<g.N;m++) { cluc=cluc+clu[m]; } cluc=cluc/g.N; return cluc; }

int main() { int node_num; int edge_num;

scanf('%d %d', &node_num, &edge_num);

Graph g = createGraph(node_num);
for(int i = 0; i < node_num; i++) {
    sprintf(g.vertex[i], '%d', i);
}

for (int i = 0; i < edge_num; i++) {
    int start_idx, end_idx, weight;
    scanf('%d %d %d', &start_idx, &end_idx, &weight);
    g.matrix[start_idx][end_idx] = weight;
    g.matrix[end_idx][start_idx] = weight;
}

int *degree = (int *)malloc(sizeof(int) * g.N);
nodeDegree(g, degree);
printf('degree distribution:\n');
for(int i=0; i<g.N; i++)
{
    printf('node%s:%d,', g.vertex[i], degree[i]);
}
printf('\n');

double c = clusteringCoefficient(g); printf('clustering coefficient:%f\n', c);

return 0;

}

输入：

7 // 节点数 8 // 节点相邻边数 0 6 1 ////节点0到节点6有一条长度为1的边 1 6 2 1 2 3 2 3 4 3 4 5 4 6 6 4 5 7 1 3 8   输出：

degree distribution: node0:1, node1:3, node2:2, node3:3, node4:3, node5:1, node6:3, clustering coefficient:0.238095