图的匹配算法

Question

如果有一定数量的节点与边缘连接(如与街道交叉)，且每个节点的值为0到3，则边的值为0。

现在我想写一个算法，它将节点的值分配给值边，所以在算法终止后，所有节点的值都是0，而所有的边都是<= 1。

例如，给定此图表：

​

​

我想制作这个：

​

。

我的解决方案：

我已经定义了数据类型-十字路口和Street：

public class Crossing{
    int value;
}

public class Street{
    int value;
    Crossing A, B;
}

该算法迭代交叉路口并将值分配给街道(注意，交叉口只能将其值分配给相邻的街道)。

void allocate(Crossing[] crossings, Street[] streets){
    foreach(crossings as c){ //iterate through every Crossing
        foreach(streets as s){ //Find the streets, which are adjacent to c
            if((s.A == c || s.B == c) && s.value < 1 && c.value != 0) 
                // The value of the crossing is >0 and the value of the 
                // street is 0.
                c.value -= 1;
                s.value += 1;
        }
    }
}

我的算法有用吗？如果是:这是否有效，还是有更好的解决方案？

Answer 1

恐怕你的算法不会总是起作用。

例如，如果节点A的A值和B值为1(而C值为0)，那么如果将来自B的值赋予A交叉，而不是B交叉(因为A值没有任何去处)，则算法将失败。

我建议阅读最大流算法，例如使用本topcoder教程

要用最大流算法解决这个问题，您需要定义一个新的有向图。这个新的图表有一个节点，用于您的每个交叉点，一个节点用于您的每条街道(加上一个源和接收器节点)。

你需要边缘：

1. 从源头到每个交叉口，其容量等于交叉口上的值。
2. 从每个交叉口到连接的街道
3. 从每条街道到容量为1的接收器节点

如果您构造了从源到汇的最大流，那么从交叉口到街道边缘的流就会告诉您如何分配值。