新闻详情

新闻详情

首页 / 资讯中心 / 详情

【数据结构】MRST_01

发布时间:2026/11/17 19:34:45来源:尧图网络
【数据结构】MRST_01
从根节点到叶子节点的最大距离叫树的半径给定一个无相连通图求半径最小的生成树结论最小半径生成树的半径 原图的半径即min⁡vmax⁡udG(v,u)vmin​umax​dG​(v,u)其中 dG(v,u)dG​(v,u) 是原图中 v,uv,u 之间的最短路距离。构造方法也很简单先求出原图所有点对之间的最短路。对每个顶点 vv计算它的离心率ecc(v)max⁡udG(v,u)ecc(v)umax​dG​(v,u)选一个离心率最小的点 cc它就是图的中心最小半径Recc(c)Recc(c)从 cc 出发做最短路径树例如无权图用 BFS带权图用 Dijkstra。记录每个非根节点的父节点这些边就构成一棵生成树。这棵生成树的半径就是 RR而且不可能有更小的半径。为什么这样最优任意生成树 TT 中两点的距离一定不小于原图中的最短距离所以r(T)≥min⁡vmax⁡udG(v,u)Rr(T)≥vmin​umax​dG​(v,u)R因此任何生成树半径都至少是 RR。选原图中心 cc最短路径树中从 cc 到每个点的距离等于原图最短距离因此r(T)max⁡udG(c,u)Rr(T)umax​dG​(c,u)R所以可以达到下界 RR。所以答案就是选图的中心做最短路径树。如果只需要半径值输出 RR 即可。对于图边为 1-22-31-33-4。最小半径 1中心节点 3半径最小的生成树最短路径树以 3 为根的边为1-32-33-4这棵树是星形根为 3到所有其他节点距离均为 1因此半径为 1。由于任何生成树至少有一条边半径不可能小于 1所以这是最优结果。图有 4 个点生成树有 44−21644−216 种去重后实际几种。这个图唯一的环是 1-2-3-1三角形生成树必须去掉三角形中的一条边并保留 3-4。去掉 1-2边为 1-3, 2-3, 3-4。半径 1中心是 3到1/2/4距离都是1。去掉 1-3边为 1-2, 2-3, 3-4。半径 1中心是 3到1/2/4距离都是1。去掉 2-3边为 1-2, 1-3, 3-4。半径 1中心是 3到2距离23-1-2到4距离1最大为2等等仔细算第三种去掉2-3保留1-2,1-3,3-4这棵树是一条链4-3-1-2。它的直径是 4 到 2距离 34-3-1-2。树的半径 直径/2 向上取整 ⌈3/2⌉2⌈3/2⌉2中心在边 3-1 中间。所以这棵树半径是2而前两棵半径是1。枚举后取最小确实是1。为什么可以不枚举因为我之前构造的以3为根的最短路径树就是第一或第二种半径1。而数学上保证了任何生成树的半径都不可能小于原图的半径你这个图原图半径就是1。既然你已经找到了半径1的生成树达到了物理极限那它必然是最优的其他枚举结果只会 ≥1≥1所以不用再算了。所以你的思路枚举取最小是绝对正确的定义我的方法是用来快速算出这个最小值的捷径二者结果一致。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/17 7:04:08

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/17 5:42:44

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/16 19:23:38

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/17 6:55:04

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/17 5:57:47

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/16 17:28:18

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