给定无向图，在逐条删除边时验证删除的边是否是桥，如果是 - 两个部分的顶点

Question

我正在为这个特定问题寻找一种高效的算法：

我的无向图最多有 10,000 个顶点，给定顶点有大约 1-10 条边。

现在我将从图中删除选定的边，我想知道我刚刚删除的边是否是一座桥 - 如果是，两边连接的顶点是什么。我会经常重复删除边的步骤，可能直到我得到 10 000 个断开连接的顶点（每次我需要桥的信息）。因此，例如，最后一条边应该告知它是一座桥，一侧有一个顶点，另一侧有一个顶点。

数据预处理是完全可以接受的，内存成本 - 在现代 PC 的合理范围内 - 还可以。我正在寻找一种优化边缘去除操作时间的算法。

我的交易工具是 C#，但我很乐意接受任何伪代码或想法

Answer 1

这个问题的近亲在名为“decremental connectivity”的文献中进行了研究。主要区别在于您想要枚举新连接的组件而不是能够回答连接查询。

This paper 似乎是最先进的理论，但略读了一下，我认为新想法对您没有用，因为您有一个图表

稀疏
可能太小了，无法发挥渐近优势
恰好是适合 L1 缓存的大小，但又足够大，您不能同时适应花哨的数据结构。

我的建议是 Even--Shiloach 的简化版本，其中省略了 BFS 部分（它增加了复杂性和内存消耗，但在稀疏图中似乎并没有明显获胜）。思路是维护

残差图
残差图的生成林
从顶点到表示连接组件的标签的映射。

如果一条不在森林中的边被删除，那么我们就直接删除它。否则，我们选择刚刚被砍掉的树的一侧（哪一侧的正确性无关紧要，但为了效率你想要较小的一侧；我建议对生成树进行生根并使用子树），遍历它以临时更新它的给新的东西贴上标签，然后扫描它的所有边，以确定刚刚删除的边是否是树的其余部分的桥梁。如果是，那太好了；遍历另一棵新树以报告顶点集。否则，我们必须修复标签和树结构。

对于数据结构，我推荐一个紧凑的邻接表。由于最多有 10,000 个节点，因此节点索引将适合 16 位 short。不幸的是，有多达 100,000 个半边，因此我们将使用 32 位 int 来表示边索引。我们用一个int数组指向一个short数组；条目 2*v 是节点 v 的邻接表的开头，条目 2*v+1 是结尾。对于缓存局部性，我们将两个额外的数据与邻接列表一起存储：连接的组件标签和生成森林中的后代数。在其他邻居之前对生成的森林后代进行排序。

总的来说，这是一张简单的图表：

Graph:
   0
  / \
 /   \
1-----3     2

Spanning forest:
   0
  /
 /
1-----3     2

Arrays:
[|   |   |   |   |   |   |   |  ]
 |   |   |    \  |   |   |   |
 |   |   |     \  \  |   |    \
 |    \   \     \  | |   |     |
 v     v   v     v v v   v     v
[0 1 1 3 x 0 1 3 0 2 0 x 0 0 0 1]
           ^ ^ \ /
           | |  |
           | |  adjacency list; descendants (3) before others (0)
           | |
           | number of spanning forest descendants
           |
           connected component label
             = root of tree in spanning forest

我留下 xs 来表示之前删除的从 0 到 2 的边。

（我没有很多 C# 经验，所以强制边界检查可能会出现问题，但我无法想象指针会更好，尤其是在 64 位机器上.)

给定无向图，在逐条删除边时验证删除的边是否是桥，如果是 - 两个部分的顶点

Given undirected graph when removing edges one-by-one verify if removed one was a bridge and if so - the vertices of both parts

algorithm

optimization

graph

graph-algorithm