首页 > 编程语言 >Tarjan算法缩点

Tarjan算法缩点

时间:2024-09-26 09:35:52浏览次数:1  
标签:缩点 Tarjan 联通 拓扑 算法 节点 分量

Tarjan算法缩点

一.Tarjan算法缩点详解

在图论中,缩点是指将有向图中的强联通分量(SCCs)缩成单个节点,从而得到一个更简单的图结构,称为缩点图SCC图。Tarjan算法不仅可以用来寻找强联通分量,还可以用来进行缩点操作。

基本概念

  • 强联通分量:在一个有向图中,如果一组节点中任意两个节点都可以互相到达,那么这组节点就构成了一个强联通分量。
  • 缩点:将每个强联通分量视为一个单一的节点,并重新构建图结构。

算法步骤

  1. 使用Tarjan算法找到所有强联通分量

    • 初始化DFS序和low值。
    • 使用栈来记录当前路径上的节点。
    • 递归访问每个节点,并更新low值。
    • 当发现一个节点的DFS序等于其low值时,找到一个强联通分量。
  2. 构建缩点图

    • 为每个强联通分量创建一个新节点。
    • 遍历原图中的每条边,如果边的两个端点属于不同的强联通分量,则在缩点图中添加一条对应的新边。

二.Tarjan缩点后的点排列顺序是逆拓扑序的解释

在使用Tarjan算法进行缩点后,得到的缩点图(SCC图)中的节点排列顺序实际上是逆拓扑序。为了理解这一点,我们需要回顾Tarjan算法的工作原理以及拓扑排序的概念。

基本概念

  • 强联通分量(SCC):在一个有向图中,如果一组节点中任意两个节点都可以互相到达,那么这组节点就构成了一个强联通分量。
  • 缩点:将每个强联通分量视为一个单一的节点,并重新构建图结构。
  • 拓扑排序:在一个有向无环图(DAG)中,拓扑排序是对节点的一种线性排序,使得对于每一条有向边 (u, v),节点 u 在排序中都出现在节点 v 之前。
  • 逆拓扑序:与拓扑排序相反的顺序,即对于每一条有向边 (u, v),节点 v 在排序中都出现在节点 u 之前。

Tarjan算法与逆拓扑序的关系

Tarjan算法在寻找强联通分量的过程中,会使用深度优先搜索(DFS)来遍历图中的节点。在DFS的过程中,当一个节点的所有邻接节点都被访问完毕后,该节点才会被标记为一个强联通分量的结束点。因此,最后一个被标记的强联通分量实际上是缩点图中的一个源节点(即没有入边的节点)。

由于Tarjan算法是深度优先的,最后一个被标记的强联通分量在缩点图中没有入边,这意味着它在拓扑排序中应该是第一个节点。因此,Tarjan算法标记强联通分量的顺序实际上是逆拓扑序。

解释

  1. DFS遍历顺序

    • Tarjan算法从任意一个未访问的节点开始进行DFS。
    • 当访问到一个节点 u 时,算法会递归访问 u 的所有邻接节点 v。
    • 当所有邻接节点都被访问完毕后,节点 u 才会被标记为一个强联通分量的结束点。
  2. 强联通分量的标记顺序

    • 由于DFS的性质,最后一个被标记的强联通分量在缩点图中没有入边。
    • 这意味着最后一个被标记的强联通分量在拓扑排序中应该是第一个节点。
  3. 逆拓扑序

    • 因此,Tarjan算法标记强联通分量的顺序实际上是逆拓扑序。

三.最短路径问题与拓扑排序和动态规划的结合

最短路径问题是图论中的一个经典问题,通常使用Dijkstra算法、Bellman-Ford算法或Floyd-Warshall算法来解决。然而,在某些特定情况下,特别是对于有向无环图(DAG),我们可以结合拓扑排序和动态规划来高效地求解最短路径问题。

基本概念

  • 最短路径问题:在加权图中找到从一个源节点到目标节点的最短路径。
  • 拓扑排序:在一个有向无环图(DAG)中,拓扑排序是对节点的一种线性排序,使得对于每一条有向边 (u, v),节点 u 在排序中都出现在节点 v 之前。
  • 动态规划:一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划通常用于优化问题,如最短路径、最长递增子序列等。

结合应用场景

在有向无环图中,由于没有环的存在,我们可以利用拓扑排序来确定节点的处理顺序,然后使用动态规划来计算最短路径。

示例:DAG中的最短路径

考虑一个有向无环图(DAG),我们需要找到从源节点到目标节点的最短路径。这个问题可以通过结合拓扑排序和动态规划来解决。

  1. 拓扑排序

    • 首先对图进行拓扑排序,得到节点的线性顺序。
    • 拓扑排序确保了在处理每个节点时,其所有前驱节点都已经被处理过。
  2. 动态规划

    • 使用动态规划数组 dp[v] 表示从源节点到节点 v 的最短路径长度。
    • 按照拓扑排序的顺序处理每个节点 v,并更新其所有后继节点 wdp 值:
      dp[w] = min(dp[w], dp[v] + weight(v, w))
      
    • 最终,dp[target] 就是从源节点到目标节点的最短路径长度。

