用BFS还是DFS确定非连通图的连通性？
2）从任意顶点开始对图进行DFS遍历。如果DFS遍历没有遍历所有顶点，则返回false。
3）求所有弧的反向（或求图的转置或反向）
4）在反向图中，将所有顶点标记为未访问顶点。
有没有关于如何改进这个解决方案的想法？。
共有1个答案
怎么样
- 让
顶点=输入 - 让
结果=空列表 - 而
顶点中有顶点：- 创建一个集
s - 选择任意未探测的顶点，并将其放入
s. - 从该顶点运行bfs/dfs，找到每个顶点后，将其从
顶点中删除，并将其添加到s中。 - 将
s添加到结果
完成后，您将得到一个顶点集合列表，其中每个集合都是从某个顶点搜索图生成的（使每个集合中的顶点相互连接）。假设是一个无向图，这应该可以工作（从我的头顶上）。
- 创建一个集
-
我在读关于BFS和DFS的图算法。当我在分析用DFS寻找图中强连通分量的算法时，我产生了一个疑问。为了寻找强连通分量，book（Coremen）首先在图上运行DFS，以得到顶点的完成时间，然后在图的转置上按照第一个DFS得到的完成时间的递减顺序运行DFS。但是我不能理解为什么第二个DFS必须按照完成时间运行。我的意思是，即使我们直接在图的转置上运行DFS（忽略完成时间），它也会给我们连接的组件吗？
-
主要内容：强连通图前面介绍了《 图存储结构》，本节继续讲解什么是 连通图。 前面讲过，图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的。例如图 1 中，虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径，分别是 和 ，因此称 V1 和 V3 之间是连通的。 图 1 顶点之间的连通状态示意图 无向图中，如果任意两个顶点之间都能够连通，则称此无向图为 连通图。例如，图
-
null 更新：最多1个简单路径。
-
我有一个强连通图。我想移除一个边并检查是否仍然保持强连接。因为我将N=图中节点的总数取为10，并且我感兴趣的大多数图都有25条以上的边，所以很难检查一次使用一条，去掉边。 如何解决这个问题？多谢了。
-
到目前为止，我已经使用了下面的算法来寻找图的强连通分量。 > 调用DFS(G)计算每个顶点v的完成时间F[v]，对G的顶点按完成时间递减的顺序排序； 计算G的转置GT；
-
主要内容：重连通图的实际应用,判断重连通图的方法在无向图中，如果任意两个顶点之间含有不止一条通路，这个图就被称为 重连通图。在重连通图中，在删除某个顶点及该顶点相关的边后，图中各顶点之间的连通性也不会被破坏。 在一个无向图中，如果删除某个顶点及其相关联的边后，原来的图被分割为两个及以上的连通分量，则称该顶点为无向图中的一个 关节点（或者 “割点”）。 图 1 连通图 图 1 是连通图但不是重连通图，图中有4个关节点，分别是：A、B、D 和