我有一个无向图。有没有有效的算法来找到两个节点之间的所有独立连接？我所说的独立是指这些连接可以具有公共(public)节点，但不能具有公共(public)边。
在此示例中，有 2 个从 0 到 8 的独立连接(0-2-3-4-8 或 0-5-6-7-8)。我尝试连续使用广度优先搜索算法，同时“伪删除”我已经看到的边缘。问题是我可以这样浏览图表:0-5-4-8，这是不正确的，因为我无法创建任何其他路径。
感谢您的帮助!
最佳答案
您感兴趣的是解决源和汇之间的最小割问题(您感兴趣的第一个节点是源，第二个是汇)。
Here您可以阅读有关此任务的方法。基本上，我链接到一个定理，证明源和汇之间的最大流量等于最小切割。您对最小切割感兴趣，因为这正是为了使源和接收器断开连接而需要删除的最小边数。
如果您运行Ford Fulkerson max flow algorithm您可以在算法完成后考虑哪些反向边缘具有容量来重建从源到接收器的不同路径。最后一点——福特富尔克森是用有向图进行经典描述的。为了使其适用于无向情况，请将每条边表示为两个面向相反方向的单独有向边。所有初始容量应等于 1。
关于algorithm - 查找图中所有独立连接，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42740288/