7-7 六度空间

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


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

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

输入格式:
输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤10
​3
​​ ，表示人数）、边数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%

版本1 ： 
30满分
#include <stdio.h>
#include <stdlib.h>

#define MaxVertexNum 1001

/* 无向图的邻接表定义——开始 */
typedef int Vertex;
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
    Vertex AdjV;
    PtrToAdjVNode Next;
};

typedef struct Vnode {
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1, V2;
};
typedef PtrToENode Edge;

LGraph CreateGraph( int VertexNum )
{
    Vertex V;
    LGraph Graph;

    Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;

    for (V = 1; V <= Graph->Nv; ++V)
        Graph->G[V].FirstEdge = NULL;

    return Graph;
}

void DestoryGraph( LGraph Graph )
{
    Vertex V;
    PtrToAdjVNode Node;
    for (V = 1; V <= Graph->Nv; ++V) {
        while (Graph->G[V].FirstEdge) {
            Node = Graph->G[V].FirstEdge;
            Graph->G[V].FirstEdge = Node->Next;
            free(Node);
        }
    }
    free(Graph);
}

void InsertEdge(LGraph Graph, Edge E)
{
    PtrToAdjVNode NewNode;

    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}
/* 无向图的邻接表定义——结束 */

/* 队列定义开始 */
#define MaxSize 1001
#define ERROR -1
typedef int Position;
struct QNode {
    int *Data;     /* 存储元素的数组 */
    Position Front, Rear;  /* 队列的头、尾指针 */
};
typedef struct QNode *Queue;

Queue CreateQueue()
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (int *)malloc(MaxSize * sizeof(int));
    Q->Front = Q->Rear = 0;
    return Q;
}

void DestoryQueue( Queue Q )
{
    if (Q->Data) free(Q->Data);
    free(Q);
}

int IsFull( Queue Q )
{
    return ((Q->Rear+1)%MaxSize == Q->Front);
}

void Enqueue( Queue Q, int X )
{
    if ( IsFull(Q) ) return;
    else {
        Q->Rear = (Q->Rear+1)%MaxSize;
        Q->Data[Q->Rear] = X;
    }
}

int IsEmpty( Queue Q )
{
    return (Q->Front == Q->Rear);
}

int Dequeue( Queue Q )
{
    if ( IsEmpty(Q) ) return ERROR;
    else  {
        Q->Front =(Q->Front+1)%MaxSize;
        return  Q->Data[Q->Front];
    }
}
/* 队列定义结束 */
Vertex visited[MaxVertexNum] = {0};
void setZero(int VertexNum)
{
    Vertex V;
    for (V = 1; V <= VertexNum; ++V)
        visited[V] = 0;
}

LGraph BuildGraph()
{
    LGraph Graph;
    Edge E;
    int Nv, i;

    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0) {
        E = (Edge)malloc(sizeof(struct ENode));
        for (i = 0; i < Graph->Ne; ++i) {
            scanf("%d %d", &E->V1, &E->V2);
            InsertEdge(Graph, E);
        }
        free(E);
    }
    return Graph;
}

int BFS(LGraph Graph, Vertex V)
{
    int count, level;
    Vertex tail, last; Queue Q;
    PtrToAdjVNode Node;
    Q = CreateQueue();
    setZero(Graph->Nv);

    visited[V] = 1; count = 1;
    level = 0; last = V; tail = V;
    Enqueue(Q, V);
    while(!IsEmpty(Q)) {
        V = Dequeue(Q);
        for (Node = Graph->G[V].FirstEdge; Node; Node = Node->Next) {
            if (!visited[Node->AdjV]) {
                visited[Node->AdjV] = 1;
                Enqueue(Q, Node->AdjV); ++count;
                tail = Node->AdjV;
            }
        }
        if (V == last) {
            ++level; last = tail;
        }
        if (level == 6) break;
    }

    DestoryQueue(Q);
    return count;
}

void SDS(LGraph Graph)
{
    Vertex V;
    double count;
    for (V = 1; V <= Graph->Nv; ++V) {
        count = BFS(Graph, V);
        printf("%d: %.2f%%\n", V, count / Graph->Nv * 100);
    }
}

int main()
{
    LGraph Graph;
    Graph = BuildGraph();
    SDS(Graph);
    DestoryGraph(Graph);

    return 0;
}















版本2：
建立矩阵求点与点的距离，0为不可达
a[i][i] = 0 
所以最后sum初始为1 把a[i][i]自身加上
但平台显示

测试点	提示	结果	分数	耗时	内存
0	sample 简单一条链	
答案正确
18	3 ms	332 KB
1	不连通	
答案正确
3	3 ms	340 KB
2	一般图	
答案正确
3	3 ms	336 KB
3	最小N和M	
答案正确
3	3 ms	204 KB
4	最大N和M	
答案错误
0	1613 ms	8108 KB



自己没有找出哪里问题 希望指出



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

int Matric[1001][1001] ;  //zong 
int Matrix[1001][1001] ; 

int main ()
{
	int vertexs  ; int edges  ;
	scanf("%d %d",&vertexs,&edges) ; 
	int v1 ; int v2  ; 
	
	
	int i ; int j  ;
	for(i=0;i<edges;i++)
	{
		scanf("%d %d",&v1 , &v2) ; 
		v1-- ; v2-- ; 
		Matrix[v1][v2]=Matric[v1][v2]=Matrix[v2][v1]=Matric[v2][v1]=1 ; 
	}
	for(i=0;i<vertexs;i++)
	{
		Matrix[i][i]=Matric[i][i] = 0 ; 
	}

	
	
	
int k ; 
	
	
		for(i=0;i<vertexs;i++)
		{
			for(j=0;j<vertexs;j++)
			{  
				for(k=0;k<vertexs;k++)
				{   
				    if (Matric[i][k]*Matrix[k][j] >0 )
				    {
				    	if(Matric[i][j]==0   || Matric[i][j] > Matric[i][k]+Matrix[k][j])
				    	{
				    	    Matric[j][i] =  Matric[i][j] = Matric[i][k]+Matrix[k][j];
				        }
					
					}
				    
					
				}
			}
		}
		
	for(i=0;i<vertexs;i++) 
	{
		Matric[i][i] = 0  ; 
	 } 
int sum ; 
	for(j=0;j<vertexs;j++)
	{
		for(i=0,sum=1;i<vertexs;i++)
		{
			if(Matric[i][j]<=6 &&Matric[i][j]>0)   sum++ ; 
		}
		printf("%d: %.2f%%\n", j+1,(float)((float)(sum)/(float)(vertexs))*100);
	}
	
	
	
}