欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

06-图3 六度空间

程序员文章站 2024-01-17 18:15:40
...

“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图1所示。

06-图3 六度空间
图1 六度空间示意图

“六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入格式:

输入第1行给出两个正整数,分别表示社交网络图的结点数N(1<N≤103,表示人数)、边数M(≤33×N,表示社交关系数)。随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个结点的编号(节点从1到N编号)。

输出格式:

对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比,精确到小数点后2位。每个结节点输出一行,格式为“结点编号:(空格)百分比%”。

输入样例:

10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

输出样例:

1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%

总结

需要注意的地方:

  • 最后需要输出百分制,所以要注意int类型会取整
  • 每遍历一个结点,需要重置标记
  • 循环退出的时间

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxVertexNum 10001
typedef int Vertex;
/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
    Vertex Adjv;        /* 邻接点下标 */
    PtrToAdjVNode Next;/* 指向下一个邻接点的指针 */
}; 
/* 顶点表头结点的定义 */
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;/* 边表头指针 */
} AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */
/* 图结点的定义 */
typedef struct GNode *LGraph;
struct GNode{
    int Ne;     /*顶点*/
    int Nv;     /*边数*/
    AdjList G;  /*邻接表*/
};
/*建邻接表*/
LGraph BuilGraph(int N,int M){
    Vertex V1,V2;
    PtrToAdjVNode Temp;
    //创建一个图
    LGraph Graph=(LGraph)malloc(sizeof(struct GNode));
    Graph->Ne=N;
    Graph->Nv=M;
    for (int i = 0; i <=N; i++)
        Graph->G[i].FirstEdge=NULL;
    //输入一个图
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d",&V1,&V2);
        /* 为V1建立新的邻接点 */
        Temp=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        Temp->Adjv=V2;
        Temp->Next=Graph->G[V1].FirstEdge;
        Graph->G[V1].FirstEdge=Temp;
        /* 为V2建立新的邻接点 */
        Temp=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        Temp->Adjv=V1;
        Temp->Next=Graph->G[V2].FirstEdge;
        Graph->G[V2].FirstEdge=Temp;
    }
    return Graph;
}
/*标记是否被遍历*/
int Visited[MaxVertexNum]={0};
/*计算结点数*/
float BFS(LGraph Graph,Vertex V){
    float Count;
    Vertex Level=0,Last=V,Tail;
    PtrToAdjVNode Temp;
    Vertex Q[MaxVertexNum];/*队列*/
    int Front=0,Rear=0;
    Visited[V]=1,Count=1;
    /*入队*/
    Rear=(Rear+1)%MaxVertexNum;
    Q[Rear]=V;
    /*计算结点数*/
    while (Front!=Rear)
    {
        /*出队*/
        Front=(Front+1)%MaxVertexNum;
        V=Q[Front];
        Temp=Graph->G[V].FirstEdge;
        while (Temp)
        {
            if (!Visited[Temp->Adjv])/*没有被遍历过*/
            {
                Rear=(Rear+1)%MaxVertexNum;
                Q[Rear]=Temp->Adjv;
                Visited[Temp->Adjv]=1;
                Tail=Temp->Adjv;
                Count+=1;
            }
            Temp=Temp->Next;
        }
        /*遍历完一层以后,层数增加*/
        if (Last==V){
                Last=Tail;
                Level++;
            }  
        /*遍历完六层,退出*/
        if (Level==6)   break;
    }
    return Count;
}
void SDS(LGraph Graph,int N){
    Vertex V;
    float Count;
    for ( V = 1; V <= N; V++)
    {
        Count=BFS(Graph,V);
        printf("%d: %.2f%%\n",V,(Count/N)*100);
        /*对标记进行重置*/
        memset(Visited,0,sizeof(Visited));
    }
}
int main()
{
    LGraph Graph;
    int N,M;
    scanf("%d %d",&N,&M);
    Graph=BuilGraph(N,M);
    SDS(Graph,N);
    return 0;
}