图论是什么?关于图的理论?下面跟小编具体来了解一下图论以及简单的图论算法吧。
一、图论起源
18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点?欧拉于1736年研究并解决了此问题，他把问题归结为如右图的“一笔画”问题，证明上述走法是不可能的。
以此，我们来看图论的概念：
图论〔Graph Theory〕以图为研究对象。在图论中，一般只存在两种形态：节点和边。
节点，也就是上述故事问题引入中的四块陆地——河的两岸，两个小岛。vertex-节点，因为首字母是V，所以用V来代表节点。
边，也就是上面故事里提到的七座桥。边(edge)，因首字母为E，所以简称E。
在图论中，我们通常用G来表示图
所以：G=(V,E)。
二、图论最简单算法
1.最短路径
我们主要考虑单源最短路径问题，也就是给定一个赋权图G=(V,E)，和一个特定的顶点s作为输入，找出从s到G中每一个其他顶点的最短赋权路径。
(1)从一个特定的顶节点s出发，那么从s到s的最短路径长度就是0;
(2)需要找到和s相邻的节点，这些节点到s的最短距离为1.把这些顶点标记，代表着已经找到了s到这些节点的最短路径。
(3)寻找距离s为2的节点，从s的邻点a出发，找到距离a为1的那些还未标记的节点，那么，理所当然的，s到这些顶点的最短路径为2.对这些节点进行标记。
(4)一直到全部点被标记，程序结束。
2.最小生成树
简单来说，对于一个有 n 个点的图，边一定是大于等于 n-1 条的，最小生成树，就是在这些边中选择 n-1 条出来连接所有的 n 个点，且这 n-1 条边的边权之和是所有方案中最小的。
最小生成树具有以下两条性质：
切割性质：连接点 x、y 的边权最小的边必定被生成树包含
回路性质：任意回路/环上的边权最大的边必不被生成树包含
求最小生成树一般有 Prim 算法与 Kruskal 算法，其中，Prim 算法时间复杂度为 O(V*V)，与图中边数无关，适合稠密图;Kruskal 算法时间复杂度 为O(ElogE)，需要对图的边进行访问，适合稀疏图。
数据分析咨询请扫描二维码
若不方便扫码，搜微信号：CDAshujufenxi
在 DDPM（Denoising Diffusion Probabilistic Models）训练过程中，开发者最常困惑的问题莫过于：“我的模型 loss 降到多少才算 ...
2025-11-04在 CDA（Certified Data Analyst）数据分析师的工作中，“无监督样本分组” 是高频需求 —— 例如 “将用户按行为特征分为高价值 ...
2025-11-04当沃尔玛数据分析师首次发现 “啤酒与尿布” 的高频共现规律时，他们揭开了数据挖掘最迷人的面纱 —— 那些隐藏在消费行为背后 ...
2025-11-03这个问题精准切中了配对样本统计检验的核心差异点，理解二者区别是避免统计方法误用的关键。核心结论是：stats.ttest_rel（配对 ...
2025-11-03在 CDA（Certified Data Analyst）数据分析师的工作中，“高维数据的潜在规律挖掘” 是进阶需求 —— 例如用户行为包含 “浏览次 ...
2025-11-03在 MySQL 数据查询中，“按顺序计数” 是高频需求 —— 例如 “统计近 7 天每日订单量”“按用户 ID 顺序展示消费记录”“按产品 ...
2025-10-31在数据分析中，“累计百分比” 是衡量 “部分与整体关系” 的核心指标 —— 它通过 “逐步累加的占比”，直观呈现数据的分布特征 ...
2025-10-31在 CDA（Certified Data Analyst）数据分析师的工作中，“二分类预测” 是高频需求 —— 例如 “预测用户是否会流失”“判断客户 ...
2025-10-31在 MySQL 实际应用中，“频繁写入同一表” 是常见场景 —— 如实时日志存储（用户操作日志、系统运行日志）、高频交易记录（支付 ...
2025-10-30为帮助教育工作者、研究者科学分析 “班级规模” 与 “平均成绩” 的关联关系，我将从相关系数的核心定义与类型切入，详解 “数 ...
2025-10-30对 CDA（Certified Data Analyst）数据分析师而言，“相关系数” 不是简单的数字计算，而是 “从业务问题出发，量化变量间关联强 ...
2025-10-30在构建前向神经网络（Feedforward Neural Network，简称 FNN）时，“隐藏层数目设多少？每个隐藏层该放多少个神经元？” 是每个 ...
2025-10-29这个问题切中了 Excel 用户的常见困惑 —— 将 “数据可视化工具” 与 “数据挖掘算法” 的功能边界混淆。核心结论是：Excel 透 ...
2025-10-29在 CDA（Certified Data Analyst）数据分析师的工作中，“多组数据差异验证” 是高频需求 —— 例如 “3 家门店的销售额是否有显 ...
2025-10-29在数据分析中，“正态分布” 是许多统计方法（如 t 检验、方差分析、线性回归）的核心假设 —— 数据符合正态分布时，统计检验的 ...
2025-10-28箱线图（Box Plot）作为展示数据分布的核心统计图表，能直观呈现数据的中位数、四分位数、离散程度与异常值，是质量控制、实验分 ...
2025-10-28在 CDA（Certified Data Analyst）数据分析师的工作中，“分类变量关联分析” 是高频需求 —— 例如 “用户性别是否影响支付方式 ...
2025-10-28在数据可视化领域，单一图表往往难以承载多维度信息 —— 力导向图擅长展现节点间的关联结构与空间分布，却无法直观呈现 “流量 ...
2025-10-27这个问题问到了 Tableau 中两个核心行级函数的经典组合，理解它能帮你快速实现 “相对位置占比” 的分析需求。“index ()/size ( ...
2025-10-27对 CDA（Certified Data Analyst）数据分析师而言，“假设检验” 绝非 “套用统计公式的机械操作”，而是 “将模糊的业务猜想转 ...
2025-10-27
京公网安备 11010802034615号
经营许可证编号：京B2-20210330
