数据结构实验任务七:基于广度优先搜索的六度空间理论验证

本文主要是介绍数据结构实验任务七:基于广度优先搜索的六度空间理论验证,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题描述

“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论 可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是 说,最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图, 请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。 输入要求 多组数据,每组数据 m+1 行。第一行有两个数字 n 和 m,代表有 n 个人和 m 组朋友关系。n 个人的编号为 1 到 n。第二行到第 m+1 行每行包括两个数字 a 和 b,代表这两个人互相认识。当 n 和 m 都等于 0 时,输入结束。 输出要求 每组数据输出 n 行,对每个结点输出与该结点距离不超过 6 的结点数占结点 总数的百分比,精确到小数点后 2 位。每个结节点输出一行,格式为“结点编号:(空 格)百分比%”

运行结果:

代码实现:

#include <stdio.h>
#include <stdlib.h>
#define MaxS 20
#define MaxE 5
//结构体部分
typedef struct{						//图结构体定义 char vex[MaxS];					//顶点数组 int vexnum;						//顶点个数 int mat[MaxS][MaxS];			//邻接矩阵 int arcnum;						//边数 
}Graph;
typedef struct{int head,tail;int mat[20];						//队列数组 
}Queue;
//全局变量部分
float result[MaxE][MaxS];					//结果存储函数
int cunt;							//用于全局变量遍历 
int state[MaxS];
//函数声明部分
void Init(Graph *a);
int Read(Graph *a);
void Cal(Graph *a);
void show();
float BFS(Graph *a,int s);
void InitQ(Queue *q);				//初始化队列 
void push(Queue* q,int n);			//入队 
int pop(Queue *q);					//出队 
//函数定义部分
void InitQ(Queue *q){q->head=0;q->tail=0;
}
void push(Queue* q,int n){q->mat[q->tail] = n;q->tail++;
}
int pop(Queue* q){q->head++;if(q->head>q->tail)return -1;return q->mat[q->head-1];
}
float BFS(Graph *a,int s){int tmp,rs=0;int *len=(int*)malloc(sizeof(int)*a->vexnum+1);			//记录到s的距离 for(int i=0;i<=a->vexnum;i++){state[i] = 0;len[i] = 0;}Queue* q = (Queue*)malloc(sizeof(Queue));InitQ(q);push(q,s);state[s]=1;for(int i = 0;i<a->vexnum;i++){						//总共遍历a->vexnum次tmp = pop(q);if(tmp==-1)continue;for(int j=1;j<=a->vexnum;j++){					//每次扫描vexnum个数  if(a->mat[tmp][j]==1&&state[j]==0){len[j] = len[tmp]+1;state[j] = 1;							//状态变成已访问push(q,j);continue;}}}for(int i=1;i<=a->vexnum;i++){if(len[i]<=6&&len[i]!=0)rs+=1;}for(int i=1;i<=a->vexnum;i++){}free(len);free(q);return (float)(rs+1)/a->vexnum*100;
}
void show(){printf("\n                  =================|    -FZC-    |===============                 \n\n");									printf("FOLLOWING OUTPUT:\n");for(int i=0;i<cunt;i++){printf("[EXP %d ]\n",i+1);for(int j=1;j<MaxS;j++){if(result[i][j]==-1)break;printf("%d: %.2f%%\n",j,result[i][j]);}}
} 
void Init(Graph *a){a->arcnum=0;a->vexnum=0;for(int i=0;i<MaxS;i++){a->vex[i] =0;state[i] = 0;result[cunt][i] = -1;for(int j=0;j<MaxS;j++){a->mat[i][j] = 0;}}}int Read(Graph *a){int n,m,s,e;printf("input n,m:");scanf("%d %d",&n,&m);if(n==0&&m==0)return 1;			//若均为0则返回1 a->vexnum = n;a->arcnum = m;printf("input relationship:\n");for(int i=0;i<m;i++){scanf("%d %d",&s,&e);a->mat[s][e] = 1;a->mat[e][s] = 1; }printf("边输入完成;共%d条\n",a->arcnum);return 0; 
}
void Cal(Graph *a){for(int i=1;i<=a->vexnum;i++){result[cunt][i] = BFS(a,i);}printf("\nSuccess!\n");cunt++; 
}
//主函数部分 
int main(){int flag = 0; Graph* a=(Graph*)malloc(sizeof(Graph));cunt=0;printf("多组数据,每组数据 m+1 行。第一行有两个数字 n 和 m,代表有 n 个人和m 组朋友关系。\nn 个人的编号为 1 到 n。\n第二行到第 m+1 行每行包括两个数字 a和 b,代表这两个人互相认识。\n当 n 和 m 都等于 0 时,输入结束。");while(1){//初始化Init(a);printf("\n                  =================|    -FZC-    |===============                 \n\n");//读取数据flag = Read(a);if(flag==1){show();				//输出结果break; }//处理数据Cal(a); }printf("程序结束!\n"); return 0;
}

这篇关于数据结构实验任务七:基于广度优先搜索的六度空间理论验证的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/466976

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i

Spring Boot 集成 Quartz 使用Cron 表达式实现定时任务

《SpringBoot集成Quartz使用Cron表达式实现定时任务》本文介绍了如何在SpringBoot项目中集成Quartz并使用Cron表达式进行任务调度,通过添加Quartz依赖、创... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启

Java使用多线程处理未知任务数的方案介绍

《Java使用多线程处理未知任务数的方案介绍》这篇文章主要为大家详细介绍了Java如何使用多线程实现处理未知任务数,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 知道任务个数,你可以定义好线程数规则,生成线程数去跑代码说明:1.虚拟线程池:使用 Executors.newVir

查看Oracle数据库中UNDO表空间的使用情况(最新推荐)

《查看Oracle数据库中UNDO表空间的使用情况(最新推荐)》Oracle数据库中查看UNDO表空间使用情况的4种方法:DBA_TABLESPACES和DBA_DATA_FILES提供基本信息,V$... 目录1. 通过 DBjavascriptA_TABLESPACES 和 DBA_DATA_FILES

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)

《Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)》本文介绍了如何使用Python和Selenium结合ddddocr库实现图片验证码的识别和点击功能,感兴趣的朋友一起看... 目录1.获取图片2.目标识别3.背景坐标识别3.1 ddddocr3.2 打码平台4.坐标点击5.图