有向图密度缩减流程是否会导致处理后的图不连通？

原因分析： #

原输入是完全加权有向图，任意两点间初始都存在直接弧。删除弧的规则是：仅当存在中间顶点j，使得从i到j、j到k的弧均存在，且路径i→j→k的总权重不大于直接弧i→k的权重时，才删除i→k的弧。

• 如果i→k的弧未被删除：两点间直接连通。
• 如果i→k的弧被删除：说明删除时存在至少一个顶点j，使得i→j和j→k的弧均存在。即使后续j→k的弧也被删除，那j→k的弧被删除的前提是存在另一个顶点m，使得j→m和m→k的弧存在，此时i到k可通过路径i→j→m→k连通。以此类推，由于顶点数量有限，不可能无限递归，最终总能找到一条由未被删除的弧组成的路径连接i和k。

简言之，所有被删除的弧都存在可替代的路径，因此处理后的图中任意两点间始终保持连通性。

内容的提问来源于stack exchange，提问作者Farah Mind