数据结构——六度空间理论验证

这篇具有很好参考价值的文章主要介绍了数据结构——六度空间理论验证。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、实验项目要求

1.输入格式:

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

输出格式:

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

二、理论分析

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

三、实现方法

#include<iostream>
#include<iomanip>
using namespace std;

#define MaxVertexNum 10000
#define MaxDistance 6
#define DefaultWeight 1
#define QERROR 0

typedef int Vertex;
typedef int WeightType;


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


typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode {
    Vertex AdjV; 
    WeightType Weight;
    PtrToAdjVNode Next;
};


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


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


typedef struct Node* PtrToNode;
struct Node {
    Vertex Data;
    PtrToNode Next;
};
typedef PtrToNode Position;


struct QNode {
    Position Front, Rear;
    int MaxSize;
};
typedef struct QNode* Queue;

LGraph CreateGraph(int Nv);
void InsertEdge(LGraph Graph, Edge E);
void BFSToSix(LGraph Graph);
int BFS(LGraph Graph, Vertex v);
Queue CreateQueue(int MaxSize);
bool QIsEmpty(Queue Q);
Vertex DeleteQ(Queue Q);
void AddQ(Queue Q, Vertex v);

int main()
{
    
    int N, M;
    LGraph Graph;
    Edge E;

    cin >> N; 
    Graph = CreateGraph(N); 

    cin >> M; 
    E = new ENode;
    for (int i = 0; i < M; i++) {
        cin >> E->V1;
        cin >> E->V2;
        E->Weight = DefaultWeight;
        InsertEdge(Graph, E);
    }

    BFSToSix(Graph);

    return 0;
}

void BFSToSix(LGraph Graph)
{
    int SixVertexNum;
    float percent;
    if (Graph->Nv != 0) {
        for (Vertex v = 1; v < Graph->Nv; v++) {
           
            SixVertexNum = BFS(Graph, v) + 1;
          
            percent = float(SixVertexNum) / float(Graph->Nv - 1);
            cout << v << ":" <<" ";
            cout<<fixed <<setprecision(2)<<percent * 100 << "%" << endl;
           
            for (int i = 0; i < Graph->Nv; i++) Graph->visited[i] = false;
        }
    }
}

int BFS(LGraph Graph, Vertex v)
{
    PtrToAdjVNode w;
    int D = 0;
    int SixVertexNum = 0;
    Queue Q;

    Q = CreateQueue(MaxVertexNum);//创建队列

    Graph->visited[v] = true;
    AddQ(Q, v);
    AddQ(Q, 0);//插入队列中的0,用于表示新的一层的开始
    ++D;
    while (!QIsEmpty(Q)) {
        v = DeleteQ(Q);
        if (v == 0 && D >= MaxDistance) break; //表示层数已超过6
        if (v == 0 && D < MaxDistance) {//层数还未超过6
            AddQ(Q, 0);
            ++D;
            continue;
        }
        for (w = Graph->G[v].FirstEdge; w != NULL; w = w->Next) {

            if (!Graph->visited[w->AdjV]) {
                Graph->visited[w->AdjV] = true;
                AddQ(Q, w->AdjV);
                ++SixVertexNum;
            }
        }
    }
    return SixVertexNum;
}

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

    ++Graph->Ne;

    NewNode = new AdjVNode;
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;


    NewNode = new AdjVNode;
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph CreateGraph(int N)
{
    LGraph Graph;

    Graph = new GNode;
    Graph->Nv = N + 1; //结点从1开始
    Graph->Ne = 0;
    Graph->visited = new bool[N + 1];

    for (int i = 1; i < Graph->Nv; i++) Graph->visited[i] = false;

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

    return Graph;
}

Queue CreateQueue(int MaxSize)
{
    Queue Q;
    Q = new QNode;
    Q->Front = Q->Rear = NULL;
    Q->MaxSize = MaxSize;
    return Q;
}

bool QIsEmpty(Queue Q)
{
    return (Q->Front == NULL);
}

void AddQ(Queue Q, Vertex v)
{
    Position NewNode;
    NewNode = new Node;
    NewNode->Data = v;
    NewNode->Next = NULL;

    if (QIsEmpty(Q)) {
        Q->Front = NewNode;
        Q->Rear = NewNode;
    }
    else {
        Q->Rear->Next = NewNode;
        Q->Rear = NewNode;
    }
}

