精华内容
下载资源
问答
  • 六度空间 c语言 【详解】
    千次阅读
    2019-12-29 18:09:27

    六度空间

    六度空间”理论又称作“六度分隔(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)将输入的关系建立成一个二维数组relation[人数][人数],其中第i行第j列为1则代表i与j有关系
    (2)用一个数组visit[人数]记录第i个人是否已经访问
    (3)用一个数组queue[人数]记录需要遍历其广度的人的队列
    (4)从编号为1的人开始,记录下他的一层所有关系的广度,每遍历到一个人,如果这个人对应的visit数组中为0,则代表这个人还未访问过,将这个遍历到的人入queue数组,再将对应的visit中的数值改为1,如果到了relation数组第n维的最后一个人,用tail记录下这个人的编号,代表着此层的最后一个人。
    (5)遍历queue数组的人的关系,当在queue中遍历到此tail编号的人的广度时,层数加1
    (6)当层数为6时,停止该人的遍历,转到下个编号的人的遍历

    代码

    #include<stdio.h>
    #include<malloc.h>
    #define MAX 1001
    
    int count(int num,int N,int **relation){ //对第num个人进行六度空间内有关联的人的计数
        int queue[MAX]; //queue数组模拟一个队列,记录需要遍历其关系的人(需要遍历第num个人认识的人)
        int front=-1,rear=-1; //front和rear模拟头尾指针,分别是queue的队列头和尾。
        int sum=1; //记录所有在六度内认识的人。
        int level=0; //记录当前的层数,便于按层遍历,当层数为6时,退出
        int levellast=num; //记录每一层最后的一个人的编号,当遍历到这个编号时,层数加1.
        int visit[MAX]={0};//记录对每个人是否已经访问过的情况,防止出现重复遍历,初始状态为全都没有遍历
        int last;
        visit[num]=1;
        queue[++rear]=num; //参数num为queue第一个元素,是第一个需要遍历其关系的人
        while(front<rear){//对待遍历队列进行遍历
            int  t=queue[++front]; //t为第一个需要遍历其关系的人
            for(int i=1;i<=N;i++) { //开始遍历该人的关系(即数组的第二维)
                if (!visit[i] && relation[t][i] == 1) { //如果第num个人和第i个人有关系且i尚未访问
                    queue[++rear] = i; //将该第i个人记录进入待访问数组,在下层进行访问
                    visit[i] = 1; //将该点记录已经访问
                    sum+=1; //认识的总人数加1
                    last=i; //记录下当层的最后一个结点
                }
            }
                if(t==levellast){ //如果已经到了一层的最后一个结点
                    level+=1; //层数加1
                    levellast=last;
                }
                if(level==6) break;
            }
            return sum; //返回总人数
        }
    
    int main(void){
        int num1,num2; //人数,关系数
        scanf("%d",&num1); //输入人数
        scanf("%d",&num2); //输入关系数
        int **relation; //二维数组,记录两个人之间的关系矩阵
        relation = (int**)malloc(sizeof(int*)*(num1+1)); //分配空间
        for (int i=0;i<=num1;i++){ //分配空间
            *(relation+i)=(int *)malloc(sizeof(int)*(num1+1));
        }
    
        for(int i=0;i<=num2-1;i++){ //记录一个关系的两端的结点
            int x,y; //记录一个关系的两端的结点
            scanf("%d",&x);
            scanf("%d",&y);
            relation[x][y]=relation[y][x]=1; //无向图的关系矩阵一定是对称的
        }//关系录入完成
        for(int i=1;i<=num1;i++){ //循环输出每个人的六度内的认识的人的比
            printf("%d: %.2f%%\n",i,((float)count(i,num1,relation)/num1)*100);
        }
    }
    
    
    更多相关内容
  • http://blog.csdn.net/xkzju2010/article/details/46503251
  • 六度空间

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

    六度空间
    “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
    在这里插入图片描述
    “六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

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

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

    解法:使用图的BFS算法,使用邻接表存储图,同时每个节点存储图节点的深度信息,对>6的节点不搜索。

    def BFS(L,k):
    	import copy
    	l=copy.deepcopy(L)
    	count=0
    	buf=[]
    	buf.append(k)
    	visited=[0 for i in range(len(L))]
    	while buf!=[]:
    		t=buf[0]
    		visited[t]=1
    		count+=1
    		del buf[0]
    		for i in l[t][1:]:
    			if i not in buf and visited[i]==0:
    				l[i][0]=l[t][0]+1
    				if l[i][0]<=6:
    					buf.append(i)
    	return count
    
    N,M=list(map(int,input().split()))
    #列表0号元素为层次
    L=[[0] for i in range(N)]
    #将1~N映射为0~N-1 用邻接表存储 给每个节点设置权重
    for k in range(M):
    	i,j=list(map(int,input().split()))
    	L[i-1].append(j-1)
    	L[j-1].append(i-1)
    
    #print(L)
    for k in range(N):
    	print(str(k+1)+': %.2f%%'%(BFS(L,k)/N*100))
    
    

    但这样内存耗费比较多,PTA最后一组测试没通过。
    在这里插入图片描述
    改进法:认为每个节点入队即代表被访问,这样就不需要if i not in buf这个判断(这个判断额外增加O(n)时间复杂度);不给每个节点添加层次信息,通过tail跟踪当前节点,last指向上一层节点,level表示当前层次数目。

    #还要改进,这里的buf不应该用来判断是否在里面
    def BFS(L,k):
    	import copy
    	l=copy.deepcopy(L)
    	buf=[]
    	buf.append(k)
    	count=1
    	visited=[0 for i in range(len(L))]
    	visited[k]=1
    	tail=k#指向跟踪当前层次节点
    	last=k#指向上一层次最后一个节点
    	level=0
    	while buf!=[]:
    		if level==6:
    			return count
    		for i in l[buf[0]]:
    			if visited[i]==0:
    				buf.append(i)
    				count+=1
    				visited[i]=1#只要入队就认为访问了
    				tail=i	
    		if buf[0]==last:
    			level+=1
    			last=tail
    		del buf[0]		
    	return count
    
    N,M=list(map(int,input().split()))
    L=[[] for i in range(N)]
    #将1~N映射为0~N-1 用邻接表存储
    for k in range(M):
    	i,j=list(map(int,input().split()))
    	L[i-1].append(j-1)
    	L[j-1].append(i-1)
    
    #print(L)
    for k in range(N):
    	print(str(k+1)+': %.2f%%'%(BFS(L,k)/N*100))
    
    

    但是最后一个测试仍然没通过,感觉是l=copy.deepcopy(L)时间复杂度为O(n^​2),
    因为L有两层,deepcopy就会复制两层,导致整个搜索效率为O(n^3)。

    仔细观察,发现前面之所以要加copy是因为第一种给节点加层次序号的方法,在BFS中会修改图,所以需要copy,而第二种方法并没有改变图,所以不需要copy,直接使用L即可,最终成功运行。

    由此分析,第一次没成功的原因不仅仅与空间复杂度有关,还与python的copy所带来的时间复杂度有关(层次越深,复杂度是幂函数数量级增加)

    def BFS(L,k):
    	buf=[]
    	buf.append(k)
    	count=1
    	visited=[0 for i in range(len(L))]
    	visited[k]=1
    	tail=k#指向跟踪当前层次节点
    	last=k#指向上一层次最后一个节点
    	level=0
    	while buf!=[]:
    		if level==6:
    			return count
    		for i in L[buf[0]]:
    			if visited[i]==0:
    				buf.append(i)
    				count+=1
    				visited[i]=1#只要入队就认为访问了
    				tail=i	
    		if buf[0]==last:
    			level+=1
    			last=tail
    		del buf[0]		
    	return count
    
    N,M=list(map(int,input().split()))
    L=[[] for i in range(N)]
    #将1~N映射为0~N-1 用邻接表存储
    for k in range(M):
    	i,j=list(map(int,input().split()))
    	L[i-1].append(j-1)
    	L[j-1].append(i-1)
    
    #print(L)
    for k in range(N):
    	print(str(k+1)+': %.2f%%'%(BFS(L,k)/N*100))
    
    
    展开全文
  • 算法 图3 六度空间

    千次阅读 2020-03-31 21:19:00
    题目:“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人...

    全部每周作业和视频思考题答案和解析 见 浙江大学 数据结构 思考题+每周练习答案汇总

    题目:“六度空间”理论又称作“六度分隔(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%

    解答:

    据作业上介绍说这个题也是有点麻烦。毕竟前面所有题都做出来了,不能因为这个题麻烦就放弃(再麻烦能有前面的哈夫曼编码那个麻烦么)。

    结果没想到半个小时就写完了,竟然比前面两个算法还要容易。

    其实视频里说的很明确了。这里编程要注意每次从一个点进行遍历的时候都把Visit标记给清零,然后,每次都要把队列清空,不然就会出错。

    #include <iostream>
    #include <map>
    #include <queue>
    #include <vector>
    #include <string>
    #include <stdio.h>
    using namespace std;
    int Graph[1002][1002];
    bool visit[1002];
    void initGraph(int N);
    void recovGraph(int N);
    void generateGra(int N, int M);
    void SDS(int N);
    int main(void) {
    	int N,M;
    	cin >> N >> M;
    	initGraph(N);
    	generateGra(N,M);
    
    	SDS(N);
    	system("pause");
    	return 0;
    }
    
    void initGraph(int N) {
    	//编号从1到N
    	for (int i = 0;i <= N;i++) {
    		visit[i] = 0;
    		for (int j = 0;j <= N;j++) {
    			Graph[i][j] = 0;
    			if (i == j) {
    				Graph[i][j] = 1;
    			}
    		}	
    	}
    }
    void recovGraph(int N) {
    	for (int i = 1;i <= N;i++) {
    		visit[i] = 0;
    	}
    }
    
    void generateGra(int N,int M) {
    	//M为连线的数量
    	for (int i = 0;i < M;i++) {
    		int a, b;
    		cin >> a >> b;
    		Graph[a][b] = 1;
    		Graph[b][a] = 1;
    	}
    	/*
    	for (int i = 1;i <= N;i++) {
    		for (int j = 1;j <= N;j++) {
    			cout << Graph[i][j] << " ";
    		}
    		cout << endl;
    	}*/
    }
    
    queue<int> myQueue;
    int BFS(int i,int N)
    {
    	int count = 1;
    	visit[i] = 1;
    	int level = 0; int last = i;
    	int tail;
    	myQueue.push(i);
    	while (!myQueue.empty()) {
    		i = myQueue.front();myQueue.pop();
    		for (int j = 1;j<=N;j++)
    			if (visit[j] == 0 && Graph[i][j] == 1) {
    				visit[j] = 1;
    				myQueue.push(j); count++;
    				tail = j;
    			}
    		if (i == last) {
    			level++; last = tail;
    		}
    		if (level == 6) break;
    	}
    	//之前忘了清空队列,导致一直出错
    	while (!myQueue.empty()) {
    		myQueue.pop();
    	}
    	return count;
    }
    
    void SDS(int N)
    {
    	for (int i = 1;i<=N;i++) {
    		recovGraph(N);
    		int count = BFS(i,N);
    		double rate =  ((double)count / (double)N)*100;
    		cout << i << ": ";
    		printf("%.2f", rate);
    		cout << "%" <<endl;
    	}
    }

    运行结果如下:

    值得注意的是,这里因为最后一个测试中节点个数特别多,耗时也很大,竟然用了半秒钟。其实如果是用邻接表这种结构来操作会更省时间(这启示我们不要仅仅运行出结果就结束,还应该思考更好的解决方法)。

    BFS找六层然后就退出的算法在视频里有,这里就不再介绍了。

    展开全文
  • 本文是记录数据结构习题解析与实验指导的课后实验八------基于广度优先搜索的六度空间理论的验证。 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即为题目的输入示例。

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

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

    展开全文
  • 什么是六度空间理论.doc
  • 六度空间的猜想与验证.pdf
  • 六度空间理论

    千次阅读 2018-05-31 19:40:14
    06-图3 六度空间(30 分)“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就...
  • 六度空间创业项目计划书.doc
  • 六度空间理论、六度分隔理论.docx
  • 六度空间的猜想与验证-10页.pdf
  • PTA 数据结构与算法 7-7 六度空间

    千次阅读 2019-05-22 21:03:05
    六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图1...
  • ——六度空间 1. 实验目的 熟练掌握图的存储结构及广度优先遍历方法。 2. 实验内容 “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所...
  • 7-7 六度空间 (30 分)

    千次阅读 2019-05-21 17:52:32
    7-7 六度空间 (30 分) “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够...
  • 7-2 六度空间(30 分)

    千次阅读 2018-06-01 10:02:08
    7-2 六度空间(30 分)“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够...
  • C语言 六度空间

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

    千次阅读 2017-10-07 15:18:06
    7-1 六度空间(30 分) “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就...
  • 假如给你一个社交网络图,请你对每个节点计算符合六度空间理论的结点总数的百分比。 (1)输入:输入第1行给出两个正整数,分别表示社交网络图的结点数N(1,表示人数)、边数M(*N,表示社交关系数)。随后的M行对应M条边...
  • 六度空间(广度优先搜索)

    千次阅读 2019-12-04 21:42:28
    广度优先搜索 六度空间 题目 “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就...
  • 六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如...
  • 【图(上)】六度空间

    千次阅读 2018-11-02 00:11:20
    六度空间(Six Degrees of Separation) 你和任何一个陌生人之间所间隔的人不会超过六个 题目:给定社交网络图,请对每个节点计算符合“六度空间”理论的结点占结点总数的百分比 算法思路: 对每个节点,进行...
  • 5-7 六度空间 (30分)

    千次阅读 2016-08-26 08:09:40
    5-7 六度空间 (30分) “六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识...
  • 原理就看书吧,看书吧,六度空间的解读好麻烦啊, 陈越姥姥的讲解赛高了。“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人...
  • 《数据结构》06-图3 六度空间

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 148,836
精华内容 59,534
关键字:

六度空间