如何判断极小连通图和极大连通图

对于一个无向图 G，它的极小连通子图是指 G 的一个连通子图，去掉其中任意一个顶点后，该子图不再是连通的。而极大连通子图则是指 G 的一个连通子图，不能再加入任意一个 G 中未包含的顶点，使得该子图仍然是连通的。

判断一个无向图 G 的极小连通子图和极大连通子图可以使用 Tarjan 算法或 Kosaraju 算法。这两个算法都是基于深度优先搜索的强连通分量算法，可以找到图中的所有强连通分量。其中，极小连通子图就是由一个点或一个强连通分量构成，而极大连通子图则是由所有强连通分量构成的缩点图所形成的 DAG（有向无环图）的每一个强连通分量所对应的原图中的点集。

因此，我们可以先使用 Tarjan 或 Kosaraju 算法求出无向图 G 的所有强连通分量，然后将强连通分量缩点为一个点，得到一个 DAG，其中每个强连通分量对应一个点。最后，我们可以在 DAG 中找出所有入度为 0 的点，它们对应的强连通分量就是原图 G 的极小连通子图；同理，我们可以在 DAG 中找出所有出度为 0 的点，它们对应的强连通分量就是原图 G 的极大连通子图。

相关问题

在图中，什么是极大连通子图和极小连通子图

在无向图中，极大连通子图是指一个连通图中最大的连通子图，也就是说，如果加入任何一个不在该子图中的点都会导致它不再连通。而极小连通子图是指一个连通图的生成树，也就是说，用边把极小连通子图中所有节点给连起来，若有n个节点，则有n-1条边。如果删除一条边，就无法构成生成树，也就是说给极小连通子图的每个边都是不可少的。需要注意的是，极大连通子图和极小连通子图只存在于连通图中。