如何在Java中实现二分图？

Question

UPDATE

到目前为止,一些答案建议使用邻接列表.在Java中,邻接列表如何？...没有指针正确:)

我正在尝试用Java实现一个Bipartite Graph,从文件中分成两组信息.我找到了这个例子,它实际上完成了这项工作:

但是,我想实现我自己的版本......如果你看一下我以前的帖子,你就会明白我为什么要这样做.

所以我必须读取一个文件,我可以从中轻松获得顶点数,但边数不是那么容易.一个示例行是"PersonA PersonB",可以读作"PersonA说PersonB".所以阅读这些内容......

"A says B"
"C says B"
"D says B"
"B says D"
"E says A & C"

...产生这种分组:

{A,D,C} and {B,E}.

我将如何实施这个二分图？什么是这项任务的好资源？在创建BipartiteGraph类时,我应该考虑和思考什么(算法)......也许是遍历/排序算法？

Answer 1

使用邻接列表实现它应该非常简单.如果它是一个无向二分图,我可能会建议使用一个关联矩阵.

因此,对于每个节点,您将拥有一个链接列表数组,或者某种动态分配列表的数组.它应该使添加边缘相当自然,例如在你的例子中你有一个边缘:

人A->人B.

然后你去对应于Person A的数组索引并推回对应于Persona B的索引:

[人A] =人B.

那么也许你会有另一个优势

角色A->人C.

然后你的索引看起来像:

[女神异闻录A] = B人,C人

作为最后一个示例,这将是示例图的邻接列表:

[A] B.

[B] D.

[C] B.

[D B

[E] A,C

每个索引都有一个可从该节点到达的节点列表.

"在创建BipartiteGraph类时,我应该考虑和思考什么(算法)......也许是遍历/排序算法？"

这真的取决于你想用图表做什么......