1.图的遍历

按照某种规则沿着图中的边对图中的所有顶点访问一次且仅访问一次。
注：图是一种特殊的树。

1.广度优先遍历BFS

不难看出，图的广度优先就是参照的树的层次遍历算法。

2.深度优先遍历

从某个顶点开始V，访问这个顶点V相邻的任意一个顶点W，在访问W相邻的结点，如此直到没有结点可以访问，依次退回到最近访问的顶点，若它还有邻点未访问则从该点继续重复上述过程，直到图中所有点访问。

2.图的最小生成树

1.Prim算法

从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
注：
  1.每次加入新顶点后要连通
  2.加入新顶点后不可构成回路
在这里插入图片描述

2.Kruskal

每次选择一条权值最小的边，使这条边的两头连通(原本已经连通了不可选)直到所有顶点都连通

注：
  1.加入新边后不可形成回路。
在这里插入图片描述

3.图的最短路径

1.Dijkstra

final[ ] :标记各顶点是否已找到最短路径
dist[ ] ：最短路径长度
path[ ] :路径上的前驱
在这里插入图片描述

假设从V0出发，则基于V0的情况对三个数组进行初始化：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

根据dist与path数组，我们可以知道V0点到任意顶点的最短路径，即路径轨迹。
如：V0到V2：V0 -> V4 - > V1 -> V2 且为9

2.Floyd

基于动态规划思想。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3.BFS

先略。

# 算法 # 图论 # 数据结构
Logo
天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

avatar 天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

avatar 天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能

avatar 天工造物局