匹配图的算法

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 的街道
从每条街道到容量为1的sink节点

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

匹配图的算法

Algorithm for Matching a Graph

algorithm

graph

bipartite

graph-algorithm