U4_1:图论之DFS/BFS/TS/Scc

2023-11-22 06:36
文章标签 图论 bfs dfs ts u4 scc

本文主要是介绍U4_1:图论之DFS/BFS/TS/Scc,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 一、图的基本概念
  • 二、广度优先搜索(BFS)
    • 记录
    • 伪代码
    • 时间复杂度
    • 流程
    • 应用
  • 三、深度优先搜索(DFS)
    • 记录
    • 伪代码
    • 时间复杂度
    • 流程
    • 时间戳结构
    • BFS和DFS比较
  • 四、拓扑排序
    • 一些概念
      • 有向图
      • 作用
      • 拓扑排序
    • 分析
    • 伪代码
    • 时间复杂度
    • 彩蛋
  • 五、强连通分量-SCC
    • 分析
    • 伪代码
    • 时间复杂度

一、图的基本概念

由点(vertices)和边(edges)组成
G = ( V , E ) G=(V,E) G=(V,E) ∣ V ∣ = n |V|=n V=n, ∣ E ∣ = m |E|=m E=m (这里默认有向图,无向图用 G G G = = ={ V V V, E E E}表示

顶点的度是关联在其上的边的数量。满足 ∑ d e g r e e ( v ) = 2 ∣ E ∣ \sum degree(v)=2|E| degree(v)=2∣E(握手定理)

路径:一个序列 < V 0 , V 1 , . . . , V k > <V_0,V_1,...,V_k> <V0,V1,...,Vk> i = 1 , 2 , . . . , k i=1,2,...,k i=1,2,...,k满足 ( V i − 1 , V i ) (V_{i-1},V_i) (Vi1,Vi),序列中任意两点之间都是可达的。
简单路径:序列中所有顶点都是不同的。

环:一个路径 < V 0 , V 1 , . . . , V k > <V_0,V_1,...,V_k> <V0,V1,...,Vk>并且 V 0 = V k V_0=V_k V0=Vk并且路径上所有边都是不同的
简单环: V 1 , V 2 , . . . , V k V_1,V_2,...,V_k V1,V2,...,Vk是不同的。

连通:两个点之间存在路径。每个顶点对之间都连通,则这个图是连通的

连通分量:两点之间连通的最大集合的个数(等价类)。如下图:
在这里插入图片描述
子图: G ′ G' G的点和边都属于 G G G
诱导子图: G ′ G' G的点属于 G G G,且连接点的所有边都要属于 G ′ G' G

在这里插入图片描述

邻接表Adj:用链表连接每个点的边。因此是遍历了每个点和每条边,因此时间复杂度 T ( n ) = O ( V + E ) T(n)=O(V+E) T(n)=O(V+E)
在这里插入图片描述
邻接矩阵: A = [ a i j ] , a i j = 1 A=[a_{ij}],a_{ij}=1 A=[aij],aij=1   i f ( v i , v j ) 属于 E if(v_i,v_j)属于E if(vi,vj)属于E,否则 a i j = 0 a_{ij}=0 aij=0
因为不管怎样任意两点间有无边都要判断一遍,因此时间复杂度 T ( n ) = O ( V 2 ) T(n)=O(V^2) T(n)=O(V2)
在这里插入图片描述

二、广度优先搜索(BFS)

用处:遍历图中的所有顶点,从而显示图的属性

记录

三个数组用于保存遍历期间收集的信息。

  1. c o l o r [ u ] color[u] color[u]:访问的每个顶点的颜色
    W H I T E WHITE WHITE:未发现
    G R A Y GRAY GRAY:已发现但未完成处理
    B L A C K BLACK BLACK:已完成处理
  2. p r e d [ u ] pred[u] pred[u]:前一个指针:指向发现u的顶点
  3. d [ u ] d[u] d[u]:从源到顶点u的距离

伪代码

BFS(G)
for u in V docolor[u] ← WHITE;pred[u] ← NULL;
end
for u in V doif color[u] is equal to WHITE thenBFSVisit(u);end
endBFSVisit(s)
color[s] ← GRAY,d[s] ← 0;
set Q a queue
Enqueue(Q,s)
while Q is not empty dou ← Dequeue(Q)for v is belong to Adj[u] do   (邻接表遍历的)if(color[v] = WHITE) thencolor[u] ← GRAYd[v] ← d[u]+1pred[v] ← uEnqueue(Q,v)endendcolor[u] ← BLACK
end

时间复杂度

每一次循环遍历,都是遍历一个点和其边,且边遍历过了其他边就不会再遍历,因此
T ( n ) = ∑ O ( 1 + d e g r e e ( u ) ) = O ( V + E ) T(n)=\sum O(1+degree(u))=O(V+E) T(n)=O(1+degree(u))=O(V+E)

流程

一次BFSVisit,能将连通分量遍历完
在这里插入图片描述

应用

  1. 最短路径问题
  2. 查找连通分量

三、深度优先搜索(DFS)

用处:同样也是遍历图中的所有顶点,从而显示图的属性

记录

四个数组用于保存遍历期间收集的信息。

  1. c o l o r [ u ] color[u] color[u]:访问的每个顶点的颜色
    W H I T E WHITE WHITE:未发现
    G R A Y GRAY GRAY:已发现但未完成处理
    B L A C K BLACK BLACK:已完成处理
  2. p r e d [ u ] pred[u] pred[u]:前一个指针:指向发现u的顶点
  3. d [ u ] d[u] d[u]:发现时间。(设置一个全局变量时间发生器)
  4. f [ u ] f[u] f[u]:结束时间。一个计数器,指示顶点u(及其所有后代)的处理何时完成

伪代码

DFS(G)
for u in V docolor[u] ← WHITE;pred[u] ← NULL;
endtime  ← 0
for u in V doif color[u] is equal to WHITE thenDFSVisit(u);end
endDFSVisit(u)
color[u] ← GRAY,d[u] ← ++time;
set Q a queue
Enqueue(Q,s)
for v is belong to Adj[u] do   (邻接表遍历的)if(color[v] = WHITE) thenpred[v] ← uDFSVisit(v)end
end
color[u] ← BLACK
f[u] ← ++time;

时间复杂度

同样,每一次循环遍历,都是遍历一个点和其边,且边遍历过了其他边就不会再遍历,因此
T ( n ) = ∑ O ( 1 + d e g r e e ( u ) ) = O ( V + E ) T(n)=\sum O(1+degree(u))=O(V+E) T(n)=O(1+degree(u))=O(V+E)

流程

在这里插入图片描述

时间戳结构

在这里插入图片描述
由图可知, u u u v v v的后代(在 D F S DFS DFS树中),当且仅当 [ d [ u ] , f [ u ] ] [d[u],f [u]] [d[u],f[u]] [ d [ v ] , f [ v ] ] [d[v],f [v]] [d[v],f[v]]的子区间

树边: i f ( u , v ) ∈ E f if (u, v)∈E_f if(u,v)Ef等价 u = p r e d [ v ] u = pred[v] u=pred[v],即 u u u D F S DFS DFS树中 v v v的前身(图中蓝色边)
后边缘:如果 v v v D F S DFS DFS树中 u u u的祖先(不包括前身)(图中红色边)
有边就有祖先和后代的关系
在这里插入图片描述

BFS和DFS比较

BFS是发现点之后先处理,DFS是发现点之后不处理,继续往下去找其他的点。

四、拓扑排序

一些概念

有向图

有向图,区分边(u, v)和边(v, u)
顶点的出界度是离开它的边的数量,顶点的入界度是进入它的边的数量
每条边(u, v)对u的出阶贡献1次,对v的入阶贡献1次
∑ o u t − d e g r e e ( v ) = ∑ i n − d e g r e e ( v ) = ∣ E ∣ \sum out-degree(v)=\sum in-degree(v)=|E| outdegree(v)=indegree(v)=E

作用

有向图通常用于表示顺序相关的任务,也就是说,我们不能在另一个任务完成之前启动一个任务。
边(u, v)表示任务u完成后才能启动任务v。
显然,要使系统不挂起,图必须是无环的,它必须是有向无环图(或DAG)

拓扑排序

拓扑排序是一种针对有向无环图的算法,对顶点进行线性排序,使得对于DAG中的每条边(u, v), u在线性排序中出现在v之前。
它可能不是唯一的,因为有许多“不兼容”的元素。

分析

  1. 起始顶点入度必须为0,如果这样的顶点不存在,图就不是无环的。
  2. 一个入度为0的顶点是一个可以马上开始的任务。所以我们可以先以线性顺序输出它.
  3. 如果输出一个顶点u,那么所有的边(u, v)都不再有用,因为任务v不再需要等待u。
  4. 去掉顶点u后,新图仍然是一个有向无环图
  5. 重复步骤2-4,直到没有顶点留下

伪代码

Initialize Q to be an empty queue
for u is belong to V do thenif u.in_degree is equal to 0 thenEnqueue(Q,u)end
end
while Q is not empty dou ← Dequeue(Q)Output u;for v is belong to Adj(u) dov.in_degree ← v.in_degree-1if v,in_degree is equal to 0 thenEnqueue(Q,v)endend
end

时间复杂度

依旧是每条边和每个顶点都遍历一遍,因此时间复杂度 T ( n ) = O ( V + E ) T(n)=O(V+E) T(n)=O(V+E)

彩蛋

也可用DFS求出拓扑序列,对于每个有向边,都有 f [ u ] > f [ v ] f[u]>f[v] f[u]>f[v]

在时间O(V+E)内计算出 D A G DAG DAG(有向无环图)中的单源最短路径:动态规划

五、强连通分量-SCC

任意两点之间都有路径,再增加一个点都不满足这个关系。
任何两个强连通分量交集都为空
在这里插入图片描述
找到一个算法,求一个图得所有连通分量

分析

  1. 对G中所有边的方向进行反转,得到逆图GR。
  2. 执行DFS,并获得GR中顶点变黑的序列,即每当一个顶点从堆栈中弹出时,将其附加到序列 L R L^R LR中,将 L R L^R LR倒序得到序列L
  3. 对原图G执行DFS,规则如下
    规则1:从L的第一个顶点开始DFS
    规则2:当需要重新开始时,从L的第一个仍然是白色的顶点开始
    将每个dfs树中的顶点输出为SCC
    在这里插入图片描述

伪代码

R ← {}
Reverse G and get G'
DFS G' and get L'
reverse L' and get L
for u属于L doif color[u] is WHITE thenLscc ← DFSVisit(G,u)R ← RUSet(Lscc)end
end

时间复杂度

翻转边需要遍历每个点和边,时间复杂度为 O ( V + E ) O(V+E) O(V+E),DFS时间复杂度为 O ( V + E ) O(V+E) O(V+E),,然后还是依次遍历每个点和边,时间复杂度也是 O ( V + E ) O(V+E) O(V+E),因此总时间复杂度为 T ( n ) = O ( V + E ) T(n)=O(V+E) T(n)=O(V+E)

这篇关于U4_1:图论之DFS/BFS/TS/Scc的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/408218

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

nyoj99(并查集+欧拉路+dfs)

单词拼接 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 5 描述 给你一些单词,请你判断能否把它们首尾串起来串成一串。 前一个单词的结尾应该与下一个单词的道字母相同。 如 aloha dog arachnid gopher tiger rat   可以拼接成:aloha.arachnid.dog.gopher.rat.tiger 输入 第一行是一个整

【代码随想录训练营第42期 续Day52打卡 - 图论Part3 - 卡码网 103. 水流问题 104. 建造最大岛屿

目录 一、做题心得 二、题目与题解 题目一:卡码网 103. 水流问题 题目链接 题解:DFS 题目二:卡码网 104. 建造最大岛屿 题目链接 题解:DFS  三、小结 一、做题心得 也是成功补上昨天的打卡了。 这里继续图论章节,还是选择使用 DFS 来解决这类搜索问题(单纯因为我更熟悉 DFS 一点),今天补卡的是水流问题和岛屿问题。个人感觉这一章节题对于刚