豆瓣知乎数据图分析：C+++Dijkstra+Prim算法详解

本篇文档详细介绍了使用C++、JSON和QT进行图分析的过程和技术细节。作者江俊广和毛誉陶合作的项目选取了豆瓣影评和知乎话题数据集作为研究对象，主要关注图的构建、核心算法实现以及可视化展示。 1. 数据集： 文档提及的两个数据集分别是豆瓣影评数据集和自采的知乎话题数据，这两个数据集用于构建和分析网络图。 2. 图分析框架与流程： - 网络图构建：主要使用C++实现，由于其时间和空间需求较大，一旦构建完成，结果会保存在"output/network.csv"文件中，不再重复执行。 - 核心算法实现：C++编程实现包括Dijkstra算法（用于计算最短路径）和Prim算法（用于求最小生成树），它们都属于优先级搜索算法，但Dijkstra采用边的权重进行优先级计算。 - 可视化：采用QT负责用户交互界面，D3库则用于图的可视化展示。 3. 算法实现细节： - 单连通域优先级搜索（PFS）：采用优先级队列进行，初始所有节点未访问，优先级最低。每次从队列中取出优先级最高的节点，更新其邻居节点的优先级并入队。 - 多连通域PFS：对于多连通区域，只需对所有未访问节点分别进行单连通域搜索，时间复杂度为O(n+e)，其中n为节点数，e为边数。 4. 边权重计算： 在网络图构建阶段，用户之间的关系权重取两者之间的最大值。在后续的最短路径和最小生成树计算中，边的权重采用的是网络图构建时的关系权重加上特定的计算公式。 5. 程序运行环境： 项目在Mac联网环境下运行，强调了网络连接对于数据处理和可视化的重要性。 这篇文档深入探讨了如何利用C++处理大规模网络数据，结合Dijkstra和Prim算法，以及如何通过QT和D3库实现用户交互和图形展示，为读者提供了图分析的完整流程和技术细节。