2

在二分图中有一个表示连接的二元方阵。问题是：是否存在所有行到列的一对一映射？（需要明确的是，如果我使用的语言错误，完全连接的图可以满足这个要求，因为我们不仅限于一对一的映射）。

我写了以下内容。有没有更快的方法来实现这一点？

/* Is there a one-to-one mapping possible with the given bipartite graph?
   input:  graph[a][b] = connected (1) or not (0)
   return: 0=no 1=yes */
int one_to_one(int graph[SIZE][SIZE], int rows_checked /* =0 */, int col_chosen /* =0 */)
{
    int my_graph[SIZE][SIZE], i, j, retval;
    memcpy(my_graph, graph, sizeof(graph[0][0]) * SIZE * SIZE);

    if (rows_checked > 0) 
        for (i=rows_checked; i<SIZE; i++)
            my_graph[i][col_chosen] = -1; /* flag for "this column done" */

    retval=1;
    for (i=0; i<SIZE; i++) {
        if (my_graph[rows_checked][i] == -1)
                    continue;
        retval=0;
        if (my_graph[rows_checked][i] == 1)
            if (one_to_one(my_graph, rows_checked+1, i))
                return 1;
    }
    return retval;
}
4

1 回答 1

1

我假设在您的表示中，您的意思是您有一个二分图，其中两个“边”具有相同数量的节点，并且该图 [A][B] 表示在“如果每个分区中的所有节点都布置在一条垂直线上，则左”到“右”上的节点 B。

如果图形稀疏，您的算法实际上并没有那么糟糕，并且它具有简单的优点。

对于更密集的图，它是指数级的，如果你愿意为它编写代码，你可以做得更好。如果将源节点添加到连接到所有“左”节点的图中，以及连接到所有“右”节点的接收器，并将容量 1 分配给包括新边在内的所有边，则从源到的最大网络流量当且仅当存在一对一配对时，sink 才等于 SIZE。如果您使用诸如Ford-Fulkurson之类的算法来计算流量，则每个循环将连接一对额外的节点，并根据需要重新排列现有连接以实现这一点，直到不再可能为止。运行时将在 SIZE^3 范围内。

这也可以直接根据二分图表示和重新排列匹配对来实现，但我发现如果您将其构建为网络流实现开始然后从那里重构回来，这是最容易理解的。如果在二分图中找到最大数量的匹配对，请参阅Wikipedia page on graph matching questions 的“二分图中的最大匹配”部分，以获取有关稍微更普遍的问题的信息，这实际上是基于流的解决方案解决。

如果您真的想要速度，请查看Hopcroft-Kamp，我还没有实现它，现在正在阅读关于我自己的信息。链接的页面表明它的最坏情况（在此示例中）为 SIZE^(5/2)，并且在优化稀疏图方面与 Ford-Fulkerson 一样好或更好。

于 2011-05-05T02:00:00.760 回答