伪代码

function shortest_path(graph, source, target):
    // 进行拓扑排序
    sorted_nodes = topological_sort(graph)
    
    // 初始化动态规划数组
    dp = array of size V initialized to infinity
    dp[source] = 0
    
    // 按照拓扑排序的顺序处理每个节点
    for each v in sorted_nodes:
        for each (v, w) in graph.edges:
            if dp[v] != infinity:
                dp[w] = min(dp[w], dp[v] + weight(v, w))
    
    return dp[target]

结论

通过上述分析,我们可以得出结论:Tarjan算法缩点后的点排列顺序是逆拓扑序。这是因为Tarjan算法在DFS遍历过程中,最后一个被标记的强联通分量在缩点图中没有入边,从而在拓扑排序中应该是第一个节点。

题目描述

题目:缩点

给定一个 \(n\) 个点 \(m\) 条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。

输入格式

第一行两个正整数 \(n,m\)

第二行 \(n\) 个整数,其中第 \(i\) 个数 \(a_i\) 表示点 \(i\) 的点权。

第三至 \(m+2\) 行,每行两个整数 \(u,v\),表示一条 \(u\rightarrow v\) 的有向边。

输出格式

共一行,最大的点权之和。

样例 #1

样例输入 #1

2 2
1 1
1 2
2 1

样例输出 #1

2

提示

对于 \(100\%\) 的数据,\(1\le n \le 10^4\),\(1\le m \le 10^5\),\(0\le a_i\le 10^3\)。

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100010; // 定义常量N,表示图中节点的最大数量

vector<int> g[N]; // 邻接表存储图
int dfn[N], low[N], ins[N], idx; // Tarjan算法所需变量
int bel[N], cnt; // bel[u]表示节点u属于哪个强联通分量,cnt表示强联通分量的数量
int sz[N]; // sz[i]表示第i个强联通分量中所有节点的权值之和
int n, m; // n表示节点数,m表示边数
int a[N]; // 每个节点的权值
stack<int> stk; // 栈,用于Tarjan算法
vector<int> ans[N]; // 存储每个强联通分量中的节点
int dp[N]; // dp[i]表示以第i个强联通分量为起点的最长路径的权值和
int way[N]; // way[i]表示以第i个强联通分量为起点的最长路径的数量
int vis[N]; // vis[i]表示第i个强联通分量是否已经被访问过
int res = 0, w = 0; // res表示最长路径的权值和,w表示最长路径的数量

// Tarjan算法求强联通分量
void tarjan(int u) {
    dfn[u] = low[u] = idx++; // 初始化dfn和low
    ins[u] = true; // 标记节点u在栈中
    stk.push(u); // 将节点u入栈
    for (auto v : g[u]) { // 遍历节点u的所有邻接节点
        if (!dfn[v]) tarjan(v); // 如果节点v未访问过,递归访问
        if (ins[v]) low[u] = min(low[u], low[v]); // 更新low值
    }
    if (dfn[u] == low[u]) { // 如果dfn[u]等于low[u],说明找到了一个强联通分量
        cnt++; // 强联通分量数量加1
        while (true) {
            int t = stk.top(); // 取出栈顶节点
            stk.pop(); // 弹出栈顶节点
            sz[cnt] += a[t]; // 累加强联通分量的权值和
            bel[t] = cnt; // 标记节点t属于当前强联通分量
            ans[cnt].push_back(t); // 将节点t加入当前强联通分量
            ins[t] = false; // 标记节点t不在栈中
            if (t == u) break; // 如果栈顶节点是u,结束循环
        }
    }
}

signed main() {
    cin >> n >> m; // 输入节点数和边数
    for (int i = 1; i <= n; i++) cin >> a[i]; // 输入每个节点的权值
    for (int i = 1; i <= m; i++) { // 输入每条边
        int u, v;
        cin >> u >> v;
        g[u].push_back(v); // 添加边到邻接表
    }
    for (int i = 1; i <= n; i++) { // 对每个未访问的节点进行Tarjan算法
        if (!dfn[i]) tarjan(i);
    }
    int tt = 0; // 用于标记访问次数
    for (int i = 1; i <= cnt; i++) { // 对每个强联通分量进行处理
        way[i] = 1; // 初始化路径数量为1
        dp[i] = 0; // 初始化路径权值和为0
        tt++; // 访问次数加1
        for (auto u : ans[i]) { // 遍历当前强联通分量中的所有节点
            for (auto v : g[u]) { // 遍历节点u的所有邻接节点
                if (bel[u] != bel[v] && vis[bel[v]] < tt) { // 如果邻接节点v不在当前强联通分量且未被访问过
                    vis[bel[v]]++; // 标记邻接节点v所在的强联通分量已被访问
                    if (dp[i] < dp[bel[v]]) dp[i] = dp[bel[v]], way[i] = 0; // 更新最长路径权值和和路径数量
                    if (dp[i] == dp[bel[v]]) way[i] = (way[i] + way[bel[v]]); // 累加路径数量
                }
            }
        }
        dp[i] += sz[i]; // 加上当前强联通分量的权值和
        if (dp[i] > res) res = dp[i], w = 0; // 更新最长路径权值和和路径数量
        if (dp[i] == res) w = (w + way[i]); // 累加路径数量
    }
    cout << res << endl; // 输出最长路径的权值和
}

