算法随笔:图论问题之割点割边

这篇具有很好参考价值的文章主要介绍了算法随笔:图论问题之割点割边。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

割点

定义

割点的定义:如果一个点被删除之后会导致整个图不再是一个连通图,那么这个顶点就是这个图的割点。举例:

算法随笔:图论问题之割点割边,# 算法随笔,算法,数据结构

 上图中的点2就是一个割点,如果它被删除,则整个图被分为两个连通分量,不再是一个连通图。

求割点的方法

最直观容易想到的一种简单朴素的方法:

依次删除每一个顶点,然后用dfs或者bfs来检查图是否依然连通。如果删除某个顶点后,导致图不再连通,那么刚才删除的顶点就是割点。

这种方法的时间复杂度是O(N(N+M))。显然不是一个高性能的算法。

考虑更高性能的算法:

考虑从根节点开始进行DFS遍历,遍历的同时记录每个节点的遍历顺序(又称为时间戳)到数组num。如下图:

算法随笔:图论问题之割点割边,# 算法随笔,算法,数据结构

算法随笔:图论问题之割点割边,# 算法随笔,算法,数据结构

圆圈中数字是顶点编号, 圆圈右上角的数表示这个顶点的“时间戳” 。

那么在遍历过程中如何判断割点?见下表:

节点类型 判断方法 解释
根节点

对于根节点,有两棵及以上不相连的子树,则根节点是割点

很显然如果根节点有两棵及以上的不相连的子树,那么根节点被删除之后整个图将会不再是一个连通图,会被划分为多个连通块。
非根节点 对于非根节点,u的直接子v或者v的后代没有回退到u的祖先的边(没有不经过u直接回到u的祖先的路径),则u不是割点,否则是。 如果非根节点u的子节点v及v的后代节点有路径可以不经过点u回退到u的祖先,那么这个点即使被删除,整个图依然是连通的。

那么该算法具体如何实现呢?

定义一个数组low来记录每个顶点在不经过父顶点时,能够回到的最小“时间戳”。(low[v]记录v和v的后代能够连回到的最小的num)。

对于某个顶点u,如果low[v]>=num[u],即v和v的后代没有边退回到祖先,顶多退回到顶点u,那么u点为割点。

示例代码(POJ1144)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e2 + 10;
const int INF = 0x3fffffff;
const int mod = 1000000007;
int num[maxn];      // 记录每个点的dfs遍历顺序
int low[maxn];      // low[v]记录v和v的后代能连回到的祖先的num
int dfn;            // 记录进入递归的顺序(也称为时间戳)
bool isCut[maxn];   // 标记割点
vector<int> G[maxn];

void dfs(int u, int fa) {       // 当前节点u,u的父节点fa
    low[u] = num[u] = ++dfn;    // 记录该点的遍历顺序,该点的low值初始等于num
    int child = 0;              // 子树数目
    for (int i = 0; i < G[u].size(); i++) {     // 处理u的所有子节点
        int v = G[u][i];
        if (!num[v]) {  // v没访问过
            child++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);       // 用后代的返回值更新low值,从v以及v的后代可以回退到的祖先的num值
            if (low[v] >= num[u] && u != 1) {   // 对于非根节点,u的直接子v或者v的后代没有回退到u的祖先的边,则u是割点
                isCut[u] = true;
            }
        } else if (num[v] < num[u] && v != fa) {    // 处理回退边
            low[u] = min(low[u], num[v]);
        }
    }
    if (u == 1 && child >= 2) {     // 对于根节点,有两棵以上不相连的子树,则根节点是割点
        isCut[1] = true;
    }
}

