新闻详情

新闻详情

首页 / 资讯中心 / 详情

Tarjan算法

发布时间:2026/9/29 11:49:07来源:尧图网络
Tarjan算法
我们先来了解一下Tarjan算法的作用Tarjan算法解决的是在有向图里找连通分量的问题连通分量听起来很高大上对吧但是实际上他就是一堆点它们两两之间可以互相到达像这样1 - 2 - 3 - 4 ^ | | | |--------------| 这里1,2,3,4就是一个连通分量因为从任意一个点出发都能绕一圈到达另一个点没错Tarjan实现的问题就是这么简单可是我们能用瞪眼法看出来但是机器做不到我们该怎么用一个高效的算法解决这个问题呢Tarjan算法的核心思想Tarjan用一次DFS就可以找连通分量我们DFS的时候会有两个很重要的编号我们在这里提前埋个伏笔dfn[u],low[u]它们非常的重要dfn[u]表示点u是第几个被访问到的如果通俗一点就是dfs序还是举一个例子吧假如说这棵树是这样的那么它的dfs序就是dfn[1]1 dfn[2]2 dfn[3]3 dfn[4]4 dfn[5]5我们理解了dfn[]之后需要理解low[]它十分重要。low[u]表示从u出发沿着dfs序往下走最多再通过一条返祖边能够到达的最早的dfn概念返祖边就是从图里抠出来了一颗树这棵树上有一个节点可以直接通过一条边连接到它的祖先哎呀其实说人话就是low[u]记录u或u的后代、最早能绕回哪一个祖先我们可以从这一张图片来理解low[u]看到这张图大众第一次看可能会觉得low[4]1实则不是的low[4]2因为是“最多通过一条返祖边”那么说到这里我们就可以开始学习新算法了我就问一个问题假如说有一个点u使得dfn[u]low[u]我们能不能确定它是某一个连通分量这里思路跳了实在想不出就继续看吧我们还是回到这个例子1 - 2 - 3 - 4 ^ | | | |--------------|从1开始DFS1访问2 2访问3 3访问4 4又能访问1于是dfn[1]1 dfn[2]2 dfn[3]3 dfn[4]4;但是4能回到1所以low[4]1然后3的儿子4能回到12的儿子3能通过4回到1所以low[2]1 low[3]1low[1]自己肯定是等于1的这个没啥好说的最后我们发现dfn[1]low[1]这真是一个惊天的发现这说明了1是这一整个连通分量里最早被访问到的点也就是一整个连通分量的“根”呃你就这么理解吧于是Tarjan就把栈从栈顶一直弹到1的点拿出来他们就是一个连通分量1,2,3,4懵逼的同学们太懵逼了不是这从哪里又冒出来一个栈啊其实是这样的DFS的过程中有点已经访问过了但是我们不知道它们属于哪一个连通分量所以Tarjan用一个栈保存这些“还没分组“的点访问一个点的时候把它压栈st[top]u; ins[u]true;其中有一个ins[u]表示u现在是否还在栈里当确定某个点u是连通分量的”根“也就是dfn[u]low[u]就开始弹栈while(true){ int xst[top--]; ins[x]false; id[x]scc; if(xu) break; }从栈顶一直弹到u为止这些点就是一个连通分量Tarjan的DFS过程所以Tarjan的核心代码就是这样的voidTarjan(intu){dfn[u]low[u]tm;st[top]u;ins[u]true;for(intv:g[u]){if(!dfn[v]){Tarjan(v);low[u]min(low[u],low[v]);}elseif(ins[v]){low[u]min(low[u],dfn[v]);}}if(dfn[u]low[u]){scc;while(true){intxst[top--];ins[x]false;id[x]scc;if(xu)break;}}}典例演习我这里有两道例题板子题你们可以拿来练练手反正我后面会出博客讲解https://www.luogu.com.cn/problem/P3387纯模板https://www.luogu.com.cn/problem/P2746挺有意思的一道题
网站建设高端定制企业官网
RELATED

相关资讯

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

较早相关资讯

最新相关资讯

Agent提示词模板管理与编排实战:从变量校验到多Agent协作 2026/9/29 12:56:18

Agent提示词模板管理与编排实战:从变量校验到多Agent协作

1. 提示词模板管理到底在管什么1.1 从“手写提示词”到“模板化”的必然转变刚开始做 Agent 开发那会儿,我习惯把提示词直接写在代码里,一个三引号字符串搞定。项目小的时候没问题,改起来也快。但一旦 Agent 数量超过三五个,每个 …

阅读更多 →
本地部署DeepSeek+Ollama+知识库:从安装到排错全流程实战 2026/9/29 12:56:18

本地部署DeepSeek+Ollama+知识库:从安装到排错全流程实战

1. 为什么要在本地跑DeepSeek加知识库把大模型跑在自己电脑上,再挂一个私有知识库,这件事在两年前还是实验室里的玩法,现在已经变成很多开发者、运维、甚至非技术岗位的日常操作。核心驱动力其实就三条:数据不出本机、断网也能用、…

阅读更多 →
融彩机械实力怎么样 2026/9/29 12:56:04

融彩机械实力怎么样

行业洞察与使命确立 顺应产业升级浪潮,锚定增材制造发展方向全球制造业正经历深度转型,增材制造作为推动制造业数字化、智能化变革的核心领域之一,对生产装备的精度、自动化水平、稳定性提出了更高要求。近年来,3D打印技术在医疗、…

阅读更多 →
Linux 搭建 Samba 服务器实现跨平台文件共享 2026/9/29 12:56:04

Linux 搭建 Samba 服务器实现跨平台文件共享

前言NFS 好用,但Windows 访问 NFS 极其麻烦(要装客户端、要配身份映射、中文还容易乱码)。如果共享目录需要 Windows 同事直接双击打开,那就得上 Samba。Samba 是 SMB/CIFS 协议的开源实现,Windows 资源管…

阅读更多 →
TensorFlow工程化实战:从CUDA安装到TFX生产流水线 2026/9/29 12:55:51

TensorFlow工程化实战:从CUDA安装到TFX生产流水线

1. 这不是“又一个深度学习框架”——TensorFlow的本质是工程化AI生产流水线 很多人第一次听说TensorFlow,是在2015年谷歌开源它的时候。当时朋友圈刷屏的标题是:“谷歌放出大招!新框架吊打Theano!”——但十年过去,真…

阅读更多 →
数据预处理实战指南:从清洗到降维的完整流程 2026/9/29 12:55:51

数据预处理实战指南:从清洗到降维的完整流程

1. 数据预处理到底是什么,为什么它比建模更值得花时间1.1 从“垃圾进,垃圾出”说起做机器学习项目这几年,我最深的体会是:算法调参的时间,其实远不如处理数据的时间多。很多人拿到数据集的第一反应是赶紧训练模型跑个b…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

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

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