Vertex DeleteQ(Queue Q)
{
    Position FrontNode;
    Vertex FrontData;

    if (QIsEmpty(Q)) {
        return QERROR;
    }
    else {
        FrontNode = Q->Front;
        if (Q->Front == Q->Rear)
            Q->Front = Q->Rear = NULL;
        else
            Q->Front = Q->Front->Next;

        FrontData = FrontNode->Data;
        delete FrontNode;
        return FrontData;
    }

}

四、实验结果分析

基于广度优先搜索的六度空间理论的验证,数据结构,数据结构,图论

 文章来源地址https://www.toymoban.com/news/detail-517931.html

到了这里,关于数据结构——六度空间理论验证的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——空间复杂度

    3.空间复杂度 空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进

    2024年02月13日
    浏览(35)
  • 【数据结构】 二叉树理论概念!一文了解二叉树!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 数据结构解析 🌄 莫道桑榆晚,为霞尚满天! 什么是二叉树?二叉树的组成构造是什么样的?我们将由浅入深,循序渐进的方式把二叉树给搞明白,让你彻底了解二叉树! 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一

    2024年02月05日
    浏览(48)
  • 数据结构-时间空间复杂度

    目录 前言 1.什么是数据结构 2.什么是算法 3.数据结构和算法的重要性 1.算法的时间复杂度和空间复杂度 1.1算法效率 1.1.1如何衡量一个算法的好坏 1.1.2算法的复杂度 1.2时间复杂度 1.2.1时间复杂度的概念 1.2.2大O的渐进表示法 2.编程练习 2.1.1 排序+遍历 2.1.2 2.1.3 单身狗解法 1.3空

    2024年02月15日
    浏览(51)
  • 【数据结构】时间、空间复杂度

    ⭐ 作者:小胡_不糊涂 🌱 作者主页:小胡_不糊涂的个人主页 📀 收录专栏:浅谈数据结构 💖 持续更文,关注博主少走弯路,谢谢大家支持 💖 算法效率分析分为两种:第一种是 时间效率 ,第二种是 空间效率 。 时间效率 被称为 时间复杂度 ,而 空间效率 被称作 空间复

    2024年02月07日
    浏览(52)
  • 数据结构--时间/空间复杂度

    时间复杂度简单的说就是一个程序运行所消耗的时间,叫做时间复杂度,我们无法目测一个程序具体的时间复杂度,但是我们可以估计大概的时间复杂度。 一段好的代码的就根据算法的时间复杂度,即使在大量数据下也能保持高效的运行速率,这也是我们学习算法的必要性。

    2024年02月14日
    浏览(35)
  • 2.数据结构--空间复杂度

    1.空间复杂度也是一个数学表达式,是 对一个算法在运行过程中临时占用额外的存储空间大小的量度 2.空间复杂度 算的是变量的个数 3.函数运行时所需要的栈空间(存储参数,局部变量,一些寄存器信息等)在编译期间就已经确定好了,因此 空间复杂度主要通过函数在运行

    2024年02月16日
    浏览(38)
  • 【数据结构】 时间和空间复杂度

    我们知道一道题,有许多种代码可以实现它。但是我们应该怎么去选择呢? 比如博主在前面讲过的斐波那契数,我们可以用递归和循环来实现。那么到底那一种方法好呢?为什么?该如何衡量一个算法的好坏呢?这就涉及到了一个新的概念—— 算法效率 算法效率分析分为两

    2024年02月12日
    浏览(36)
  • 【数据结构】时间和空间复杂度

     马上就要进入到数据结构的学习了 ,我们先来了解一下 时间和空间复杂度,这也可以判断我们的算法是否好坏; 就是看它的算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度

    2024年02月05日
    浏览(45)
  • 自然语言处理 Paddle NLP - 结构化数据问答-理论

    基础 自然语言处理(NLP) 自然语言处理PaddleNLP-词向量应用展示 自然语言处理(NLP)-前预训练时代的自监督学习 自然语言处理PaddleNLP-预训练语言模型及应用 自然语言处理PaddleNLP-文本语义相似度计算(ERNIE-Gram) 自然语言处理PaddleNLP-词法分析技术及其应用 自然语言处理Pa

    2024年02月11日
    浏览(62)
  • 数据结构介绍与时间、空间复杂度

    什么是数据结构? 什么是算法? 数据结构和算法的重要性 数据结构是计算机科学中研究数据组织、存储和管理的一门学科。数据结构描述了数据对象之间的关系,以及对数据对象进行操作的方法和规则。 常见的数据结构 数组(Array):连续存储相同类型的数据元素。 链表

    2024年02月08日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包