图论是什么?关于图的理论?下面跟小编具体来了解一下图论以及简单的图论算法吧。
一、图论起源
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
R 语言：数据科学与科研领域的核心工具及优势解析 一、引言 在数据驱动决策的时代，无论是科研人员验证实验假设（如前文中的 T ...
2025-09-08T 检验在假设检验中的应用与实践 一、引言 在科研数据分析、医学实验验证、经济指标对比等领域，常常需要判断 “样本间的差异是 ...
2025-09-08在商业竞争日益激烈的当下，“用数据说话” 已从企业的 “加分项” 变为 “生存必需”。然而，零散的数据分析无法持续为业务赋能 ...
2025-09-08随机森林算法的核心特点：原理、优势与应用解析 在机器学习领域，随机森林（Random Forest）作为集成学习（Ensemble Learning） ...
2025-09-05Excel 区域名定义：从基础到进阶的高效应用指南 在 Excel 数据处理中，频繁引用单元格区域（如A2:A100、B3:D20）不仅容易出错， ...
2025-09-05CDA 数据分析师：以六大分析方法构建数据驱动业务的核心能力 在数据驱动决策成为企业共识的当下，CDA（Certified Data Analyst） ...
2025-09-05SQL 日期截取：从基础方法到业务实战的全维度解析 在数据处理与业务分析中，日期数据是连接 “业务行为” 与 “时间维度” 的核 ...
2025-09-04在卷积神经网络（CNN）的发展历程中，解决 “梯度消失”“特征复用不足”“模型参数冗余” 一直是核心命题。2017 年提出的密集连 ...
2025-09-04CDA 数据分析师：驾驭数据范式，释放数据价值 在数字化转型浪潮席卷全球的当下，数据已成为企业核心生产要素。而 CDA（Certified ...
2025-09-04K-Means 聚类：无监督学习中数据分群的核心算法 在数据分析领域，当我们面对海量无标签数据（如用户行为记录、商品属性数据、图 ...
2025-09-03特征值、特征向量与主成分：数据降维背后的线性代数逻辑 在机器学习、数据分析与信号处理领域，“降维” 是破解高维数据复杂性的 ...
2025-09-03CDA 数据分析师与数据分析：解锁数据价值的关键 在数字经济高速发展的今天，数据已成为企业核心资产与社会发展的重要驱动力。无 ...
2025-09-03解析 loss.backward ()：深度学习中梯度汇总与同步的自动触发核心 在深度学习模型训练流程中，loss.backward()是连接 “前向计算 ...
2025-09-02要解答 “画 K-S 图时横轴是等距还是等频” 的问题，需先明确 K-S 图的核心用途（检验样本分布与理论分布的一致性），再结合横轴 ...
2025-09-02CDA 数据分析师：助力企业破解数据需求与数据分析需求难题 在数字化浪潮席卷全球的当下，数据已成为企业核心战略资产。无论是市 ...
2025-09-02Power BI 度量值实战：基于每月收入与税金占比计算累计税金分摊金额 在企业财务分析中，税金分摊是成本核算与利润统计的核心环节 ...
2025-09-01巧用 ALTER TABLE rent ADD INDEX：租房系统数据库性能优化实践 在租房管理系统中，rent表是核心业务表之一，通常存储租赁订单信 ...
2025-09-01CDA 数据分析师：企业数字化转型的核心引擎 —— 从能力落地到价值跃迁 当数字化转型从 “选择题” 变为企业生存的 “必答题”， ...
2025-09-01数据清洗工具全景指南：从入门到进阶的实操路径 在数据驱动决策的链条中，“数据清洗” 是决定后续分析与建模有效性的 “第一道 ...
2025-08-29机器学习中的参数优化：以预测结果为核心的闭环调优路径 在机器学习模型落地中，“参数” 是连接 “数据” 与 “预测结果” 的关 ...
2025-08-29
京公网安备 11010802034615号
经营许可证编号：京B2-20210330
