Lecture5-图的遍历和强连通分支.ppt

图的遍历及强连通分支 高文宇 gwyy@163.com 图的表示 邻接表和邻接矩阵 广度优先有哪些信誉好的足球投注网站 BFS color[u]存放节点u的颜色信息。 ∏[u]存放节点u的父节点。 d[u]存放根（s）到节点u的距离。 广度优先有哪些信誉好的足球投注网站 Breadth-first search 广度优先树 根据BFS算法中保存的信息可以构造出一棵BFS生成树。 “∏[u]存放节点u的父节点” 深度优先有哪些信誉好的足球投注网站 Depth-first search 在DFS有哪些信誉好的足球投注网站过程中，也通过对顶点进行着色来表示顶点的状态。 （1）开始时，每个顶点都为白色；（2）有哪些信誉好的足球投注网站中被发现时即置为灰色；（3）结束时又被置为黑色（即当其邻接表被完全检索之后）。 除了创建一个深度森林之外，DFS有哪些信誉好的足球投注网站同时为每个顶点加盖时间戳。每个顶点v有两个时间戳：当顶点v第一次被发现时（置为灰色），记录下第一个时间戳d[v]，当结束检索v的邻接表（置为黑色）时，记录下第二个时间戳f[v]。时间戳为1到2|V|之间的整数，因为对每个顶点，都对应一个发现事件和一个完成事件。对每一个顶点u，有： d[u]f[u] 深度优先有哪些信誉好的足球投注网站 Depth-first search 深度优先有哪些信誉好的足球投注网站 Depth-first search DFS的性质 括号定理 深度优先有哪些信誉好的足球投注网站 Depth-first search DFS—边的分类 在图G上进行DFS所产生的深度优先森林，可以把图的边分为四种类型： （1）Tree edge，是DFS森林中的边。若顶点v是在探寻边(u, v)时被首次发现的，那么(u, v)就是一条树边。 （2）Back edge，在DFS树中，连接顶点u到它的某一个祖先顶点v的那些边。有向图中可能出现的自环也被认为是反向边。 （3）Forward edge，是指DFS树中，连接顶点u到它某个后裔v的非树边(u, v)。 （4）Cross edge，是其它类型的边，存在于同一棵DFS树中的两个顶点之间，条件是其中一个顶点不是另一个顶点的祖先。交叉边也可在不同的DFS树的顶点之间。 DFS—边的分类 可以对DFS算法进行一些修改，使之遇到图中的边时，对其进行分类。算法的核心思想在于对于每条边(u, v)，当该边被第一次搜寻到时，即根据所到达的顶点v的颜色，来对该边进行分类（只是对正向边和交叉边不作区分）。 （1）白色表明它是一条树边； （2）灰色表示它是一条反向边； （3）黑色表明它是一条正向边或交叉边，若d[u]d[v]，则(u, v)是一条正向边，若d[u]d[v]，则(u, v)是一条交叉边。 无向图DFS定理 定理22.10：在对一个无向图G进行DFS有哪些信誉好的足球投注网站的过程中，G的每一条边要么是树边，要么是反向边。 DFS的应用 无向图环的检测。 有向图环的检测—进行DFS的过程中若有回边（Back edge），则图中一定存在环，反之无环。 强连通分支 Strongly connected component 在寻找SCC时，用到了图G的转置，其定义为：GT = (V, ET)， 其中 ET = {(u, v) : (v, u)∈E } 即图G中的边全部反向。 定理： G和GT有着完全相同的强连通分支。 问题：图G中，若节点u可达v1,v2,…,vk，且v1,v2,…,vk可达u，则u和v1,v2,…,vk构成一个强连通分支。成立否？ 强连通分支 SCC SCC算法 下列线性时间算法 (Θ(V + E))可找出有向图G = (V, E)的SCC，该算法执行两次DFS，一次在 G 上，一次在 GT上。 SCC算法有效性分析 （1）第一次在G上进行DFS，得到一个生成森林，由若干棵生成树组成。每棵生成树表明从该树的根节点出发可以到达树中所有节点，但无法到达其它树的节点。 （2）第二次在GT上进行DFS，并按f[u]的降序，意味着从上一次的生成树的树根出发。因此这一次产生的生成树也意味着从树根出发可以到达树中所有节点，同时意味着在G中从树的所有非根节点出发可以到达根节点。所以这一次得到的生成树就构成SCC。 引理22.13 引理22.13：设C and C′是图G = (V, E)中不同的连通分量，设u, v ∈ C，且u′, v′ ∈ C′, 若图G中存在路径 u~?u′，则图G 中一定不存在路径v′~?v。 引理22.14 引理22.14：Let C and C′ be distinct strongly connected components in directed graph G = (V, E). Suppose that there is an edge (u, v) ∈ E, where u ∈ C and v ∈ C′. Then f (C) f(C′). 推论22.15 推论22.15：Let C an