use*_*673 1 algorithm computer-science graph
我有一个强烈连接的图表.我想删除边缘并检查是否仍然保持强连接.当我拿N =图中的节点总数为10时,我感兴趣的大多数图表都有25个以上的边缘,很难一次性使用一个去除边缘.
如何解决这个问题呢 ？谢谢.
如果您删除的边是(u - > v),如果您可以找到从u到v的路径,图表将保持连接状态.您可以使用任何路径查找算法来检查这一点.
另一种选择是每次都从头开始运行连接检查算法; 这样做并不重要,因为图表非常小.
对于更大的图形,有针对此问题设计的特殊数据结构.它被称为"动态连接":https://en.wikipedia.org/wiki/Dynamic_connectivity