void solve() {
    int n, ans;
    while (cin >> n, n) {
        if (n == 0)
            break;
        memset(low, 0, sizeof low);
        memset(num, 0, sizeof num);
        dfn = 0;
        for (int i = 1; i <= n; i++) {
            G[i].clear();
        }
        int a, b;
        while (cin >> a, a) {
            while (cin.get() != '\n') {
                cin >> b;
                G[a].push_back(b);
                G[b].push_back(a);
            }
        }
        memset(isCut, 0, sizeof isCut);
        ans = 0;
        dfs(1, 1);
        for (int i = 1; i <= n; i++) {
            ans += isCut[i];
        }
        cout << ans << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    solve();
    return 0;
}

割边

定义

如果在一个无向图中删除某条边后,图不再连通,那么这条边叫做割边(又称桥)。举例:

算法随笔:图论问题之割点割边,# 算法随笔,算法,数据结构

算法随笔:图论问题之割点割边,# 算法随笔,算法,数据结构

求割边的方法

只需将求割点的算法修改一个符号就可以。 只需将low[v]>=num[u]改为low[v]>num[u]。

这是为什么呢?

low[v]和num[u]相等则表示还可以回到父亲结点; 而low[v]>num[u]则表示连父亲都回不到了。倘若顶点v不能回到祖先,也没有另外的路能回到父亲,那么 u-v 这条边就是割边。

割边代码

……后边补上……

注:本文的部分内容和图片参考了 https://www.cnblogs.com/ljy-endl/p/11595161.html文章来源地址https://www.toymoban.com/news/detail-648891.html

到了这里,关于算法随笔:图论问题之割点割边的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】图论及其相关算法

    线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了图。 图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图:

    2024年02月09日
    浏览(40)
  • 数据结构的应用场景:如社交网络、路由算法、图论、网络协议等

    作者:禅与计算机程序设计艺术 数据结构(Data Structure)是计算机科学中存储、组织、管理数据的方式,主要用于解决信息检索、处理和运算时的效率及空间占用问题。它是指数据元素(elements)之间的关系、顺序和逻辑结构,以及相互作用的算法。数据结构通常采用抽象数据类

    2024年02月14日
    浏览(47)
  • 数据结构第12周 :( 有向无环图的拓扑排序 + 拓扑排序和关键路径 + 确定比赛名次 + 割点 )

    【问题描述】 由某个集合上的一个偏序得到该集合上的一个全序,这个操作被称为拓扑排序。偏序和全序的定义分别如下:若集合X上的关系R是自反的、反对称的和传递的,则称R是集合X上的偏序关系。设R是集合X上的偏序,如果对每个x,y∈X必有xRy或yRx,则称R是集合X上的全序

    2024年02月08日
    浏览(41)
  • 【算法/图论】2-SAT问题详解

    在了解2-SAT的定义之前,我们需要给出一些基础定义。 布尔变量 (Boolean variable):只能取 1 1 1 (true)或 0 0 0 (false)的变量。 否定连接词 ¬ neg ¬ (negation):取布尔变量的否定。例如 ¬ 1 = 0 neg1=0 ¬1 = 0 , ¬ 0 = 1 neg0=1 ¬0 = 1 。 ¬ ( ¬ a ) = a neg(neg a)=a ¬ ( ¬ a ) = a 。 合取

    2024年02月02日
    浏览(40)
  • 图论问题建模和floodfill算法

    目录 引入:leetcode695.岛屿的最大面积 分析与转换 一维二维转换 四联通 完整代码解答:  1)显示的创建图解决问题的代码 2)不显示的创建图解决此问题的代码 floodfill算法 定义 在题目中0是海水,1是陆地。在我们自己设定的图中假设蓝色是海水,红色是陆地。且每一个小格

    2024年02月06日
    浏览(39)
  • 图论与算法(7)最短路径问题

    最短路径问题是指在一个加权图中寻找两个顶点之间的最短路径,其中路径的长度由边的权重确定。 常见的最短路径算法包括: Dijkstra算法 :适用于解决单源最短路径问题,即从一个固定的起点到图中所有其他顶点的最短路径。该算法通过不断选择当前路径上权重最小的顶

    2024年02月06日
    浏览(42)
  • 【计算机算法】【图论】【最优匹配与点云对准问题】最(极)大团算法

    团与最大团的定义 图顶点集的子集满足任意两个顶点相邻,称该子集是该图的一个团。图的所有团中顶点最多的,即最大的一个或多个,称为图的最大团或极大团。 图的最大团的实际应用问题 CVPR2023最佳论文之一用最大团算法实现鲁棒的点云对准,有效解决外点问题。顾名

    2024年03月15日
    浏览(38)
  • 【图论】中国邮递员问题、平面图上最大割问题的多项式时间算法

    中国邮递员问题(Chinese Postman Problem, CPP)是图论中的一个著名问题,它是在1960年由我国学者管梅谷首先提出并研究的。简单来说,就是问:一个邮递员从邮局出发,把一个城市的所有街道都至少走一遍,最后回到邮局,问怎样使他走的总路程最小?这个问题有许多现实的应

    2024年02月12日
    浏览(39)
  • 数学建模十大算法04—图论算法(最短路径、最小生成树、最大流问题、二分图)

    一、最短路径问题 从图中的某个顶点出发,到达另一个顶点的 所经过的边的权重之和最小 的一条路径。 1.1 两个指定顶点之间的最短路径 问题如下:给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间,求一条最短铁路线。 1.1.1 Dijkstra算法 迪杰斯特拉(D

    2024年02月02日
    浏览(73)
  • 算法与数据结构——递归算法+回溯算法——八皇后问题

    八皇后问题是一个经典的回溯算法问题,目的是在8×8的国际象棋棋盘上放置八个皇后,使得没有皇后可以互相攻击(即没有两个皇后在同一行、同一列或同一对角线上)。 回溯算法是一种解决问题的算法,它通过尝试所有可能的解决方案来解决问题。在八皇后问题中,计算

    2024年02月09日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包