the*_*guy 8 algorithm graph data-structures
我有一个图表,从一个根节点开始.节点逐个添加到图表中.在节点创建时,它们必须通过单个边链接到根节点或另一个节点.也可以创建和删除边缘(在任意两个节点之间逐个删除).可以一次删除一个节点.节点和边创建,删除操作可以以任意顺序发生.
好的,所以这里是我的问题:当删除边缘时,是否可以在恒定时间内(即使用O(1)算法)确定,如果这样做会将图形分成两个不相交的子图形？如果是,那么根节点属于哪一边？
我愿意在合理的限度内维护任何可以促进此信息推导的附加数据结构.
也许在O(1)中不可能这样做,如果是这样的话,任何指向文学的人都会受到赞赏.
编辑:图表是有向图.
编辑2:好的,也许我可以限制从根节点删除边缘的情况.[编辑3:不,实际上]此外,没有边缘落入根节点.
为了加快显而易见的O(| V | + | E |)解决方案的速度,你可以保留一个生成树,当图形发生变化时,它很容易更新.
如果删除了不在生成树中的边缘,则图形不会断开连接并且不执行任何操作.如果删除生成树中的边缘,则必须尝试在这两个顶点之间找到新路径(如果找到一个,则使用它来更新生成树,否则图形将断开连接).
所以,最好的情况是O(1),最坏情况的O(| V | + | E |),但无论如何都要相当简单.
小智 2
这是有向图吗？下面假设无向。
您要寻找的是给定的边是否是图中的桥。我相信这可以通过遍历查找包含该边的循环来找到，并且时间复杂度为 O(|V| + |E|)。
O(1) 的要求太高了。
您可能会发现在动态图中维护 2 边连通分量可能对您有用。
Eppstein 等人对此有一篇论文：http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf
它可以在允许边插入和删除的 n 个节点的图中维护 2 边连通分量。每次更新的时间为 O(sqrt(n))，每次查询的时间为 O(log n)。
因此，每次删除时，都可以在 O(logn) 中查询以确定 2 边连通分量的数量是否发生变化。我想它还可以告诉您特定节点位于哪个组件中。
这篇论文更通用，适用于其他图问题，而不仅仅是 2 个边连通分量。
我建议您寻找网桥和动态 2 边缘连接来帮助您入门。
希望有帮助。