ma22.11 Theorem 22.12 A directed graph G is acyclic if and only if 2 Topological-Sort(G) produces a a depth-first search of G yields no back al sort of a directed acyclic graph G C Proof. It makes a cycle in the graph if there exists a back edges 证明 穿衣实例 设DFS在图G=(E运行完毕并得到所有顶点的 我们只需要证明对任意的边(uv)都有 这能实 面(uv)成为回退边矛盾,故v只 是白的,它将成为u的孩子【后代】,故有 色,则它已经被搜索完毕,而u还未结束,故 逆挂列后所有的边将有序 Strongly connected components a Strongly-Connected-Components(G 1. Call DFS(G) to compute finishing time f[u 强连通分支 2. Compute G Definition: in a directed graph, a strongly 3. Call DFS(G), but in the main loop of DFS connected component contains maximal the vertices is selected in the order of set of vertices C subset of V such that fo decreasing f[u every pair of vertices u and v in C, we 4. Output the vertices of each tree in the second DFS(G), we got the separate have both u -->v and v->u trongly connected components9 清华大学 宋斌恒 49 Lemma22.11 Lemma22.11 A directed graph G is acyclic if and only if a depth-first search of G yields no back edges Proof. It makes a cycle in the graph if there exists a back edges. 清华大学 宋斌恒 50 Theorem 22.12 Theorem 22.12 Topological-Sort(G) produces a topological sort of a directed acyclic graph G. 清华大学 宋斌恒 51 证明 设 DFS 在图G=(V,E)运行完毕并得到所有顶点的 完成时间。我们只需要证明对任意的边(u,v)都有 f[v]<f[u]. 考虑对G中任意边(u,v)，当此边被搜索到时，【此时u 是灰色的，】v不能是灰色的。 如果这样，v是u的祖先，而(u,v)成为回退边矛盾,故v只 能是白或黑， 如果v是白的，它将成为u的孩子【后代】，故有 f[v]<f[u]， 如果是黑色，则它已经被搜索完毕，而u还未结束，故 有f[v]<f[u]。 按照完成时间逆序排列后所有的边将有序。 清华大学 宋斌恒 52 穿衣实例 袜子 鞋 裤子 裤带 手表 衬衣 领带 内裤 手套 大衣 清华大学 宋斌恒 53 Strongly connected components Strongly connected components 强连通分支！ Definition: in a directed graph, a strongly connected component contains maximal set of vertices C subset of V such that for every pair of vertices u and v in C, we have both u --->v and v -->u. 清华大学 宋斌恒 54 Strongly-Connected-Components(G) 1. Call DFS(G) to compute finishing time f[u] 2. Compute GT 3. Call DFS(GT), but in the main loop of DFS, the vertices is selected in the order of decreasing f[u] 4. Output the vertices of each tree in the second DFS(GT), we got the separate strongly connected components