IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> Tarjan算法附图详解(SCC) -> 正文阅读

[数据结构与算法]Tarjan算法附图详解(SCC)

Tarjan算法用于有向图,用于找强连通区域,割边等,属于图论内容。

它的思路类似于DFS + Union Find,
下面来详细介绍:

图和详细视频参考链接

首先任意选一点作为起点做DFS,DFS的过程中要给各node标上id
在这里插入图片描述
然后每个node有一个low link value,
简单解释这是表示当前node能到达的node中最小的id(包括它自己的id)
比如node1,它能到达的node中最小id是0
node2 和 3能到达的最小id是2,同理4,5
在这里插入图片描述
好了,现在概念清楚了,
我们可以看到有相同low link value的node在一个强连通区域。

下面要解决的问题是怎么样在DFS的过程中更新low link value。

首先我们认识到当node的id和它的low link value相同时,说明又回到了起点,进入了SCC(强连通区域),
比如node 0, 2, 4

DFS需要一个stack装入现在正在访问的node,
还要一个visited数组记录node是否已经被访问过,防止重复遍历。

从任意的0点出发,DFS
像下图这样,正在访问的0,1,2压入stack,
然后出现了在0处,它的id和low link value相同,说明进入了SCC,开始回溯,
回溯的时候更新stack.top点的low link value, 就是node 2,
2和0是相通的,都在stack里,所以2的low link value和 node 0 应该相同,更新lowlink[2],
把当前SCC的node全部从stack中取出,更新low link value
在这里插入图片描述
然后任选另一起点继续上面的过程,
然后到node 5的时候,又到了0,但是现在0不在stack里面,所以不更新low link value。
在这里插入图片描述
同理经过node 6到了node 2, node 2不在stack里面,所以也不更新low link value
然后到node 4, node 4的id和low link value相等,所以开始回溯。
在这里插入图片描述
得到第2个SCC
在这里插入图片描述
虽然node 3的id和low link value相同,但是还不能判断SCC,因为node还没访问完呢,

最后找到了所有的SCC
在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-21 19:13:41  更:2022-05-21 19:15:14 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/30 1:00:53-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码