首页 > 编程语言 >Tarjan算法求割点

Tarjan算法求割点

时间:2022-12-19 17:22:55浏览次数:56  
标签:Tarjan cur 求割点 DFS order 算法 dfn low 节点

定义

如果在一个图中,删除某个节点连同与之关联的边,会导致整个图的连通分支数增加,那么这个节点叫做 割点(Articulation Point, Cut Vertex)

如下图:

img

整个图的连通分支数为1,但是删除节点3后,整个图就“分裂”成了2个连通分支:

img

因此,节点3是整个图的割点。

方法

一个很容易想到的方法是,依次删除图中的每一个节点,看剩下部分的连通分支数增没增加。但是那样显然太浪费时间了!有没有一种办法,能够快速的找出整个图的割点呢?

Tarjan算法的核心思想:深度优先遍历(DFS)这张图,得到的DFS树(由遍历路径和节点构成的树)中,当某个节点u满足以下条件之一时,它就是割点:

  1. u为DFS树的树根,且u有2棵及以上的子树,如图(三角形代表子树):
    img
  2. u不为DFS树的树根,且对于u在DFS树中的任意一个后代v,都必须先经过u才能通往u的祖先,如图(蓝绿色箭头代表DFS路径):
    img

注意第一点并不等价于u有2个及以上的邻居,因为这些邻居有可能处于同一个DFS树,比如下面这张图,u有2个邻居,但却只有一个子树,因此u不是整个图的割点。
img

第二点也不难理解,如果v必须先经过u才能到达u的祖先的话,那么去掉u就无路可走了,连通分支数会增加,u就是割点。

DFS

