[数据结构与算法]六度空间理论(数据结构图c语言版)

六度空间理论(数据结构图,c语言版)

一、实验题目

六度空间理论是一个数学领域的猜想，又称为六度分割理论 (Six Degrees of Separation)。六度空间理论是20世纪60年代由美国的心理学家米格兰姆(Stanley Milgram) 提出的，理论指出：你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。

1.案例分析

六度空间理论的数学模型属于图结构，我们把六度空间理论中的人际关系网络图抽象成一个不带权值的无向图G, 用图G 中的一个顶点表示一个人，两个人 ”认识” 与否，用代表这两个人的顶点之间是否有一条边来表示。这样六度空间理论问题便可描述为：在图 G 中任意两个顶点之间都存在一条路径长度不超过7的路径。 在实际验证过程中，可以通过测试满足要求的数据达到一定的百分比（比如 99.5%) 来进行验证。 这样我们便把待验证六度空间理论问题描述为：在图G 中，任意一个顶点到其余 99.5%以上的顶点都存在一条路径长度不超过 7 的路径。比较简单的一种验证方案是：利用广度优先搜索方法， 对任意一个顶点，通过对图 G的 "7层”遍历，就可以统计出所有路径长度不超过 7 的顶点数 从而得到这些顶点在所有顶点中的所占比例。

2.案例实现

算法中有关数据结构的定义如下：

// - - - -图的邻接表存储表示 - - - -
#define MVNum 100 //最大顶点数

typedef struct ArcNode  //边结点
{ 
	int adjvex;  //该边所指向的顶点的位置
	struct ArcNode* nextarc; //指向下一条边的指针
	//Otherinfo info; //和边相关的信
}ArcNode; 

