匹配图的算法

Question

如果我们有一定数量的节点与边相连(比如与街道的十字路口)，并且每个节点的值为 0 到 3。边的值为 0。

现在我想编写一个算法，将节点的值分配给值边，因此在算法终止后所有节点的值为 0 并且所有边 <= 1。

例如，给定这张图:

我想制作这个:

.

我的解决方案:

我已经定义了数据类型 Crossing 和 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-B-C，其中 A 和 B 的值为 1(而 C 的值为 0)，那么如果将 B 的值提供给 A-B 交叉而不是 B-C 交叉(因为那时A 值无处可去)。

我建议阅读最大流量算法，例如与 this topcoder tutorial

要使用最大流算法解决此问题，您希望定义一个新的有向图。这个新图表有一个节点代表你的每个十字路口，一个节点代表你的每条街道(加上源节点和汇节点)。

你需要边缘:

1. 从源头到每个路口，通行能力等于路口的值
2. 从每个十字路口到其连接的容量为 1 的街道
3. 从每条街道到容量为1的sink节点

如果您构造从源头到汇点的最大流量，那么从十字路口到街道的边中的流量会告诉您如何分配值。