在二部图中查找映射
有一个二分方阵表示二分图中的连接。问题是：是否存在所有行到列的一对一映射？ （需要明确的是，如果我使用的语言错误，则完全连接的图可以满足此要求，因为我们不仅限于一对一映射）。
我写了以下内容。有没有一种更快的方法来实现这一目标？
/* 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;
}
There is a square binary matrix that denotes connections in a bipartite graph. The question is: does there exist a one-to-one mapping of all rows to columns? (To be clear, if I'm using the language wrong, a fully connected graph satisfies this requirement as we are not restricted to ONLY a one-to-one mapping).
I wrote the following. Is there a ridiculously faster way to accomplish this?
/* 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;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我假设在您的表示中，您的意思是您有一个二部图，其中两个“边”具有相同数量的节点，并且该图[A][B] 意味着“上有来自节点 A 的连接”如果每个分区中的所有节点都布置在垂直线上，则“左”到“右”的节点 B。
如果图形稀疏，您的算法实际上并没有那么糟糕，并且它具有简单的优点。
对于更密集的图，它是指数级的，如果您愿意为其编写代码，您可以做得更好。如果将一个源节点添加到连接到所有“左”节点的图中，并添加一个连接到所有“右”节点的接收器，并将容量 1 分配给包括新边在内的所有边，则从源到的最大网络流量当且仅当存在一对一配对时，sink 等于 SIZE。如果使用诸如 Ford-Fulkurson 之类的算法来计算流量，则每个循环都会连接一对额外的节点，根据需要重新排列现有连接以实现这一点，直到不再可能为止。运行时将在 SIZE^3 之内。
这也可以直接根据二分图表示和重新排列匹配对来实现，但我发现如果将其构建为网络流实现来启动然后从那里重构回来，那么最容易理解。请参阅有关图匹配问题的维基百科页面的“二分图中的最大匹配”部分 有关稍微更一般的问题的信息，如果在二部图中找到最大数量的匹配对，这就是基于流的解决方案实际解决的问题。
如果你真的想要速度，请查看我尚未实现的 Hopcroft-Kamp我现在正在阅读有关我自己的内容。链接的页面指出它的最坏情况（在本例中）为 SIZE^(5/2)，并且在优化稀疏图方面与 Ford-Fulkerson 一样好或更好。
I'm presuming that in your representation, you mean that you have a bipartite graph where both "sides" have the same number of nodes, and that graph[A][B] means that there is a connection from node A on the "left" to node B on the "right" if all the nodes in each partition were laid out in a vertical line.
Your algorithm actually isn't that bad if the graph is sparse, and it has the advantage of simplicity.
For denser graphs, it is exponential, and you can do better if you are willing to write the code for it. If you add a source node to the graph connected to all the "left" nodes, and a sink connected to all the "right" nodes, and assign capacity 1 to all edges including the new ones, then the maximum network flow from source to sink is equal to SIZE if and only if there's a one-to-one pairing. If you use an algorithm such as Ford-Fulkurson to calculate the flow, each loop will connect an additional pair of nodes, rearranging existing connections as needed to make that happen, until it's no longer possible. Runtime will be within SIZE^3.
This can also be implemented directly in terms of the bipartite graph representation and rearranging pairs of matches around, but I find it's easiest to understand if you build it as a network flow implementation to start and then refactor back from there. See the "Maximum matchings in bipartite graphs" section of the Wikipedia page on graph matching problems for info on the slightly-more-general problem if finding a maximal number of matched pairs in a bipartite graph, which is what the flow-based solution actually solves.
If you REALLY want speed, at a look at Hopcroft-Kamp which I have yet to implement and am just now reading about myself. The page linked states it has a worst case (in this example) of SIZE^(5/2) and is as good or better at optimizing for sparse graphs as Ford-Fulkerson.