知识总结

连通性概念

• 连通：无向图中，两个顶点之间存在路径
• 连通图：任意两个顶点都连通的无向图
• 连通分量：无向图中的极大连通子图
• 强连通：有向图中，u到v和v到u都有路径
• 强连通图：任意两个顶点都强连通的有向图

树与图的关系

• 树是一种特殊的图：连通且无环
• n个顶点的树恰好有 n-1 条边
• 在树中添加一条边必然产生环
• 在树中删除一条边必然不连通

生成树

• 连通图的生成树：包含所有顶点的极小连通子图
• n个顶点的连通图的生成树有 n-1 条边
• 最小生成树（MST）：所有生成树中边权之和最小的

最小生成树算法

初赛常考

• 判断图是否连通
• 求连通分量个数
• n个顶点至少需要多少条边才能连通（答案：n-1）
• 生成树的边数