我们可以维护两个数组:dfnlow,其中:

  • dfn[u]代表u被遍历到的次序(时间戳)。如果节点u先于节点v被访问,那么dfn[u] < dfn[v]。规定根节点的dfn为1。
  • low[u]代表从u的后代出发,在不经过父节点的情况下能够“另辟蹊径”回溯到的最先遍历到的祖先的dfn。(每一步都不能走到当前走到的节点的父节点,且走到某个祖先就马上记录low

设u、v分别为DFS树中的两个节点,且v是u的后代,那么如果low[v] >= dfn[u],那么从v不经过父节点是走不到u的祖先的,则u就是割点,如图所示。(蓝绿色箭头表示DFS路径,黄绿色箭头表示回溯路径)

img

举个栗子吧。以下面这张图为例:

img

从节点0开始DFS。因为节点0是最开始遍历的节点,因此它的dfnlow均为1。

img

节点0有两个子节点,不妨先从1开始。因为我们还没有走到3和2,所以我们将1的low暂定为2。

img

继续走下去:

img

节点3有3个子节点,先从节点4开始DFS。中间过程省略,直接一步到位走到5:

img

回溯到4,因为5是4和6的后代,按照low的定义,同样的可以将low更新为3。

img

继续回溯到3,由于4和5都已经访问过了,还剩2没访问,先走到2。

img

从2可以不经过父节点直接走到0,更新2的low为1;回溯的时候也将相应节点的low更新为1。

img

由此可以得到一个所有节点的dfnlow的表格(按dfn由小到大排序):

节点 dfn low
0 1 1
1 2 1
3 3 1
4 4 3
6 5 3
5 6 3
2 7 1

对于节点3来说,因为它的所有后代4、6、5的low均等于3的dfn,所以从这些节点出发不经过父节点是不能走到3的祖先的,因此3是整幅图的割点。

代码实现

首先给出两个类型别名:node_torder_t,用以使语义更加明确:

using node_t = unsigned long long;
using order_t = unsigned long long;

因为这里主要利用两个顶点之间的邻接关系,这里图使用邻接表来表示:

class Graph {
    unsigned long long n;
    vector<vector<node_t>> adj;

protected:
    void dfs(node_t cur, vector<order_t> &dfn, vector<order_t> &low, order_t &order, unordered_set<node_t> &aps);

public:
    Graph(initializer_list<initializer_list<node_t>> list) : n(list.size()), adj({}) {
        for (auto &l : list) {
            adj.emplace_back(l);
        }
    }

    unordered_set<node_t> findAP();
};

“寻找割点”的代码整体框架:

unordered_set<node_t> Graph::findAP() {
    vector<order_t> dfn(n, 0);
    vector<order_t> low(n, 0);
    order_t order = 0;
    unordered_set<node_t> aps;
    node_t root = 0;
    dfs(root, dfn, low, order, aps);
    return aps;
}

DFS的大体框架:

void Graph::dfs(node_t cur, vector<order_t> &dfn, vector<order_t> &low, order_t &order, unordered_set<node_t> &aps) {
    size_t children = 0;
    dfn[cur] = low[cur] = ++order;
    for (node_t neighbor: adj[cur]) {
        if (dfn[neighbor] == 0) {
            children++;
            dfs(neighbor, dfn, low, order, aps);
            // ...
        } else {
            // ...
        }
    }
}

问题来了,low怎么计算。

假设当前遍历到的节点u的某一个邻居为v:

  1. 若v为u的子节点,则low[u]更新为low[u]low[v]取最小值。
  2. 若v不为u的子节点,也不是u的父节点,则说明从u出发可以不经过父节点直接到达v,此时low[u]更新为low[u]dfn[v]的最小值。

代码实现如下:

if (dfn[neighbor] == 0) {
    // ...
    low[cur] = min(low[cur], low[neighbor]);
    // ...
} else {
    low[cur] = min(low[cur], dfn[neighbor]);
}

割点的判定,上文已有提及,直接上代码:

if (dfn[cur] == 1 && children > 1 || dfn[cur] > 1 && low[neighbor] >= dfn[cur]) {
    aps.insert(cur);
}

完整代码:

void Graph::dfs(node_t cur, vector<order_t> &dfn, vector<order_t> &low, order_t &order, unordered_set<node_t> &aps) {
    size_t children = 0;
    dfn[cur] = low[cur] = ++order;
    for (node_t neighbor: adj[cur]) {
        if (dfn[neighbor] == 0) {
            children++;
            dfs(neighbor, dfn, low, order, aps);
            low[cur] = min(low[cur], low[neighbor]);
            if (dfn[cur] == 1 && children > 1 || dfn[cur] > 1 && low[neighbor] >= dfn[cur]) {
                aps.insert(cur);
            }
        } else {
            low[cur] = min(low[cur], dfn[neighbor]);
        }
    }
}

测试:

int main() {
    Graph graph{{1, 2},
                {0, 3},
                {0, 3},
                {1, 2, 4, 5},
                {3, 6},
                {3, 6},
                {4, 5}};
    auto aps = graph.findAP();
    cout << "The articulation points are:" << endl;
    for (node_t ap: aps) {
        cout << ap << ' ';
    }
    cout << endl;
    return 0;
}

输出:

The articulation points are:
3

复杂度分析

  • 时间复杂度:\(O(n+e)\),其中 \(n\) 代表节点数,\(e\) 代表边数,DFS的时间复杂度为\(O(n+e)\)。
  • 空间复杂度:\(O(n+e)\),其中 \(n\) 代表节点数,\(e\) 代表边数,邻接表的空间复杂度为 \(O(n+e)\),维护的数组的空间复杂度为 \(O(n)\),加起来为 \(O(n+e)\)。

标签:Tarjan,cur,求割点,DFS,order,算法,dfn,low,节点
From: https://www.cnblogs.com/YWT-Real/p/16992625.html

相关文章

  • 基础算法汇总之二叉搜索树实现
    一.树定义在计算机科学中,树(英语:tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层......
  • 基础算法汇总之AVL树实现
    一.什么是AVL树?在说AVL树之前,先回顾一下我们之前研究过的二分查找树(二分搜索树),在极端的情况下,二分搜索树会从一棵二叉树变为链表(按顺序插入数据)这样的查询效率会大打折扣。......
  • 基础算法汇总之哈希表
    一.什么是哈希表哈希表也叫做散列表,是一种可以根据关键key值直接访问的数据结构;简单说就是把关键的key值映射到数组中一个位置来访问记录,这样可以加快反应速度。这里面计算......
  • 基础算法汇总之堆和优先队列
    一.简述这篇文章将介绍几种常见的队列,本文将重点介绍优先队列以及优先队列底层的二叉堆并且实现基础算法(go实现),最后还会介绍一样Java并发包中的四种最常用的队列,分析其源码......
  • TapTap 算法平台的 Serverless 探索之路
    作者:陈欣昊Serverless在构建应用上为TapTap节省了大量的运维与开发人力,在基本没投入基建人力的情况下,直接把我们非常原始的基建,或者说是资源管理水平拉到了业界相对前......
  • 【算法实践】有始有终,雨露均沾--手把手带你手撸选择排序
    前言选择排序是一个非常经典且简单直观的排序算法,无论什么数据进去都是O(n^2)的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间......
  • C++数学与算法系列之排列和组合
    1.前言本文将聊聊排列和组合,排列组合是组合学最基本的概念,在程序运用中也至关重要。排列问题:指从给定个数的元素中取出指定个数的元素进行排序。组合问题:指从给定个......
  • 老生常谈React的diff算法原理-面试版
    第一次发文章notonly(虽然)版式可能有点烂butalso(但是)最后赋有手稿研究finally看完他你有收获diff算法:对于update的组件,他会将当前组件与该组件在上次更新是对应的......
  • 数据结构与算法学习笔记
    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏 。有不懂的地方指出来,我做修改。数据结构与算法思维导图数据结构指的是“一组数据的存储结构”......
  • 强化学习的基础知识和6种基本算法解释
    强化学习的基础知识和概念简介(无模型、在线学习、离线强化学习等)机器学习(ML)分为三个分支:监督学习、无监督学习和强化学习。监督学习(SL):关注在给定标记训练数据的情......