图论是什么?关于图的理论?下面跟小编具体来了解一下图论以及简单的图论算法吧。
一、图论起源
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
【核心关键词】采购、周期、原材料、企业、产品、成本、要素、库存、供应商、数据分析、生产计划、生产制造、加工制造、技术工 ...
2026-07-08在数据分析、特征工程、机器学习建模的工作流程中，原始数据往往包含多个不同维度的数值指标，例如客户交易数据中的消费金额、交 ...
2026-07-08 很多分析师每天和数据打交道，但当被问到“标签是什么”“标签和指标有什么区别”“标签体系如何设计”时，却常常答不上来。 ...
2026-07-08商业谈判是企业采购合作、渠道签约、价格议价、项目合作、客户签约的核心关键环节，直接决定企业的合作成本、利润空间与经营风险 ...
2026-07-07在数据分析、业务效果验证、AB 测试、学术研究等场景中，T 检验是假设检验体系里最基础、应用最广泛的统计方法，也是均值差异分 ...
2026-07-07 很多数据分析师每天都在写SQL，但当被问到“数据查询语言（DQL）的本质是什么”“SELECT语句中各子句的书写顺序与实际执行顺 ...
2026-07-07【核心关键词】转化率、企业、策略、岗位、互联网、拆分、产品、运营、分析师、指标体系、数据分析、用户画像、数据诊断、产品 ...
2026-07-06在数据分析工作中，文本数据处理是高频刚需场景，用户评论、客服工单、日志信息、调研问卷、商品文案等数据都包含大量文本内容。 ...
2026-07-06 很多数据分析师写过无数个SELECT查询，但当被问到“如何新建一张表来固化中间数据”“创建视图和创建物理表有什么区别”“视 ...
2026-07-06在 CDA 数据分析师能力体系中，透视分析是数据探索、多维度汇总、业务复盘的核心基础技能。无论是 Excel 数据透视表，还是 Power ...
2026-07-03在市场竞争日趋激烈、获客成本持续攀升的当下，企业粗放式的“广撒网”获客模式早已无法适配经营需求。企业经营的核心逻辑，已经 ...
2026-07-03 很多数据分析师精通Excel函数和数据透视表，但当被问到“数据从哪里来”“表和视图有什么区别”“数据库管理系统和SQL是什么 ...
2026-07-03【核心关键词】运营、企业、核心、客户、新技术、数字化运营、数据分析、传统企业、人工录入、生产系统、技术人员、数据安全、 ...
2026-07-02在产品开发、项目立项、业务拓展、运营优化的工作中，市场调查、竞品分析、需求调研是三大核心基础工作。很多从业者容易将三者混 ...
2026-07-02 很多企业团队并非缺乏指标，而是陷入“指标失控”：仪表盘上堆满实时跳动的数据，却无法回答“当前瓶颈在哪、下一步该做什么 ...
2026-07-02在MySQL数据库运维与开发工作中，当单表数据量达到千万级、亿级后，会出现查询卡顿、索引失效、写入性能下降等问题。为优化性能 ...
2026-07-01在信息化建设、系统开发、数据分析、需求梳理的工作场景中，业务模型与逻辑模型是两个最基础、也最容易混淆的核心概念。很多项目 ...
2026-07-01 很多数据分析师能熟练计算各种指标，但当被问到“这些指标之间是什么关系”“为什么要选这个指标而不是那个”“指标体系的整 ...
2026-07-01【核心关键词】报表、数据源、客户、营销、业绩、销售、时效性、函数、可视化、运营、数据分析、数据报表、业务部门、数据运营 ...
2026-06-30在数据分析、商业预测、经济统计、运维监控等领域中，绝大多数业务数据都具备时间连续性特征，例如月度销售额、日度客流量、季度 ...
2026-06-30
京公网安备 11010802034615号
经营许可证编号：京B2-20210330
