wap网站源码,苏州建网站公司,米拓建设网站,微信开发者平台取消授权文章目录 一、图的基本概念二、广度优先搜索#xff08;BFS#xff09;记录伪代码时间复杂度流程应用 三、深度优先搜索#xff08;DFS#xff09;记录伪代码时间复杂度流程时间戳结构BFS和DFS比较 四、拓扑排序一些概念有向图作用拓扑排序 分析伪代码时间复杂度彩蛋 五、强… 文章目录 一、图的基本概念二、广度优先搜索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 i1,2,...,k i1,2,...,k满足 ( V i − 1 , V i ) (V_{i-1},V_i) (Vi−1,Vi)序列中任意两点之间都是可达的。 简单路径序列中所有顶点都是不同的。
环一个路径 V 0 , V 1 , . . . , V k V_0,V_1,...,V_k V0,V1,...,Vk并且 V 0 V k V_0V_k V0Vk并且路径上所有边都是不同的 简单环 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(VE) T(n)O(VE) 邻接矩阵 A [ a i j ] , a i j 1 A[a_{ij}],a_{ij}1 A[aij],aij1 i f ( v i , v j ) 属于 E if(v_i,v_j)属于E if(vi,vj)属于E否则 a i j 0 a_{ij}0 aij0 因为不管怎样任意两点间有无边都要判断一遍因此时间复杂度 T ( n ) O ( V 2 ) T(n)O(V^2) T(n)O(V2)
二、广度优先搜索BFS
用处遍历图中的所有顶点从而显示图的属性
记录
三个数组用于保存遍历期间收集的信息。 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:已完成处理 p r e d [ u ] pred[u] pred[u]前一个指针指向发现u的顶点 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(1degree(u))O(VE) T(n)∑O(1degree(u))O(VE)
流程
一次BFSVisit能将连通分量遍历完
应用
最短路径问题查找连通分量
三、深度优先搜索DFS
用处同样也是遍历图中的所有顶点从而显示图的属性
记录
四个数组用于保存遍历期间收集的信息。 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:已完成处理 p r e d [ u ] pred[u] pred[u]前一个指针指向发现u的顶点 d [ u ] d[u] d[u]发现时间。设置一个全局变量时间发生器 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(1degree(u))O(VE) T(n)∑O(1degree(u))O(VE)
流程 时间戳结构 由图可知 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] upred[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| ∑out−degree(v)∑in−degree(v)∣E∣
作用
有向图通常用于表示顺序相关的任务也就是说我们不能在另一个任务完成之前启动一个任务。 边(u, v)表示任务u完成后才能启动任务v。 显然要使系统不挂起图必须是无环的它必须是有向无环图(或DAG)
拓扑排序
拓扑排序是一种针对有向无环图的算法对顶点进行线性排序使得对于DAG中的每条边(u, v) u在线性排序中出现在v之前。 它可能不是唯一的因为有许多“不兼容”的元素。
分析
起始顶点入度必须为0如果这样的顶点不存在图就不是无环的。一个入度为0的顶点是一个可以马上开始的任务。所以我们可以先以线性顺序输出它.如果输出一个顶点u那么所有的边(u, v)都不再有用因为任务v不再需要等待u。去掉顶点u后新图仍然是一个有向无环图重复步骤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(VE) T(n)O(VE)
彩蛋
也可用DFS求出拓扑序列对于每个有向边都有 f [ u ] f [ v ] f[u]f[v] f[u]f[v]
在时间O(VE)内计算出 D A G DAG DAG有向无环图中的单源最短路径动态规划
五、强连通分量-SCC
任意两点之间都有路径再增加一个点都不满足这个关系。 任何两个强连通分量交集都为空 找到一个算法求一个图得所有连通分量
分析
对G中所有边的方向进行反转得到逆图GR。执行DFS并获得GR中顶点变黑的序列即每当一个顶点从堆栈中弹出时将其附加到序列 L R L^R LR中将 L R L^R LR倒序得到序列L对原图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(VE) O(VE)DFS时间复杂度为 O ( V E ) O(VE) O(VE),然后还是依次遍历每个点和边时间复杂度也是 O ( V E ) O(VE) O(VE)因此总时间复杂度为 T ( n ) O ( V E ) T(n)O(VE) T(n)O(VE)