typedef struct VNode //顶点信息
{ 
	//VerTexType data; 
	ArcNode *firstarc;	//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型

typedef struct  //邻接表
{
	AdjList vertices; 
	int vexnum,arcnum;//图的当前顶点数和边数 
}ALGraph;

3.算法步骤

1.完成系列初始化工作：设变量 Visit_Num 用来记录路径长度不超过 7 的顶点个数，初值为0; Start 为指定的一个起始顶点， 置 visited[Start]的值为 true, 即将 Start 标记为六度顶点的始点；辅助队列 Q 初始化为空，然后将 Start 进队。
2.当队列Q非空，且循环次数小千7时，循环执行以下操作（统计路径长度不超过7的顶点个数）：
? 队头顶点u出队；
? 依次检查 u 的所有邻接点 w, 如果 visited[w]的值为 false, 则将w标记为六度顶点；
? 路径长度不超过7的顶点个数 Visit_Num 加1 ;
? 将w进队。
3.退出循环时输出从顶点Start出发，到其他顶点长度不超过7的路径的百分比。

4.算法描述

void SixDegree_BFS(Graph G,int Start) 
{//通过广度优先搜索方法遍历G来验证六度空间理论，Start为指定的一个起点
	Visit_Num=O; //记录路径长度不超过7的顶点个数
	visited[Start]=true; //置顶点Start访问标志数组相应分址值为true
	InitQueue(Q); //辅助队列Q初始化， 置空
	EnQueue(Q,Start); //Start进队
	for(len=l;len<=7 && !QueueEmpty(Q);len++)//统计路径长度不超过7的顶点个数
	{
		DeQueue(Q,u}; //队头顶点u出队
		for(w=FirstAdjVex(G,u);w>=O;w=NextAdjVex(G,u,w)) 
		{//依次检查u的所有邻接点w, FirstAdjVex(G,u)表示u的第一个邻接点
		 //NextAdjVex(G,u,w)表示u相对于w的下一个邻接点，w匀表示存在邻接点
			if(!visited[w]) //w为u的尚未访问的邻接顶点
			{
				visited[w]=true; //将w标记为六度顶点
				Visit_Num++; //路径长度不超过7的顶点个数加1
				EnQueue(Q,w); //w进队
			}//if 
		}
	}//结束至多7次for循环
	cout<<1OO*Visit_Num/G.vexnum; 
	//输出从顶点Start出发， 到其他顶点长度不超过7的路径的百分比
}

二、工具环境

Window10操作系统，Microsoft Visual C++2010学习版 集成开发环境，C语言

三、实验代码

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

//  - - - -队列的存储表示 - - - -
#define MAXSIZE 100    //队列可能达到的最大长度
#define OK  1
#define ERROR  0
#define OVERFLOW -2

typedef int  Status;

typedef struct{ 
	int *vex; //队列中数据
	int front; //头指针
	int rear;  //尾指针
}SqQueue; 

Status InitQueue (SqQueue *Q);
Status EnQueue(SqQueue *Q, int e);
Status DeQueue(SqQueue *Q, int *e);
Status QueueEmpty(SqQueue Q);

// - - - -图的邻接表存储表示 - - - -
#define MVNum 100 //最大顶点数

typedef struct ArcNode  //边结点
{ 
	int adjvex;  //该边所指向的顶点的位置
	struct ArcNode* nextarc; //指向下一条边的指针
	//Otherinfo info; //和边相关的信
}ArcNode; 

typedef struct VNode //顶点信息
{ 
	//VerTexType data; 
	ArcNode *firstarc;	//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型

typedef struct  //邻接表
{
	AdjList vertices; 
	int vexnum,arcnum;//图的当前顶点数和边数 
}ALGraph;

void CreateUDG(ALGraph *G);
int FirstAdjVex(ALGraph G,int v);
int NextAdjVex(ALGraph G,int u,int w);
void SixDegree_BFS(ALGraph G,int Start);
void ShowResults(ALGraph G);

int main()
{	
	ALGraph G;
	CreateUDG(&G);
	ShowResults(G);
	return 0;
}

Status InitQueue (SqQueue *Q) 
{//构造一个空队列Q
	Q->vex=(int *)malloc(MAXSIZE*sizeof(int));//为队列分配一个最大容量为MAXSIZE的数组空间
	if(!Q->vex) exit(OVERFLOW);//存储分配失败
	Q->front=Q->rear=0;//头指针和尾指针置为零、队列为空
	return OK;
}

Status EnQueue(SqQueue *Q, int e) 
{//插入元素e为Q的新的队尾元素
	if ((Q->rear+1)%MAXSIZE==Q->front)//尾指针在循环意义上加1后等于头指针，表明队满
	return ERROR; 
	Q->vex[Q->rear]=e;//新元素插入队尾
	Q->rear=(Q->rear+1)%MAXSIZE;//队尾指针加1
	return OK; 
}

Status DeQueue(SqQueue *Q, int *e) 
{//删除Q的队头元素，用e返回其值
	if(Q->front==Q->rear) return ERROR; //队空
	*e=Q->vex[Q->front]; //保存队头元素
	Q->front=(Q->front+1)%MAXSIZE; //队头指针加1
	return OK;
}

Status QueueEmpty(SqQueue Q)
{//判断队列是否为空
	if(Q.front==Q.rear) return OK;//队列空，返回1
	else return ERROR;//队列不空，返回0
}

void CreateUDG(ALGraph *G) 
{//采用邻接表表示法， 创建无向图 G
	int i,j,k,v1,v2;
	ArcNode *p1=NULL,*p2=NULL;
	printf("输入点和边\n");
	scanf("%d %d",&((*G).vexnum),&((*G).arcnum));//输入总顶点数，总边数
	for(i=0;i<(*G).vexnum;++i) //输入各点，构造表头结点表
	{
		//cin>>G.vertices[i].data; //输入顶点值
		(*G).vertices[i].firstarc=NULL;//初始化表头结点的指针域为NULL
	}//for 
	for(k=0;k<(*G).arcnum;++k) //输入各边， 构造邻接表
	{
		printf("输入俩顶点\n");
		scanf("%d %d",&v1,&v2);//输入一条边依附的两个顶点
		i=v1-1; j=v2-1;
		//i=LocateVex(G,vl); j=LocateVex(G,v2); 
		//确定vl和 v2在G中位置， 即顶点在G.vertices中的序号
		p1=(ArcNode*)malloc(sizeof(ArcNode)); //生成一个新的边结点*pl
		p1->adjvex=j; //邻接点序号为j
		p1->nextarc=(*G).vertices[i].firstarc; (*G).vertices[i].firstarc=p1;
		//将新结点*pl插入顶点Vi的边表头部
		p2=(ArcNode*)malloc(sizeof(ArcNode)); //生成另一个对称的新的边结点*p2
		p2->adjvex=i; //邻接点序号为i
		p2->nextarc=(*G).vertices[j] .firstarc; (*G).vertices[j].firstarc=p2; 
		//将新结点*p2插入顶点Vj的边表头部
	}//for
}

int FirstAdjVex(ALGraph G,int v)
{
   if(!G.vertices[v].firstarc)//判断是否有临界点
   {
        return -1;
   }
   return G.vertices[v].firstarc->adjvex;//如果有返回该点的位置
}

int NextAdjVex(ALGraph G,int u,int w)//表示u相对于w的下一个临界点w>=0 表示存在临界点
{
    ArcNode *p;
    p=G.vertices[u].firstarc;//与u相邻的第一条边
	while(p && p->adjvex!=w){//只要这条边的邻接点不是w
		 p=p->nextarc;//下一个位置
	}
	if(p->nextarc!=NULL)
	{//找到w位置且下一个边不空
		return p->nextarc->adjvex;
	}
    return -1;//该位置为NULL说明，与u位置有关系的点已经遍历完
}

void SixDegree_BFS(ALGraph G,int Start) 
{//通过广度优先搜索方法遍历G来验证六度空间理论，Start为指定的一个起点
	int Visit_Num=0,len,u,w; //记录路径长度不超过7的顶点个数
    int visited[MVNum]={0} ; //访问标志数组， 其初值为 "false"
	SqQueue Q;
	visited[Start]=1;  //置顶点Start访问标志数组相应分址值为true
	InitQueue(&Q); //辅助队列Q初始化，置空
	EnQueue(&Q,Start); //Start进队
	for(len=1;len<=7 && !QueueEmpty(Q) ;len++)//统计路径长度不超过7的顶点个数
	{
		DeQueue(&Q,&u); //队头顶点u出队
		for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
		{//依次检查u的所有邻接点w, FirstAdjVex(G,u)表示u的第一个邻接点
		 //NextAdjVex(G,u,w)表示u相对于w的下一个邻接点，w匀表示存在邻接点
			if(!visited[w]) //w为u的尚未访问的邻接顶点
			{
				visited[w]=1; //将w标记为六度顶点
				Visit_Num++; //路径长度不超过7的顶点个数加1
				EnQueue(&Q,w); //w进队
			}//if 
		}
	}//结束至多7次for循环
	printf("第%d个点，%.2f%%\n",Start+1,100*Visit_Num/(float)G.vexnum);
	//输出从顶点Start出发， 到其他顶点长度不超过7的路径的百分比
}

void ShowResults(ALGraph G)
{
	int Start;
	printf("从顶点出发，到其他顶点长度不超过7的路径的百分比\n");
	for(Start=0;Start<G.vexnum;Start++)
	{
		SixDegree_BFS(G,Start);
	}
}