数据结构 实验 c/c++ 六度空间 图 图论

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

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

实验要求 ：(1)输入格式说明:

输入第1行给出两个正整数，分别表示社交网络图的结点数N (1 (2)输出格式说明:

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

(3)样例输入与输出:

代码如下：

#include
#include

#define SIX 6
#define  MaxVertexNum  1000     

typedef unsigned long  VertexType;    
typedef  struct  node{          
    VertexType AdjV;              
    struct  node  *Next;          
  
} EdgeNode;        

typedef unsigned long  VertexType;    
typedef  struct  Vnode{       
    char   Visited;              
    double  Percent;              
    EdgeNode  *FirstEdge;       
} VertexNode;

typedef  VertexNode  AdjList[ MaxVertexNum ];

typedef  struct{  
    AdjList  adjlist;          
    unsigned long int  n, e;  
} ALGraph;                   

typedef struct Element { 
    VertexType v;        
    int Layer;           
} QElementType;
typedef struct Node{
    QElementType  Data;
    struct Node  *Next;
}QNode; 
typedef  struct {              
    QNode  *rear;              
    QNode  *front;             
} linkQueue;

void Initialize(linkQueue  *PtrQ)
{
    PtrQ->rear = PtrQ->front = NULL;
}

int IsEmptyQ(linkQueue  *PtrQ)
{
    return PtrQ->front == NULL ;
}

void AddQ ( linkQueue  *PtrQ, QElementType item )
{   
    QNode *cell = (QNode *)malloc(sizeof(QNode));

    cell->Data = item; 
    cell->Next = NULL;
    if  ( IsEmptyQ(PtrQ) )  
        PtrQ->front = PtrQ->rear = cell;
    else
    { 
        PtrQ->rear->Next = cell;
        PtrQ->rear = cell;
    }
}

QElementType DeleteQ ( linkQueue  *PtrQ )
{   QNode  *FrontCell; 
    QElementType FrontElem;

    if  ( PtrQ->front == NULL) {
        printf("队列空");
        exit(0);
    } 
    FrontCell = PtrQ->front;
    if ( PtrQ->front == PtrQ->rear) 
        PtrQ->front = PtrQ->rear = NULL; 
    else                     
        PtrQ->front = PtrQ->front->Next;
    FrontElem = FrontCell->Data;
    free( FrontCell );  
    return  FrontElem;
}

void DestroyQueue( linkQueue  Q )
{
    QNode *cell ;
    while((cell = Q.front)){
        Q.front = Q.front->Next;
        free(cell);
    }
}

void CreateALGraph( ALGraph *G )
{
    unsigned long int i,j,k;
    EdgeNode *edge;

    scanf( "%ld %ld", &(G->n), &(G->e) );       
    for ( i=0; i < G->n; i++ ) {        
        G->adjlist[i].Visited = 0;      
        G->adjlist[i].Percent = 0.0;    
        G->adjlist[i].FirstEdge = NULL; 
    }
    for ( k=0; k < G->e; k++ ){   
        scanf( "%ld %ld", &i, &j); 
        edge = (EdgeNode*) malloc( sizeof( EdgeNode ) );
        
        edge->AdjV = j-1; 
        
        edge->Next = G->adjlist[i-1].FirstEdge;
        G->adjlist[i-1].FirstEdge = edge;
        
        edge = (EdgeNode*) malloc( sizeof( EdgeNode ) );
        edge->AdjV = i-1; 
        
        edge->Next = G->adjlist[j-1].FirstEdge;
        G->adjlist[j-1].FirstEdge = edge;
    }
}

void  SixDegree_BFS( ALGraph *G , VertexType Start )
{   
    QElementType  qe;   
    linkQueue  Q; 
    VertexType  v;
    EdgeNode *edge;
    unsigned long int VisitCount = 1;  

    Initialize( &Q );     
     G->adjlist[Start].Visited = 1; 
    qe.v = Start; qe.Layer = 0;   
    AddQ( &Q, qe );                  
    while ( !IsEmptyQ(&Q) ) {      
        qe = DeleteQ(&Q); v = qe.v; 
        for( edge=G->adjlist[v].FirstEdge; edge; edge=edge->Next )
            if ( !G->adjlist[edge->AdjV].Visited )
            
            {    
                G->adjlist[edge->AdjV].Visited = 1; 
                
                VisitCount++ ;        
                if(++qe.Layer < SIX) 
                {    qe.v = edge->AdjV;   
                    AddQ(&Q, qe);
                }
                qe.Layer--;   
            } 
    } 
    DestroyQueue( Q );
    G->adjlist[Start].Percent = 100.0 * (double)VisitCount / (double)G->n;
}

int main()
{
    VertexType i,j;
    ALGraph *G = (ALGraph *)malloc( sizeof(ALGraph) );
    CreateALGraph( G );
    for(i=0L; in; i++)
    {    
        SixDegree_BFS( G, i );
        printf("%ld: %.2f%%n", i+1, G->adjlist[i].Percent);
        for ( j=0; j < G->n; j++ )         
            G->adjlist[j].Visited = 0;     
    }    
    return 0;
}