图论的小技巧和易错点-北京尧图网络

Part 0 题目在解题前需要先明确题目的图的模型边题目中的边代表什么给定的是点权还是边权如果是点权应该如何转为边权边是有向边还是无向边图图是简单图吗是否存在重边或自环存在重边或自环时应该如何处理或者它是一棵树规模题目是否给出了顶点数n nn和边数m mm还是需要手工计算n nn和m mmPart 1 建图Part 1.1 邻接表为什么要使用邻接表存图而不是其他方式存入的是代表是否两点连通的01还是边权Part 1.2 邻接矩阵作者不常用所以没有总结出太多的易错点和技巧……Part 1.3 链式前向星边是否无向如果是存边的数组大小是否达到了2 × N 2 \times N2×N边的编号是从0 00开始还是1 112 22开始注意边双连通分量的建图必须从2 22开始。Part 2 最短路FloydFloyd 算法一般使用「邻接矩阵」进行存图。Floyd 的最外层k为什么必须放在最外层解释Floyd 算法的主要思想是动态规划其状态转移方程为d i s i , j min ⁡ ( d i s i , j , d i s i , k d i s k , j ) dis_{i,j} \min(dis_{i,j},\; dis_{i,k} dis_{k,j})disi,jmin(disi,j,disi,kdisk,j)最短路场景或在传递闭包场景中的d i s i , j d i s i , k ∧ d i s k , j dis_{i,j} dis_{i,k} \land dis_{k,j}disi,jdisi,k∧disk,j算法必须保证在计算d i s i , j dis_{i,j}disi,j时所有以1 11到k − 1 k-1k−1为中间点的最短路径或传递关系都已计算。若将k kk放入内层循环可能在更新d i s i , j dis_{i,j}disi,j时所需的d i s i , k dis_{i,k}disi,k或d i s k , j dis_{k,j}disk,j未被正确计算或未计算导致结果错误。Floyd 算法可以计算每个节点恰好或至多经过k kk步可达的点集。恰好 k 步初始可达数组d i s disdis的k kk次方至多 k 步为每个节点i ii增加一条自环即d i s i , i 1 dis_{i,i} 1disi,i1再进行k kk次方。SPFA小心出题人卡 SPFASPFA 在某些特殊构造的数据下可能退化为O ( N × M ) O(N \times M)O(N×M)的时间复杂度。Dijkstra适用条件用于无负权边的图。使用前应明确求的是单源最短路还是多源最短路每个点的初值是否足够大源头节点的初值是0 00或是x xx边权的含义。版本朴素版本适用于稠密图。堆优化版本适用于大多数图。过程更新边权的时候可以直接更新吗还是像旅行巴士一样有一些限制。Part 3 其他其他内容敬请期待…

图论的小技巧和易错点

相关推荐

Python异常处理：从语法到可观察系统工程

零基础在VMware虚拟机安装Kali Linux：从下载到配置完整指南

IK 分词器 vs ES 内置分词器：中文搜索场景下的5项性能与效果对比

更多资讯

Folia歌曲不可用怎么办：版权与地域限制下的替代方案

Microduck RL轮滑训练：带被动轮的速度跟踪任务从0到1

SolidWorks 2020安装与稳定部署实战指南

OpenCloud 内置日志库 Logrus 1.10.2 变更日志深度解析：结构化日志的演进、性能优化与集成实践

postgres_lsp 规则详解：preferBigInt——用 BIGINT 规避整数溢出与迁移风险

Unity实时画面采集与RTMP推流实战：RenderTexture+FFmpeg方案详解

今日更新

AReaL 调试指南：从 Agent Workflow 验证到分布式训练死锁诊断

MATLAB实现GPS L1 C/A信号仿真与二维捕获验证

彻底搞懂ASCII、Unicode与UTF-8：从乱码根源到编码实战

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？