怎么用深度优先判断一个图是否连通

Question

有一个无向图，找到相应的边，去掉这条边这个图就不是连通的。求相应算法。在线等。作业题急！

Answer 1

在图论中，连通图基于连通的概念。在一个无向图G中，若从顶点v_i到顶点v_j有路径相连（当然从v_j到v_i也一定有路径），则称v_i和v_j是连通的。如果G是有向图，那么连接v_i和v_j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。

所以问题的关键是使用深度优先判断缺少某一边后图中是否任意两点连通。
一个基本的思路如下：
设计所有边的集合L；
任取 一个未使用删除手段的边l∈L（LOOP）：
在（新开辟的）图中删除边，
使用深度优先搜索遍历所有节点
如果每一个节点都遍历到，则非目标边
否则，记录该边（如不只一条，须记录成类似数组的结构里）
END LOOP