问题标签 [bipartite]

所以，我需要一些方法来在 C# 中实现一个无向网络（我认为这是正确的术语）

假设我有以下数据：

我将如何实现可以支持这一点的东西？

一种方法是创建一个包含 Foo 和 Bar 的类，在我的示例中，我将拥有其中的 6 个，每种可能的组合，但是这会使数据加倍。

有了这些数据，我需要能够根据它所指向的 Bar 点数以及 Foo 的 Bar 点数等对 Foo1 执行计算。

我不是在寻找答案，我更愿意就如何实现这一点提供一些指导，甚至可能是几个链接。

例如，假设我有一个图 G = (V, E) 其中

V = {A, B, C, D}
E = {(A, B), (A,D), (C, D)}

该图是二分图，因此可以分成两个不相交的集合 {A, C} 和 {B, D}。我的第一个猜测是我可以简单地遍历图形并为每个顶点分配交替颜色。是这种情况，还是比这更复杂/更简单？是否有任何已知的算法？

有人知道 Python 中计算最佳二分匹配的任何模块吗？我尝试了以下两个：

1. 芒克雷斯
2. 匈牙利

有什么建议吗？

我需要编写一个程序来检查一个图是否是二分的。

我已阅读有关图形着色和二分图的维基百科文章。这两篇文章提出了测试二分性的方法，例如 BFS 搜索，但我无法编写实现这些方法的程序。

更新

到目前为止，一些答案建议使用邻接列表。Java 中的邻接表是什么样子的？...没有正确的指针:)

我正在尝试在 Java 中实现一个二分图，以将文件中的信息分类为 2 组。我找到了这个例子，它确实完成了这项工作：

http://users.skynet.be/alperthereal/source_files/html/java/Bipartite.java.html

但是，我想实现我自己的版本...如果您查看我以前的帖子，您就会明白我为什么要自己做这个。

所以我必须读取一个文件，从中我可以很容易地得到顶点的数量，但边的数量并不那么容易。一个示例行是"PersonA PersonB"，可以读作"PersonA says PersonB"。所以阅读这些行...

...产生这个分组：

我将如何实现这个二分图？什么是这项任务的好资源？在创建 BipartiteGraph 类时，我应该考虑和考虑哪些事情（算法）......也许是遍历/排序算法？

I have a graph in form of a rectangular grid, i.e. N nodes and 2N edges, all adjacent nodes are connected. This means it is two-colourable, and hence it is possible to do bipartite matching on it.

Each (undirected) edge has a weight assigned to it - either -2, -1, 0, 1 or 2. No other values are allowed

How would I go about finding the matching on this graph that maximises the sum of the weighs in the matching? Pseudocode would be nice, don't bother with specific languages.

Ideally, I am looking for an algorithm that runs in quadratic time - maybe O(n^2 log n) at worst.

Before you propose a solution, I have tried doing a max match using edges of weight 2, then of weight 1 (without going over edges of weight 2). I have scored 98% with this implementation (the problem is from an informatics olympiad), and wondering what is the 100% solution.

我有一种单级树结构：

其中 p 是父节点，c 是子节点，b 是假设分支。

我想在只有一个父节点只能分支到一个子节点并且两个分支不能共享父节点和/或子节点的约束下找到所有分支组合。

例如，如果combo是一组组合：

我想这就是全部。=)

对于这种结构的任意树，如何在 Python 中自动实现这一点，即 p:s、c:s 和 b:s 的数量是任意的。

编辑：

它不是一棵树，而是一个二部有 向无环图

我正在尝试使用 networkx 作为图形表示在 Python 中实现Hopcroft Karp 算法。

目前我是这样的：

该算法取自http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm 但是它不起作用。我使用以下测试代码

不幸的是，这不起作用，我最终陷入了无限循环:(。有人能发现错误吗，我没有想法，我必须承认我还没有完全理解算法，所以它主要是伪的实现维基百科上的代码

假设我有一个图 G 及其邻接矩阵 A。我知道 G 是二分的。如何将 G 中的顶点拆分为始终形成二分图的两组？谢谢！

我在这里有一个问题，我设法减少到加权二分匹配问题。基本上，我有一个带有分区 A 和 B 的二部图，以及一组带有权重的边。就我而言，|A|~=20 和 |B| =300。

我想找到一组最小化权重并覆盖“A”的边（A上的每个边都有一个相关的解决方案边）

问题：

-这种问题有没有专门的名字，我可以找算法和解决方案？

-我知道我可以通过在 A 上添加具有无限权重的虚拟顶点来将其简化为加权二分完美匹配。但是我担心自从|B|>>|A|之后的实际性能。

- 对 Java 库有什么建议吗？我发现了这个：http ://algs4.cs.princeton.edu/code/ 。我认为“AssignmentProblem.java”几乎是我所需要的——（但我想它不能确保完美匹配？）

在此先感谢，并对糟糕的英语感到抱歉。