大门|大门IT 2005 |问题14

在图中，n个顶点被标记为深度为k的边。G中连接组件的数量为 （A） K （B） k+1 （C） n-k-1 （D） n–k 答复: （D） 说明： 树边是DFS树的一部分。如果树中有x个树边，则树中有x+1个顶点。

如果图形断开连接，DFS的输出是一个林。下面我们来看一个简单的例子，图是断开连接的。

上面的示例与D选项匹配

更多示例：

1） 图的所有顶点都是连通的。k必须是n-1。n-k=1的组件数

2） 没有顶点是连通的。k必须是0。我们得到了连接组件的数量=n-k=n–0=n 这个问题的小测验