我有一个无向图 . 有没有什么有效的算法可以找到两个节点之间的所有独立连接？通过独立，我的意思是这些连接可以有共同的节点，但不能有共同的边缘 .
在此示例中，有2个独立的连接，从0到8（0-2-3-4-8或0-5-6-7-8） . 我尝试连续使用广度优先搜索算法，而我已经看过“伪删除”边缘 . 问题是我可以通过这种方式通过图表：0-5-4-8这是不对的，因为我不能做任何其他路径 .
谢谢你的帮助！
您感兴趣的是解决源和接收器之间的最小切割问题（您感兴趣的第一个节点是源，第二个是接收器） .
Here您可以阅读有关此任务的方法 . 基本上我链接到一个定理，证明源和接收器之间的最大流量等于最小切割 . 您对最小切割感兴趣，因为这正是为了使源和接收器断开而需要移除的最小边数 .
如果运行Ford Fulkerson max flow algorithm，则可以在算法完成后考虑哪些反向边具有容量，重建从源到接收器的不同路径 . 最后一点 - 福特富尔克森在有向图中经典地描述 . 为了使其适用于您的无向情况，将每个边缘表示为面向相反方向的两个单独的定向边缘 . 您的所有初始容量应等于1 .
1 回答
您感兴趣的是解决源和接收器之间的最小切割问题（您感兴趣的第一个节点是源，第二个是接收器） .
Here您可以阅读有关此任务的方法 . 基本上我链接到一个定理，证明源和接收器之间的最大流量等于最小切割 . 您对最小切割感兴趣，因为这正是为了使源和接收器断开而需要移除的最小边数 .
如果运行Ford Fulkerson max flow algorithm，则可以在算法完成后考虑哪些反向边具有容量，重建从源到接收器的不同路径 . 最后一点 - 福特富尔克森在有向图中经典地描述 . 为了使其适用于您的无向情况，将每个边缘表示为面向相反方向的两个单独的定向边缘 . 您的所有初始容量应等于1 .