标签:缩点,Tarjan,联通,拓扑,算法,节点,分量
From: https://www.cnblogs.com/Violetfan/p/18432784

相关文章

  • 算法-复杂度分析
    复杂度分析不依赖具体的执行环境不用具体的测试数据在算法实现前,我们在脑海就可以评估算法的性能评估一个算法的性能:本质上就是评估这个算法代码执行的时间N为数据规模 大O复杂度表示法表示算法的性能,通常看最差的情况,算法运行的上界O(n) T=5n+2常数不重要,复杂......
  • 【算法】C++KMP算法的简洁实现
    目录简介next数组匹配完整代码简介对于朴素的字符串匹配算法,如果想在主串中寻找到第一次出现子串的位置,需要依次枚举主串中的每一个位置作为起始位置进行匹配尝试,如果主串中存在许多与子串相似结构的部分,那么朴素算法会进行大量的无用枚举,时间复杂度非常之高。KMP算法......
  • 【算法题】63. 不同路径 II-力扣(LeetCode)-”如果起点有障碍物,那么便到不了终点“
    【算法题】63.不同路径II-力扣(LeetCode)-”如果起点有障碍物,那么便到不了终点“1.题目下方是力扣官方题目的地址63.不同路径II一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格......
  • 【算法】笔试题记录
    哇今天做了道特别有意思的题。编程就给了两道,第一题特别简单,a、b两个数,每次选其中一个数*2,这样操作两次,问最后得到的两数之和的期望值是多少。简单吧?因为每次选择都有两种可能性,操作两次后就会有四种可能的结果(22)。其中有两个结果是重复的(2a,2b),剩下两个分别是(a,4b)和(4a,......
  • 【鸟类识别系统】+计算机毕设项目+卷积神经网络算法+人工智能+深度学习+模型训练+Pyth
    一、介绍鸟类识别系统。本系统采用Python作为主要开发语言,通过使用加利福利亚大学开源的200种鸟类图像作为数据集。使用TensorFlow搭建ResNet50卷积神经网络算法模型,然后进行模型的迭代训练,得到一个识别精度较高的模型,然后在保存为本地的H5格式文件。在使用Django开发Web网页端操作......
  • 【动物识别系统】计算机毕设项目案例+Python卷积神经网络算法+模型训练+人工智能+深度
    一、介绍动物识别系统。本项目以Python作为主要编程语言,并基于TensorFlow搭建ResNet50卷积神经网络算法模型,通过收集4种常见的动物图像数据集(猫、狗、鸡、马)然后进行模型训练,得到一个识别精度较高的模型文件,然后保存为本地格式的H5格式文件。再基于Django开发Web网页端操作界面,实现......
  • 求最大公约数的三种算法
    #include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intgcdByBruteForce(inta,intb){for(inti=min(a,b);i>0;--i){if(a%i==0&&b%i==0){returni;......
  • 矿山井下/传送带堆料检测AI算法的检测作用、工作原理及其解决方案
    传送带堆料分为两种情况,一种是传送带的井下堆料检测AI算法,一种是传送带上面的堆料检测AI算法,传送带井下堆料检测AI算法是在带式输送机的漏煤下方井下安装摄像仪,通过视频分析检测井下堆煤情况,当洒煤堆积到一定程度后,智慧矿山版ai盒子自动产生报警,并语音通知值班人员,也可通过前端音箱......
  • 代码中的大数定律:蒙特卡洛算法逼近圆周率π
    摘要:当程序员遇上π,蒙特卡洛算法成了他们的魔法棒。本文用一段C语言代码,将随机点的雨滴洒向数字的海洋,用概率的网捕捉π的踪迹。这不仅是一场算法的探险,更是对编程魔法的一次奇妙展示。认识蒙特卡洛算法蒙特卡洛算法是一类基于概率的算法的统称,不是特指某一种算法。它也被称为统计......
  • 10.解析解方法推导线性回归——不容小觑的线性回归算法
    引言线性回归是许多复杂机器学习模型的基础。作为一种基本的机器学习方法,线性回归提供了清晰的思路和工具,通过理解其推导过程,可以更好地掌握机器学习的基本原理和模型设计。通过阅读本篇博客,你可以:1.学会如何用解析解的方法推导线性回归的最优解2.了解如何判定损失函数是凸......