
图论是什么?关于图的理论?下面跟小编具体来了解一下图论以及简单的图论算法吧。
一、图论起源
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
尊敬的考生: 您好! 我们诚挚通知您,CDA Level I和 Level II考试大纲将于 2025年7月25日 实施重大更新。 此次更新旨在确保认证 ...
2025-07-09CDA 数据分析师考试:从报考到取证的全攻略 在数字经济蓬勃发展的今天,数据分析师已成为各行业争抢的核心人才,而 CDA(Certi ...
2025-07-09【CDA干货】单样本趋势性检验:捕捉数据背后的时间轨迹 在数据分析的版图中,单样本趋势性检验如同一位耐心的侦探,专注于从单 ...
2025-07-09year_month数据类型:时间维度的精准切片 在数据的世界里,时间是最不可或缺的维度之一,而year_month数据类型就像一把精准 ...
2025-07-09CDA 备考干货:Python 在数据分析中的核心应用与实战技巧 在 CDA 数据分析师认证考试中,Python 作为数据处理与分析的核心 ...
2025-07-08SPSS 中的 Mann-Kendall 检验:数据趋势与突变分析的有力工具 在数据分析的广袤领域中,准确捕捉数据的趋势变化以及识别 ...
2025-07-08备战 CDA 数据分析师考试:需要多久?如何规划? CDA(Certified Data Analyst)数据分析师认证作为国内权威的数据分析能力认证 ...
2025-07-08LSTM 输出不确定的成因、影响与应对策略 长短期记忆网络(LSTM)作为循环神经网络(RNN)的一种变体,凭借独特的门控机制,在 ...
2025-07-07统计学方法在市场调研数据中的深度应用 市场调研是企业洞察市场动态、了解消费者需求的重要途径,而统计学方法则是市场调研数 ...
2025-07-07CDA数据分析师证书考试全攻略 在数字化浪潮席卷全球的当下,数据已成为企业决策、行业发展的核心驱动力,数据分析师也因此成为 ...
2025-07-07剖析 CDA 数据分析师考试题型:解锁高效备考与答题策略 CDA(Certified Data Analyst)数据分析师考试作为衡量数据专业能力的 ...
2025-07-04SQL Server 字符串截取转日期:解锁数据处理的关键技能 在数据处理与分析工作中,数据格式的规范性是保证后续分析准确性的基础 ...
2025-07-04CDA 数据分析师视角:从数据迷雾中探寻商业真相 在数字化浪潮席卷全球的今天,数据已成为企业决策的核心驱动力,CDA(Certifie ...
2025-07-04CDA 数据分析师:开启数据职业发展新征程 在数据成为核心生产要素的今天,数据分析师的职业价值愈发凸显。CDA(Certified D ...
2025-07-03从招聘要求看数据分析师的能力素养与职业发展 在数字化浪潮席卷全球的当下,数据已成为企业的核心资产,数据分析师岗位也随 ...
2025-07-03Power BI 中如何控制过滤器选择项目数并在超限时报错 引言 在使用 Power BI 进行数据可视化和分析的过程中,对过滤器的有 ...
2025-07-03把握 CDA 考试时间,开启数据分析职业之路 在数字化转型的时代浪潮下,数据已成为企业决策的核心驱动力。CDA(Certified Da ...
2025-07-02CDA 证书:银行招聘中的 “黄金通行证” 在金融科技飞速发展的当下,银行正加速向数字化、智能化转型,海量数据成为银行精准 ...
2025-07-02探索最优回归方程:数据背后的精准预测密码 在数据分析和统计学的广阔领域中,回归分析是揭示变量之间关系的重要工具,而回 ...
2025-07-02CDA 数据分析师报考条件全解析:开启数据洞察之旅 在当今数字化浪潮席卷全球的时代,数据已成为企业乃至整个社会发展的核心驱 ...
2025-07-01