当前位置: 首页 > news >正文

图论初步 - L

一、图

1. 图的概念

图是一种数据结构,由节点和连接它们的构成。

数学上,一般使用 \(G = (V, E)\) 表示一个点集为 \(V\),边集为 \(E\) 的图。

与一个顶点 \(u\) 关联的边的个数叫做顶点 \(u\) 的的,用 \(d(u)\) 表示。

2. 图的分类

  • 按照点或边是否有限:

    有限图、无限图。

  • 按照边是否有方向:

    有向图(所有边都有方向);

    无向图(所有边都没有方向);

    混合图(一部分边有方向,另一部分没有)。

  • 按照边是否有权:

    有权图、无权图。

3. 简单图

  • 自环:对于边 \((u, v)\),若 \(u = v\),那么 \(e\) 叫做自环。
  • 重边:连接同一组顶点的边互为重边。
  • 如果一个图没有自环或重边,那么这个图叫做简单图。反之,这个图叫做多重图。

4. 图的连通性

5. 图的存储

在 C++ 语言中,一般使用下列方法来存储图。

1)邻接矩阵

2)邻接表

3)链式前向星

6. 图的遍历

图一般有两种遍历方式:DFS 与 BFS。

1)DFS

2)BFS

7. 特殊的路径

1)最短路

对于一条路径,若它是节点 \(u\) 到节点 \(v\) 所有路径中,权值和最小的那条,那么这条路径叫做节点 \(u\) 到节点 \(v\)最短路。反之,若权值和最大,那么它叫做最长路

最短路或最长路,可以使用多种算法求解。

A. 单源最短路
a. Dijkstra 算法
b. Bellman-Ford 算法
c. SPFA 算法
B. 多源最短路
a. Floyd 算法
b. Johnson 算法

2)环

对于一条路径,若起点与终点相同,且这组点对是唯一重复出现的点对,那么这条路径叫做一个

如果一个环所有边的权值为负,那么这个环叫做负环

可以使用 SPFA 算法寻找图中负环。

8. 生成树问题

二、例题

1. 图的遍历:P5318

2. 最长路:P1807

3. 单源最短路:P4779

4. 多源最短路:B3611

5. 最小生成树:P3366

6. 负环:P3385

7. 图上 DP:P1113

三、习题

http://www.hskmm.com/?act=detail&tid=32934

相关文章:

  • CSP-S2 历年真题 - L
  • 2025 集装箱吊机厂家推荐:乳山华江以智能技术+硬核质量破局,解决选机难题!
  • springboot结合阿里巴巴easyexcel,实现一键导出数据到Excel中
  • 深入解析:PX4 无人机地面调试全攻略:从机械到参数的系统优化
  • 2025年陶瓷过滤板厂家推荐排行榜,白刚玉陶瓷过滤板,棕刚玉陶瓷过滤板,扇形陶瓷板,真空陶瓷过滤板,陶瓷滤膜,陶瓷过滤机配件公司推荐
  • springboot结合阿里巴巴easyexcel,实现一键把Excel数据导入数据库
  • 2025年10月长白山度假酒店推荐:民俗与国际品质兼得
  • 2025年10月长白山度假酒店推荐:民俗与国际范兼得
  • 2025年10月访客系统推荐:五强榜单与选型要点
  • 2025年工业设备安装厂家权威推荐榜:管道/电气/暖通空调/空压系统/纯水系统/厂房通风/车间配电/机械设备专业安装服务全景解析
  • 实习内推】机器人操作系统Dora-rs团队招募实习生(北京)
  • 2025 上海财税服务机构优选榜:上海注册公司与代理记账领域靠谱服务商推荐
  • GoodSync 2025年10月17日
  • 书本p66实训题第2题
  • 2025全屋定制厂家推荐:聚焦异形空间+特色色系,森佰特木业领衔优质之选
  • springboot 上传图片到服务器之后,前段不能正确加载图片问题
  • springboot 设置文件上传大小
  • 【光照】UnityURP[屏幕空间环境光遮蔽SSAO]原理剖析实践
  • Ai元人文:讨论一种新的决策科学
  • 2025年流量计厂家权威推荐榜单:热式/模拟式/数字式/高压/高温/耐腐蚀/多气体/4-20mA/RS485/分体式/不锈钢高精度流量计公司精选
  • 深入解析:云原生时代的数据流高速公路:深入解剖Apache Pulsar的架构设计哲学
  • 251017
  • DeepResearch代码浅析
  • 2025年连铸机厂家权威推荐榜单:扇形段/大包回转台/钢包中间罐/结晶器总成/拉矫机/引锭杆/输送辊道/液压剪等核心部件专业供应商
  • 拉格朗日插值
  • 2025年10月中国专精特新申报服务机构推荐榜:五强实测
  • 2025年轧钢设备厂家权威推荐榜:冷轧机、热轧机源头生产厂家,技术实力与市场口碑深度解析
  • 正态总体中标准化单样本残差的分布推导
  • 10.16 CSP-S 模拟赛总结
  • 远程无钥匙进入(PKE)技术:便利与安全的完美融合