学校网络-白红宇的个人博客

学校网络

发布日期：2021-05-14 16:51:22 浏览次数：27 分类：精选文章

本文共 383 字，大约阅读时间需要 1 分钟。

要解决给定图的问题：最少激活多少个点可以遍历整个图，以及最少需要添加几条边才能使每个点都能到达任何点（形成一个连通分量），可以按照以下步骤进行分析：

连通分量分析：首先确定图的连通分量数目（记为c）。每个连通分量至少需激活一个点，否则无法遍历到该分量。

结论：最少需要激活的点数等于连通分量的数目（c）。因为每个连通分量至少一个起点，才能通过深度优先搜索或广度优先搜索遍历整个图。

连通性需求：为了让整个图连通，需将所有连通分量合并成一个大的连通分量。

树结构转换：若原图是多个树构成的森林（各连通分量均为树结构），则分成c个树。

边数计算：要连通c个树，需添加c-1条边，类似将树连接成一个大树。

结论：最少需要添加的边数为（c - 1）。

最少激活点数：连通分量的数目，即c。

最少添加边数：c - 1（其中c为连通分量数目）。

上一篇：最大半连通子图

下一篇：174. 受欢迎的牛

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！