图论是什么?关于图的理论?下面跟小编具体来了解一下图论以及简单的图论算法吧。
一、图论起源
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-09-29在数据分析与统计学研究中，数据往往不是独立存在的，不同变量之间普遍存在相互关联、相互影响的关系。相关性统计分析是挖掘变量 ...
2026-09-29 导读：大多数人只把 dataclasses 当成偷懒工具，用来少写 __init__、__repr__ 这类魔法方法。但它的能力远不止于此。本文带 ...
2026-09-29 很多数据分析师能熟练地计算指标、搭建标签体系，但当被问到“画像到底在解决什么问题”“画像和标签是什么关系”“画像如何 ...
2026-09-29在MySQL数据库运维与业务开发中，行业普遍存在“数据达到千万级就必须分表”的说法。但在实际生产环境中，千万条数据并不是强制 ...
2026-09-28CDA数据分析师 出品 作者：李诗怡 1. 5W1H 分析法 定义：经典系统性思维框架，通过六个核心维度对问题进行全方位拆解与剖析，确 ...
2026-09-28 很多分析师在设计标签时思路清晰，但真到落地环节却面临“数据在手，不知如何转化为可用标签”的困境：或因加工方式选择不当 ...
2026-09-28CDA数据分析师 出品 作者：李诗怡 1. 用户标签体系 定义： 通过一系列高度精炼的特征标识，对用户属性、行为与偏好进行量化刻画 ...
2026-09-24Pandas是Python生态中用于表格数据处理的核心库，广泛应用于数据清洗、统计运算、报表输出、数据分析建模等场景。在处理极大数值 ...
2026-09-24随着数字经济快速发展，数据已成为核心生产要素，各行各业的业务沉淀、用户行为、设备运行、市场交易均产生海量数据。数据处理作 ...
2026-09-24 很多分析师每天和数据打交道，但当被问到“标签是什么”“标签和指标有什么区别”“标签体系如何设计”时，却常常答不上来。 ...
2026-09-24在时序数据分析中，大部分业务数据并非持续平稳变化，而是会在某些时间节点出现突然抬升、断崖下跌、趋势反转、波动异变等现象， ...
2026-09-23在统计学与数据分析中，研究多组数据差异最常用的方法为单因素方差分析与事后多重比较。很多数据分析初学者容易混淆两者功能，认 ...
2026-09-23 很多数据分析师每天都在写 SQL，但当被问到“DQL 的本质是什么”“SELECT 子句的书写顺序与执行顺序为何不同”“INNER JOIN ...
2026-09-23 很多数据分析师写过无数个SELECT查询，但当被问到“如何新建一张表来固化中间数据”“创建视图和创建物理表有什么区别”“视 ...
2026-09-22CDA数据分析师 出品 作者：李诗怡 1. 金字塔原理 定义： 一种“先总后分、先结论后原因”的思考和表达方式。顶层为核心观点，中 ...
2026-09-22数据收集是数据分析、数据挖掘与数字化运营的源头工作，数据收集的完整性、准确性、时效性直接决定后续数据分析结果的可信度与业 ...
2026-09-21箱线图是数据分析中用于识别数据分布、判断离散程度、筛查异常值的核心图表。相比于直方图、趋势图，箱线图可以精准区分正常数据 ...
2026-09-21 很多数据分析师精通Excel函数和数据透视表，但当被问到“数据从哪里来”“表和视图有什么区别”“数据库管理系统和SQL是什么 ...
2026-09-21在数据库数据查询与数据分析工作中，日期时间是最常用的数据类型之一。原始数据库中存储的日期格式多为标准时间戳、年月日时分秒 ...
2026-09-20
京公网安备 11010802034615号
经营许可证编号：京B2-20210330
