[精华]图的连通性总结

[精华]图的连通性总结图的连通性总结 boboo 目录 1. 图的遍历及应用 1.1. DFS遍历 1.2. DFS树的边分类 1.3. DFS树的性质 1.4. 拓补排序1.5. 欧拉回路 2. 无

[精华]图的连通性总结 图的连通性总结 boboo 目录 1.图的遍历及应用 1.1.DFS遍历 1.2.DFS树的边分类 1.3.DFS树的性质 1.4.拓补排序 1.5.欧拉回路 2.无向图相关 2.1求割顶 2.2求图的桥 2.3求图的块 3.有向图相关 3.1求强连通分量(SCC划分) 3.2求传递闭包4.最小环问题 一、图的遍历及应用 1.1DFS遍历 DFS是求割顶、桥、强连通分量等问题的基础。 DFS对图进行染色， 白色:未访问; 灰色:访问中(正在访问它的后代);