精华内容
下载资源
问答
  • 六度空间理论

    千次阅读 2018-05-31 19:40:14
    06-图3 六度空间(30 分)“六度空间理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就...

    06-图3 六度空间(30 分)

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


    图1 六度空间示意图

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

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

    输入格式:

    输入第1行给出两个正整数,分别表示社交网络图的结点数N1<N104,表示人数)、边数M33×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%

    程序:

    #include <iostream>
    #include <iomanip>
    #define MaxNvNum (10000)
    using namespace std;
    
    typedef int WeightType;//权重数据类型
    typedef int Vertex;//顶点类型
    typedef int ElementType;//队列中数据类型
    
    						//邻接矩阵表示的图
    typedef struct GNode * PtrToGNode;
    struct GNode {
    	int Nv;//顶点数
    	int Ne;//边数
    	WeightType Weight[MaxNvNum][MaxNvNum];
    };
    typedef PtrToGNode MGraph;
    
    int Visit[MaxNvNum];
    
    
    //边结构
    typedef struct ENode * PtrToENode;
    struct ENode {
    	Vertex v, w;
    	//WeightType Weight;
    };
    typedef PtrToENode Edge;
    
    
    //队列
    typedef struct QNode * PtrToQNode;
    struct QNode {
    	int Front, Rear;//头指针、尾指针
    	ElementType * Data;
    	int MaxLength;
    };
    typedef PtrToQNode Queue;
    
    //函数声明
    MGraph CreateGraph(int Nv);//创建一个只有顶点没有边的图
    void InsertEdge(MGraph G, Edge E);//插入边
    int BNF(MGraph G, Vertex v);//BNF搜索
    void SDS(MGraph G);//SDS六度空间
    
    Queue CreateQueue(int Length);//创建队列
    void InQueue(Queue Q, ElementType X);//入队
    ElementType OutQueue(Queue Q);//出队
    
    
    
    int main()
    {
    	int Nv;
    	int i;
    	MGraph G;
    	Edge E;
    	cin >> Nv;
    	G = CreateGraph(Nv);
    	E = new struct ENode;
    	cin >> G->Ne;
    	for (i = 0; i<G->Ne; i++) {
    		cin >> E->v >> E->w;
    		InsertEdge(G, E);
    	}
    
    	SDS(G);
    
    	delete G;
    	delete E;
    	return 0;
    }
    
    //创建一个只有顶点没有边的图
    MGraph CreateGraph(int Nv)
    {
    
    	Vertex v, w;
    	MGraph G;
    	G = new struct GNode;
    	G->Nv = Nv;
    
    	for (v = 1; v<=G->Nv; v++) {
    		for (w = 1; w<=G->Nv; w++) {
    			G->Weight[v][w] = 0;//表示没有边
    		}
    	}
    
    	return G;
    }
    
    //插入边
    void InsertEdge(MGraph G, Edge E)
    {
    	G->Weight[E->v][E->w] = 1;
    
    	G->Weight[E->w][E->v] = 1;
    }
    
    //六度空间搜索
    void SDS(MGraph G)
    {
    	Vertex v;
    	float Percent;
    	int Count;
    	for (v = 1; v<=G->Nv; v++) {
    		Count = BNF(G, v);
    		Percent = (float)(Count+1) * 100 / G->Nv;
    		cout << v << ": ";
    		cout.setf(ios::fixed);
    		cout << fixed << setprecision(2) << Percent;
    		cout << "%" << endl;
    	}
    }
    
    //对每个顶点做广度优先搜索
    int BNF(MGraph G, Vertex v)
    {
    	Queue Q;
    	Vertex w;
    	int Count = 0;//6层内的顶点数
    	int Level = 1;//层数
    	int Last, Tail;
    	int i;
    
    	Q = CreateQueue(G->Nv);
    	Visit[v] = 1;//拜访过此顶点
    	Last = v;
    	InQueue(Q, v);
    	while (Q->Rear != Q->Front) {//队列非空
    		v = OutQueue(Q);
    		for (w = 1; w<=G->Nv; w++) {
    			if (!Visit[w] && G->Weight[v][w]) {
    				Visit[w] = 1;
    				InQueue(Q, w);
    				Count++;
    				Tail = w;
    			}
    		}
    		if (v == Last) {
    			Level++;
    			Last = Tail;
    		}
    		if (Level > 6) {
    			break;
    		}
    	}
    	for (i = 1; i <= G->Nv; i++) {
    		Visit[i] = 0;
    	}
    	delete Q;
    	return Count;
    }
    
    //创建队列
    Queue CreateQueue(int Length)
    {
    	int i;
    	Queue Q;
    	Q = new struct QNode;
    	Q->Front = Q->Rear = 0;
    	Q->MaxLength = Length;
    	Q->Data = new ElementType[Q->MaxLength];
    	for (i = 1; i <= Q->MaxLength; i++) {
    		Q->Data[i] = 0;
    	}
    
    	return Q;
    }
    
    //入队
    void InQueue(Queue Q, ElementType X)
    {
    	Q->Rear++;
    	if (Q->Rear >= Q->MaxLength) {
    		Q->Rear = Q->Rear % Q->MaxLength;
    	}
    	Q->Data[Q->Rear] = X;
    }
    
    //出队
    ElementType OutQueue(Queue Q)
    {
    	int X;
    	Q->Front++;
    	if (Q->Front >= Q->MaxLength) {
    		Q->Front = Q->Front % Q->MaxLength;
    	}
    	X = Q->Data[Q->Front];
    	return X;
    }

    展开全文
  • 什么是六度空间理论

    2008-07-21 10:09:00
    有一个数学领域的猜想,名为Six Degrees of Separation,中文翻译包括以下几种: 六度分割理论、六度空间理论以及小世界理论等。 你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就...
    有一个数学领域的猜想,名为Six Degrees of Separation,中文翻译包括以下几种: 六度分割理论、六度空间理论以及小世界理论等。

    你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。这就是六度空间理论,也叫小世界理论。

    社会网络其实并不高深,它的理论基础正是“六度分隔”。而社会性软件则是建立在真实的社会网络上的增值性软件和服务。有这么一个故事,几年前一家德国报纸接受了一项挑战,要帮法兰克福的一位土耳其烤肉店老板,找到他和他最喜欢的影星马龙·白兰度的关联。结果经过几个月,报社的员工发现,这两个人只经过不超过六个人的私交,就建立了人脉关系。原来烤肉店老板是伊拉克移民,有个朋友住在加州,刚好这个朋友的同事,是电影《这个男人有点色》的制作人的女儿在女生联谊会的结拜姐妹的男朋友,而马龙·白兰度主演了这部片子。

    1967年,哈佛大学的社会心理学家米尔格兰姆(Stanley Milgram)就设计了一个连锁信件实验。他将一套连锁信件随机发送给居住在内布拉斯加州奥马哈的160个人,信中放了一个波士顿股票经纪人的名字,信中要求每个收信人将这套信寄给自己认为是比较接近那个股票经纪人的朋友。朋友收信后照此办理。最终,大部分信在经过五、六个步骤后都抵达了该股票经纪人。六度空间的概念由此而来。

    这个连锁实验,体现了一个似乎很普遍的客观规律:社会化的现代人类社会成员之间,都可能通过“六度空间” 而联系起来,绝对没有联系的A与B是不存在的。这是一个更典型、深刻而且普遍的自然现象。那么,怎样用数学理论揭示 “六度分割现象”?这是现代数学领域又一个重大的数学猜想。

    这有点儿像地图的邻接色问题,只不过邻接色问题是通过数学方法可以精确证明的(即最多只需要使用4种颜色即可),而6度分割理论我个人估计只能通过不完全归纳来形成假设了吧,社会的模型还是比二维地图模型要复杂莫测得多啦!

    六度分隔的现象,并不是说任何人与人之间的联系都必须要通过六个层次才会产生联系,而是表达了这样一个重要的概念:任何两位素不相识的人之间,通过一定的联系方式,总能够产生必然联系或关系。显然,随着联系方式和联系能力的不同,实现个人期望的机遇将产生明显的区别。

    看来六度分隔理论很有意思,找一些资料来看看学习,运用起来真的会很有效的。

    不管理论如何深奥,“六度分隔”和互联网的亲密结合,已经开始显露出商业价值。人们在近几年越来越关注社会网络的研究,很多网络软件也开始支持人们建立更加互信和紧密的社会关联,这些软件被统称为“社会性软件” (Social  Software)。例如Blog就是一种社会性软件,因为Blog写作所需要的个性和延续性,已使Blogger圈这种典型的物以类聚的生态形式,越来越象真实生活中的人际圈。据致力于研究社会软件的毛向辉介绍,国外现在更流行的是一种快速交友,或者商业联系的工具,例如 LinkedIN。人们可以更容易在全球找到和自己有共同志趣的人、更容易发现商业机会、更容易达到不同族群之间的理解和交流,等等。

    社会性软件的定义很多,而且还都在不断的发展演变过程之中。它的核心思想其实是一种聚合产生的效应。人、社会、商业都有无数种排列组合的方式,如果没有信息手段聚合在一起,就很容易损耗掉。WWW成功地将文本、图形聚合在一起,使互联网真正走向应用;即时通讯又将人聚合在一起,产生了ICQ这样的工具。然而这还是虚拟的,虚拟虽然是网络世界的一种优势,但是和商业社会所要求的实名、信用隔着一条鸿沟。通过熟人之间,通过“六度分隔”产生的聚合,将产生一个可信任的网络,这其中的商业潜能的确是无可估量的。

    聚合作为社会研究的对象也具有实际价值。康奈尔大学的科学家开发了一个算法,能够识别一篇文章中某些文字的“突发”增长,而这些“突发”增长的文字可以用来快速识别最新的趋势和热点问题,因此能够更有效地筛选重要信息。过去很多搜索技术都采用了简单计算文字 /词组出现频率的方法,却忽略了文字使用增加的速率。如果这种方法应用到广告商,就可以快速找到潜在的需求风尚。

    社会、网络、地域、商业、Blog,这些词汇你也许都听麻木了。然而一旦那些预见先机的人找到聚合它们的商业价值,被改变的绝不仅仅是网络世界。

    六度虽然是个社会学的理论,但是实际上它更像一个数学理论,很多人说六度和四色问题有异曲同工之妙。在我看来,六度理论很好的阐述了在一个网状结构(我们的人类社会)下,不同节点之间的联系和连接关系,然而它并不完整,并不足以指导我们的实践。

    (1)关系的强弱——权值问题
    首先六度肯定了人与人之间的普遍联系,但是没有对这种联系作定量分析。我们一生可能会认识千百人,他们有的对我极其重要,有的对我无足轻重,我们联系的建立的原因和方法也是千差万别,有父母亲属这类生而固有的联系,也有因为地理位置接近发展出来的,如邻里关系,还有因为共同学习生活而发展出来的同学、同事关系。六度理论中只把他们统统归结于联系,没有强弱之分。在网状结构里面,人与人的关系,需要加权处理,在这里,六度是残缺的。

    (2)到达和建立联系的区别——目的和结果问题
    20世纪60年代,耶鲁大学的社会心理学家米尔格兰姆(Stanley Milgram)就设计了一个连锁信件实验。他将一套连锁信件随机发送给居住在内布拉斯加州奥马哈的160个人,信中放了一个波士顿股票经纪人的名字,信中要求每个收信人将这套信寄给自己认为是比较接近那个股票经纪人的朋友。朋友收信后照此办理。最终,大部分信在经过五、六个步骤后都抵达了该股票经纪人。六度分割(也叫“六度空间”)的概念由此而来。这个故事很多六度的爱好者都知道,并奉为圣经。但是我请大家注意这个故事和我们现在流行的SNS网站的理念的重要差别。在这个故事里面,信到达了波士顿股票经纪人手里面没错,但是请注意整个过程中,每个人的朋友关系都没有发生改变。对,这点很重要,这个故事里面传递的信息,而我们现在看到的SNS网站希望在用户之间传递的是什么呢?是联系方式是朋友关系。
    说到这里想提一下前面提到的火炬的买车票的实验,在那个实验里面,传递的实际上也是信息,而不是朋友关系。

    (3)传递的成本和激励——阻尼问题
    在Stanley Milgram的实验和火炬的实验里面,都没有任何的花费,或者说看起来成本为0。但是是不是真的成本为0呢?每个人传递一下信件花费极低,改下msn名字更是没有成本,然而那些人肯这么做,其实是看着朋友的面子上,所以这里花费的成本实际是什么呢?是中国人说的人情债,所谓的关系成本。没有人喜欢一个整天都要人帮忙这帮忙那的人,人情债和金钱债一样,背了就一定要还,这就是传递中的成本问题。火炬的火车实验后,我们一直在想这个问题,今天我们急需车票,可以请朋友们改他们的名字,但是我们能不能天天都用这种方法来找人帮忙呢?今天买车票,明天买球票,也许一次两次可以,次数多了,朋友们肯定会觉得厌烦,甚至放弃你这个朋友。

    Gmail的邀请方式直至今日仍被很多人称颂,刚刚出现的时候,一个邀请甚至可以卖到60美金。很多人惊呼这是最伟大的营销。然而,到了今天,很多人的邀请已经变得无法送出去。为什么呢?因为一开始的时候Gmail是稀缺物品,所以价值高昂,加上Gmail带有Google的强势品牌和高度用户认同感,所以就更加被追捧,拥有Gmail成了荣誉的象征。这是这种荣誉成为了Gmail邀请在六度网络中疯狂传播的激励。然而随着Gmail的高度普及,这种荣誉感逐步下降,最终降低了激励,从来使传播陷入了停滞状态。

    阻尼是好还是坏?没有阻尼我们可以给任何人发送信息,每个SNS网站都在宣扬你只需要六度就可以认识克林顿可以认识盖茨,但是有几个人真的去认识他们了?是因为他们不值得认识么?不是,是因为联系虽然看起来只有六度,然而每度的阻尼都有可能都是无法跨越的。但是你不要悲观,如果没有阻尼也许你会更加不爽!LLF算过“举例来说吧。假设每个人有30个朋友,信息经过六度是30的6次方 =729000000,数量足够到达一个能够覆盖所有可能的人的级别。”,如果六度的连接没有任何的阻尼,估计我们每天收到的来自六度好友的各种各样的信息就会让我们的脑袋爆炸。

    在我们的生活里面,一个身份越高的人,越有名的人他就会有越多的好友,于是他也就越不想随便拓展自己的关系圈子,因为他们往往不胜其扰。前些日子的600演艺名人联系方式泄露事件就是一个例子,本来我们作为社会一分子都和这600名人有着六度的联系,然而某天因为他们的联系方式被公开,他们和我们的联系立刻被扁平化变成了一度。一瞬间,阻尼消失了,你可以随便打电话给那英、田震了,你不是想跟冯小刚聊电影么?你现在可以打电话了。但是,我们只能说结果这成了一场灾难,很多名人诉苦,说很多人打电话到他们的家里,说了句“你是XXX么?我很喜欢你!”然后就挂了电话。很多人不堪其扰停了机,甚至换了号。

    这场灾难对我们这些局外人来说是一个很有意思的故事,很有趣的一点在于此,一旦这些名人和大众的关系扁平化后(六度变成一度),他们对大众的价值也开始流失,大众们只能打电话过去,问一声,然后炫耀自己给明星打过电话,仅此而已。这个巨大的扁平化工程并没有扩展追星族们的朋友圈子,他们仍旧离那些明星很远……

    (4)朋友的朋友是朋友的假设——关系的方向和传递问题
    SNS网站最爱说的一句话也许就是“朋友的朋友是朋友”,然而那天我跟LLF在Msn聊天的时候就说过这个问题,我认识的某A的朋友某B是我非常反感的一个家伙,而且我的朋友里面还有个人某C对那个家伙某B更加痛恨。所以在现在的SNS服务里面我是不敢把某A和某C同时引入的,因为他们同时引入后,很可能的结果是某B和某C建立联系后,开始吵架。

    六度分割
       上世纪60年代,美国哈佛大学的社会心理学家米尔格伦提出了“六度分割”(Six  Degrees  of  Separation)的理论。简单来说,“六度分割”就是在这个社会里,任何两个人之间建立一种联系,最多需要六个人(不包括这两个人在内),无论这两个人是否认识,生活在地球上任何偏僻的地方,他们之间只有六度分割。

        By now, most people are familiar with the idea of "six degrees of separation". The 1993 film, which starred Will Smith, brought the idea to the general public by using it as the title and main topic of the plot. The idea became more popular through the "Kevin Bacon game", whereby you pick any actor or actress and try to link them, in some way, to the actor Kevin Bacon within "six steps". Entertaining and seemingly frivolous though they are, these popularizing vehicles were based upon a serious academic concept of social interaction and human networks which had been around since the early 1990s.

    The concept, as in the Kevin Bacon game, is that due to the technological advances in communications and transport, human beings are becoming ever more connected. Great distances have less effect upon communication and, therefore, human networks were expanding well beyond previous limits and barriers. The modern world is shrinking.

    Social networks are at the heart of the Kevin Bacon game, and the six degrees of separation concept. A social network is, essentially, a series of connections between individuals or groups of individuals or organizations. One person or group may have many different networks, for example, one person may have a family network, an old school network, a network of friends, a golf playing network, and many others.

    An organization may have an employee network, a supplier network, a client network, etc. Each of these networks is characterized by the type of relationship, or interaction, which connected it. A network of employees might be characterized by an employer, a network of golfers by those who play or are interested in golf. Networks start at the family and go right up to the level of nations. They are the "glue of societies, and are at the basis of all cultures.

    While we probably each recognize that we are all a part of a network, or variety of networks, we don't necessarily think of them as anything more than the people we know in various capacities. Of course, the sorts of networks we are a part of are usually reflective of our domestic lives, our hobbies, our work life, our interests, and so the network itself isn't such a feature as the people that represent it for us. But it is interesting to consider, for a moment, these networks as structures.

    If you were to write down the names of all the people you knew, and placed them each in lists corresponding to how you came to know them through family, golf, school, etc. then you would be close to creating a structural map of your networks. If each of the people in one of your lists then did the same, you could compare lists and then see the true extent of the network. You may only know five golfers, but each of them know five more, and so on. Your recommendation of a particular club could cross national boundaries based upon the advice given to a friend, which got passed on, and passed on.

    In analyzing social networks, greater emphasis is given to those individual people, or groups, who not only have more connections within the specific network, but also are members of more networks. If you and all your golfer friends live in an isolated town where you only play golf and work and go home then your network will be restricted in its effectiveness and would be considered to be a "small and tight" network. Knowledge and opportunities in such networks goes no further than the individuals involved.

    New and fresh members are less likely to join, the network is less likely to expand or stimulate its members any further once the existing knowledge and opportunities have been shared. If, on the other hand, each member of a network is also a member of many other networks then it is "more open" network and will expand and allow a greater circulation of fresh opportunities and wider access to new information. The flow of knowledge and information in such a network is far greater and beneficial to its members.

    If we now apply these ideas to online networking, it should be immediately clear just how useful and beneficial the heightened communication possibilities of a worldwide web of networks would be. Since knowledge and opportunities may be seen as part of the valued currency of a network, then a worldwide platform must be a superior form. With online social network services specializing in this very aspect of networking the ability to join huge, and potentially greatly beneficial, networks is "supercharged".

    转载于:https://www.cnblogs.com/junzhongxu/archive/2008/07/21/1247404.html

    展开全文
  • 4004.六度空间理论

    2018-12-04 19:19:00
    六度空间理论 发布时间: 2018年11月26日 10:17 时间限制: 1000ms 内存限制: 128M 核心思想使用BFS对邻接表扫描6层计数。 描述 “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这...

    六度空间理论

    发布时间: 2018年11月26日 10:17   时间限制: 1000ms   内存限制: 128M

    核心思想是使用BFS对邻接表扫描6层计数。

    描述

    “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

    输入

    多组数据,每组数据m+1行。第一行有两个数字n和m,代表有n个人和m组朋友关系。n个人的编号为1到n。第二行到第m+1行每行包括两个数字a和b,代表这两个人互相认识。当n和m都等于0时,输入结束。

    输出

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

    样例输入1
    10 9
    1 2
    2 3
    3 4
    4 5
    5 6
    6 7
    7 8
    8 9
    9 10
    10 8
    1 2
    2 3
    3 4
    4 5
    5 6
    6 7
    7 8
    9 10
    0 0
    
    样例输出1
    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: 70.00%
    2: 80.00%
    3: 80.00%
    4: 80.00%
    5: 80.00%
    6: 80.00%
    7: 80.00%
    8: 70.00%
    9: 20.00%
    10: 20.00%
     1 #include<iostream>
     2 #include<cstring>
     3 using namespace std;
     4 #define maxn 100
     5 
     6 typedef struct node
     7 {
     8     int data;
     9     struct node *next;
    10 } Node;
    11 
    12 Node *V[maxn];//邻接表
    13 int visit[maxn];
    14 
    15 void BFS(int s, int n)
    16 {
    17     int count = 1;
    18     Node *p;
    19     memset(visit, 0, sizeof(visit));
    20     int Queue[maxn];
    21     int front = 0, rear = 0, last = 0;
    22     Queue[0] = s;
    23     visit[s] = 1;
    24     int six = 0;
    25     while (front <= last)
    26     {
    27         p = V[Queue[front++]]->next;
    28         while (p)//单层遍历,一个人的所有朋友遍历,Queue存储其友
    29         {
    30             if (!visit[p->data])
    31             {
    32                 count++;//计数加一
    33                 visit[p->data] = 1;//改变访问状态
    34                 Queue[++rear] = p->data;//队尾赋值
    35             }
    36             p = p->next;
    37         }
    38         if (front>last)//判断此人的一度朋友是否遍历,如果遍历结束,进入其二度朋友
    39         {
    40             last = rear;
    41             six++;
    42             if (six == 6)
    43                 break;
    44         }
    45     }
    46     printf("%d: %.2f%%\n", s, count*100.0 / n);
    47 }
    48 
    49 int main()
    50 {
    51     int n, m;
    52     int x, y;
    53     Node *p;
    54     while (1)
    55     {
    56         cin >> n >> m;
    57         if (!n&&!m)break;
    58         for (int i = 1; i <= n; i++)
    59         {
    60             V[i] =new Node;
    61             V[i]->data = i;
    62             V[i]->next = NULL;
    63         }//set up 邻接表 index
    64         while (m--)
    65         {
    66             cin>>x>>y;
    67             p = new Node;
    68             p->data = y;
    69             p->next = V[x]->next;
    70             V[x]->next = p;//y follow V[x]
    71             p = new Node;
    72             p->data = x;
    73             p->next = V[y]->next;
    74             V[y]->next = p;//x follow V[y]
    75         }
    76         for (int i = 1; i <= n; i++)
    77             BFS(i, n);
    78     }
    79     return 0;
    80 }

     

    转载于:https://www.cnblogs.com/wind-chaser/p/10066182.html

    展开全文
  • 本文记录数据结构习题解析与实验指导的课后实验八------基于广度优先搜索的六度空间理论的验证。 1 实验内容 问题描述 “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地...

    本文是记录数据结构习题解析与实验指导的课后实验八------基于广度优先搜索的六度空间理论的验证。

    1 实验内容

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

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

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

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

    输出格式:
    对每个结点输出与该结点距离不超过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%
    

    2 基本思路

    这里采用邻接表进行数据存储,由于题目输入的是无向边,所以我们需要对其进行处理。根据题目的输入,建立好树之后,就是利用BFS进行遍历,来寻找范围为6的节点的个数,由于BFS是一个节点一个节点的出队,所以我们要设定一个标识,来表示一层的末尾,当到达末尾时,层数加一,达到六层,就可以退出了,返回节点数(每入一次队,节点数加1)。

    3 核心代码

    1 数据结构代码:

    #include<bits/stdc++.h>
    #define MAXVEX 100
    using namespace std;
    
    typedef struct EdgeNode
    {
        int adjvex;
        int weight;
        EdgeNode *next;
    }EdgeNode;
    
    typedef struct
    {
        int data;
        EdgeNode *firstEdge;
    }vertexNode, AdjList[MAXVEX];
    
    typedef struct
    {
        AdjList adjList;
        int numVertexs, numEdges;
    }GraphAdjList;
    

    2 建树代码:

    void CreateAlGraph(GraphAdjList &g)
    {
        cin>>g.numVertexs>>g.numEdges;
        if (g.numVertexs == 0 && g.numEdges == 0)
        {
            return ;
        }
        int iStart, iEnd;
        for (int i = 0; i < g.numVertexs; ++i)
        {
            g.adjList[i].data = i + 1;
            g.adjList[i].firstEdge = NULL;
        }
        for (int j = 0; j < g.numEdges; ++j)
        {
            cin>>iStart>>iEnd;
            EdgeNode *n = new EdgeNode;
            n->adjvex = iEnd;
            n->weight = 1;
            n->next = g.adjList[iStart - 1].firstEdge;
            g.adjList[iStart - 1].firstEdge = n;
            EdgeNode *n2 = new EdgeNode;
            n2->adjvex = iStart;
            n2->weight = 1;
            n2->next = g.adjList[iEnd - 1].firstEdge;
            g.adjList[iEnd - 1].firstEdge = n2;
        }
    }
    

    因为输入的是无向边,所以需要做两次处理。

    3 BFS遍历代码:

    int BFSTraverse(GraphAdjList &g, int start)
    {
        queue<int> q;
        int cnt = 0;
        int level = 0;
        int last = start;
        int tail = 0;
        int visited[g.numVertexs];
        for (int i = 0; i < g.numVertexs; ++i)
        {
            visited[i] = 0;
        }
        visited[start] = 1;
        q.push(start);
        cnt++;
        EdgeNode *te;
        while (!q.empty())
        {
            int temp = q.front();
            q.pop();
            te = g.adjList[temp].firstEdge;
            while(te != NULL)
            {
                if (!visited[te->adjvex-1])
                {
                    q.push(te->adjvex - 1);
                    visited[te->adjvex - 1] = 1;
                    cnt++;
                    tail = te->adjvex - 1;
                }
                te = te->next;
            }
            if (temp == last)
            {
                last = tail;
                level++;
            }
            if (level == 6)
            {
                break;
            }
        }
        return cnt;
    }
    

    level用来表示层次,到6的时候break.last表示每一层的最末尾节点。而tail用来寻找下一层最末尾节点。当temp==last时,也就是到达这一层的末尾时,tail也刚好到达下一层的末尾,于是将tail的值赋给last,并且层数加一。

    4 全部代码

    #include<bits/stdc++.h>
    #define MAXVEX 100
    using namespace std;
    
    typedef struct EdgeNode
    {
        int adjvex;
        int weight;
        EdgeNode *next;
    }EdgeNode;
    
    typedef struct
    {
        int data;
        EdgeNode *firstEdge;
    }vertexNode, AdjList[MAXVEX];
    
    typedef struct
    {
        AdjList adjList;
        int numVertexs, numEdges;
    }GraphAdjList;
    
    void CreateAlGraph(GraphAdjList &g)
    {
        cin>>g.numVertexs>>g.numEdges;
        if (g.numVertexs == 0 && g.numEdges == 0)
        {
            return ;
        }
        int iStart, iEnd;
        for (int i = 0; i < g.numVertexs; ++i)
        {
            g.adjList[i].data = i + 1;
            g.adjList[i].firstEdge = NULL;
        }
        for (int j = 0; j < g.numEdges; ++j)
        {
            cin>>iStart>>iEnd;
            EdgeNode *n = new EdgeNode;
            n->adjvex = iEnd;
            n->weight = 1;
            n->next = g.adjList[iStart - 1].firstEdge;
            g.adjList[iStart - 1].firstEdge = n;
            EdgeNode *n2 = new EdgeNode;
            n2->adjvex = iStart;
            n2->weight = 1;
            n2->next = g.adjList[iEnd - 1].firstEdge;
            g.adjList[iEnd - 1].firstEdge = n2;
        }
    }
    
    int BFSTraverse(GraphAdjList &g, int start)
    {
        queue<int> q;
        int cnt = 0;
        int level = 0;
        int last = start;
        int tail = 0;
        int visited[g.numVertexs];
        for (int i = 0; i < g.numVertexs; ++i)
        {
            visited[i] = 0;
        }
        visited[start] = 1;
        q.push(start);
        cnt++;
        EdgeNode *te;
        while (!q.empty())
        {
            int temp = q.front();
            q.pop();
            te = g.adjList[temp].firstEdge;
            while(te != NULL)
            {
                if (!visited[te->adjvex-1])
                {
                    q.push(te->adjvex - 1);
                    visited[te->adjvex - 1] = 1;
                    cnt++;
                    tail = te->adjvex - 1;
                }
                te = te->next;
            }
            if (temp == last)
            {
                last = tail;
                level++;
            }
            if (level == 6)
            {
                break;
            }
        }
        return cnt;
    }
    
    void show(GraphAdjList &g)
    {
        EdgeNode *temp;
        for (int i = 0; i < g.numVertexs; ++i)
        {
            temp = g.adjList[i].firstEdge;
            printf("%d",g.adjList[i].data);
            while(temp != NULL)
            {
                printf("-->%d",temp->adjvex);
                temp = temp->next;
            }
            printf("\n");
        }
    }
    
    int main()
    {
        freopen("7.txt","r",stdin);
        GraphAdjList g;
        double result = 0;
        CreateAlGraph(g);
        for (int i = 0; i < g.numVertexs; ++i)
        {
            result = BFSTraverse(g,i);
            printf("%d: %.2f%%\n",i+1,result/g.numVertexs*100);
        }
        //show(g);
        return 0;
    }
    

    其中的7.txt即为题目的输入示例。

    到这里这篇文章就结束了。如果有错误,可以在下方评论,或者私聊我😉,我会及时改正的。

    如果看了有收获,可以点赞加关注😉,看计算机小白的成长之路。

    展开全文
  • 六度空间理论探索 - 维基百科的中心在哪里? ugmbbc发布于 2008-05-29 10:12:01|3914 次阅读 字体:大 小 ...所谓六度空间理论指你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就
  • 六度分隔、六度空间理论资料来源:eureka的blog,2004/01/14-04:47你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。社会网络其实并不高深,它的理论基础正是...
  • 六度空间理论,也成为小世界理论,认为最多可以通过六个人就可以认识你想认识的陌生人,这个数学猜想,如果这个猜想正确的话,那么人类社会中不会存在结构洞。 原创于南开经院图书馆 2011年1月16...
  • 六度空间理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如...
  • 六度空间

    2020-09-07 11:21:50
    六度空间理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如...
  • C语言 六度空间

    千次阅读 2018-06-07 11:49:53
    六度空间理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如...
  • 六度空间 bfs

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

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 196
精华内容 78
关键字:

六度空间理论是最多通过