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